Как вставить слово в список в Python?

Question

У меня есть список.

Мне нужно добавить слово в список, но я не уверен, как это сделать.

Например,

У меня естьсписок = ['Alice', 'Amy', 'Andy', 'Betty', 'Eric', 'Peter', 'Richard', 'Tony']

Answer 1

Попробуйте использовать библиотеку bisect:

>>> import bisect
>>> someList = ["a", "b", "d"]
>>> bisect.insort(someList,'c')
>>> someList
['a', 'b', 'c', 'd']
>>> 

Answer 2

Во-первых, чтобы «проверить соответствие букв» между двумя строками, все, что вам действительно нужно, это <.Строки сравниваются лексикографически: 'abc' < 'abd' < 'acd' < 'acdd'.

---

При наличии связанного списка вам нужно искать узлы из головы, чтобы найти местоположение.Следите за предыдущим и следующим узлом по мере продвижения, и как только вы найдете next.head > value, вставьте новый узел после prev.(Если вы используете реализацию с голым узлом, убедитесь, что ваша функция возвращает заголовок, иначе нет возможности вставить перед заголовком.)

Конечно, это автоматически означает линейное время, чтобы найти правильную позицию(и, если вы используете неизменяемые узлы, то и линейное время для построения новых узлов обратно до головы).

Учитывая вашу реализацию, это может выглядеть как эти методы на SingleLinkedList:

def find_pos(self, element):
    '''Returns the position before element, or None if no such position'''
    prev, node = None, self._head
    while node:
        if node.element > element:
            return prev
        prev, node = node, node.next
    return prev

def insert(self, element):
    pos = self.find_pos(element)
    if pos:
        # add it after the node we found
        node = Node(element, pos.next)
        pos.next = node
    else:
        # add it before the current head
        node = Node(element, self._head)
        self._head = node
    self._size += 1

---

С такой структурой данных с произвольным доступом, как массив (Python list), вы можете bisect, чтобы найти правильное местоположение во время регистрации.Но с массивом вам все еще нужно линейное время, чтобы выполнить вставку, потому что все последующие значения должны быть сдвинуты вверх.(Хотя это обычно линейно с гораздо более быстрой константой, чем поиск по связанному списку.)

bisect.insort(lst, value)

И последнее: если вы выполняете тонну вставок в строке, часто более эффективноПакуй их.На самом деле, простой вызов extend, а затем sort может быть на самом деле быстрее, чем insort каждый, если число добавляемых элементов составляет значительную часть списка.

---

ЕслиВы хотите получить лучшее из обоих миров, вам нужна более сложная структура данных:

• Сбалансированное бинарное дерево поиска некоторого вида (красно-черный, AVL и т. д.) является традиционным ответом,хотя на практике это имеет тенденцию быть довольно медленным.
• Более широкое дерево поиска, как и любой из вариантов B-дерева, позволяет избежать большей части затрат на производительность двоичных деревьев (и позволяет выполнять поиск с более высокой базой журналов,для загрузки).
• Пропускаемый список - это связанный список с журналом N «высокоуровневых» связанных списков, пронизанных через него (или расположенных над ним), так что вы можете разделить его пополам.Есть и другие варианты этой концепции «индексированного списка».
• Существует несколько реализаций сложных гибридов в Python, например, структура deque / веревка с необязательным вариантом B-дерева, сложенным сверху.

Популярные реализации включают blist.sortedlist, sortedcontainers.SortedList, pybst.AVLTree и т. Д.

Но на самом деле, почтилюбая реализация любой такой структуры, которую вы найдете в Python, будет иметь встроенное поведение. Поэтому правильный ответ, вероятно, будет выглядеть примерно так:

lst.add(val)

Answer 3

В сыром питоне вы можете сделать:

def ins_sorted(toIns, list): # insert a value, with respect to a sorted list
    for i in range(0, len(list)):
        if(toIns < list[i]):
            list.insert(i, toIns) # insert the value to the left of the one it DOESNT match
            break # efficiency!
    return list

Почему это работает?Строки можно сравнивать так же, как числа в питоне!A < B, C > B и т. Д.

Если честно: это не самый эффективный вариант, и bisect.insort лучше, но если вам нужен собственный код, которым вы можете управлять, то вы есть.

Сроки:

import timeit

setupStr='''def ins_sorted(toIns, list): # insert a value, with respect to a sorted list
    for i in range(0, len(list)):
        if(toIns < list[i]):
            list.insert(i, toIns) # insert the value to the left of the one it DOESNT match
            break # efficiency!
    return list'''

a = timeit.timeit('ins_sorted("c", ["a", "b", "d", "e"])', number=100000, setup=setupStr)
print(a)

b = timeit.timeit('bisect.insort(["a", "b", "d", "e"], "c")', number=100000, setup='import bisect')
print(b)

Сроки:

0.25098993408028036
0.05763813108205795

Answer 4

Модуль bisect обеспечивает поддержку ведения списка в отсортированном порядке без необходимости сортировки списка после каждой вставки.

bisect.insort_left() метод «вставит элемент в список в отсортированном порядке»:

import bisect

a = ['Alice', 'Amy', 'Andy', 'Betty', 'Eric', 'Peter', 'Richard', 'Tony']
x = 'Beatrice'

bisect.insort_left(a, x)

print(a)

['Alice', 'Amy', 'Andy', 'Beatrice', 'Betty', 'Eric', 'Peter', 'Richard', 'Tony']

Answer 5

Если вы уверены, что у вас есть отсортированный список, вы можете реализовать наивную сортировку вставок

def insertion_sort(lst, newval, key=None):
    """insertion_sort(lst, newval) modifies the pre-sorted lst by inserting
    newval in its sorted order
    """

    if key is None:
        key = type(lst[0]).__lt__

    for i, val = enumerate(lst):
        if key(val, newval):
            continue
        else:
            # newval is less than val, so we insert here
            lst.insert(i, newval)

Или вы можете, менее наивно, использовать stdlib bisectмодуль для вставки для вас.

import bisect

l = ['Alice', 'Amy', 'Andy', 'Betty', 'Eric', 'Peter', 'Richard', 'Tony']
bisect.insort(l, "Andrew")  # or insort_left

Answer 6

Используя двоичное дерево, вставка может быть выполнена в O(height_of_tree):

class Tree:
  def __init__(self, value = None):
    self.right, self.left, self.value = None, None, value
  def __lt__(self, _node):
    return self.value < getattr(_node, 'value', _node)
  def insert_val(self, _val):
    if self.value is None:
      self.value = _val
    else:
      if _val < self.value:
         if self.left is None:
           self.left = Tree(_val)
         else:
           self.left.insert_val(_val)
      else:
          if self.right is None:
            self.right = Tree(_val)
          else:
            self.right.insert_val(_val)
  def flatten(self):
     return [*getattr(self.left, 'flatten', lambda :[])(), self.value, *getattr(self.right, 'flatten', lambda :[])()]

t = Tree()
l = ['Alice', 'Amy', 'Andy', 'Betty', 'Eric', 'Peter', 'Richard', 'Tony']
for i in l:
  t.insert_val(l)

t.insert_val('Beatrice')
print(t.flatten())

Вывод:

['Alice', 'Amy', 'Andy', 'Beatrice', 'Betty', 'Eric', 'Peter', 'Richard', 'Tony']

---

С помощью связанного списка вы можете выполнитьadd и insert операций в одном методе с применением дополнительной логики:

class LinkedList:
  def __init__(self, value=None):
    self.value = value
    self._next = None
  def __lt__(self, _node):
    return True if self._next is None else _node[0] > self._next.value[0]
  def insert_val(self, _val):
    if self.value is None:
      self.value = _val
    else:
      if self._next is None or self._next < _val:
         getattr(self._next, 'insert_val', lambda x:setattr(self, '_next', LinkedList(x)))(_val)
      else:
          _temp_next = self._next._next
          self._next._next = LinkedList(_val)
          self._next._next._next = _temp_next
  def flatten(self):
     return [self.value, *getattr(self._next, 'flatten', lambda :[])()]
  @classmethod
  def load_list(cls):
    _l = cls()
    for i in ['Alice', 'Amy', 'Andy', 'Betty', 'Eric', 'Peter', 'Richard', 'Tony']:
       _l.insert_val(i)
    return _l

l = LinkedList.load_list()
print(l.flatten())
>>>['Alice', 'Amy', 'Andy', 'Betty', 'Eric', 'Peter', 'Richard', 'Tony']
l.insert_val('Beatrice')
print(l.flatten())
>>>['Alice', 'Amy', 'Andy', 'Beatrice', 'Betty', 'Eric', 'Peter', 'Richard', 'Tony']

Answer 7

Вы можете использовать специализированную библиотеку, такую ​​как sortedcontainers, которая более эффективна, чем наивная list.sort после каждой вставки.Сложность SortedList.add составляет ~ O (log n ).

from sortedcontainers import SortedList

lst = SortedList(['Alice', 'Amy', 'Andy', 'Betty', 'Eric', 'Peter', 'Richard', 'Tony'])

lst.add('Beatrice')

print(lst)

SortedList(['Alice', 'Amy', 'Andy', 'Beatrice', 'Betty', 'Eric', 'Peter', 'Richard', 'Tony'])

Answer 8

Попробуйте это:

>>> l = ['Alice', 'Amy', 'Andy', 'Betty', 'Eric', 'Peter', 'Richard', 'Tony']
>>> l.append('Beatrice')
>>> l.sort()
>>> l
['Alice', 'Amy', 'Andy', 'Beatrice', 'Betty', 'Eric', 'Peter', 'Richard', 'Tony']
>>>