如何在 python 的列表中插入单词?

我有一个列表。

我需要在列表中添加一个单词，但我不确定该怎么做。

例如

我有一个列表 =['Alice', 'Amy', 'Andy', 'Betty', 'Eric', 'Peter', 'Richard', 'Tony']

您可以使用诸如sortedcontainers这样的专业库，这比每次插入后的幼稚list.sort更有效。SortedList.add的复杂度为 ~O(logn(。

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'])

如果您确定您有一个排序列表，则可以实现朴素插入排序

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)

或者，您可以不那么天真地使用 stdlibbisect模块为您插入。

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

首先，要"检查两个字符串之间的匹配字母"，您真正需要的只是<。字符串按字典顺序比较：'abc' < 'abd' < 'acd' < 'acdd'。

使用链表，您必须从头部搜索节点才能找到位置。随时跟踪上一个节点和下一个节点，一旦找到next.head > value，在prev之后插入新节点。(如果使用裸节点实现，请确保函数返回 head，否则无法在 head 之前插入。

当然，这自动意味着找到正确位置的线性时间(如果你使用不可变节点，还有线性时间将新节点构建到头部(。

鉴于您的实现，这可能看起来像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

使用随机访问数据结构(如数组(Pythonlist(，您可以bisect在日志时间中找到正确的位置。但是对于数组，您仍然需要线性时间来执行插入，因为所有后续值都必须向上移动。(尽管这通常是线性的，常量比链接列表搜索快得多。

bisect.insort(lst, value)

最后一件事：如果你连续做大量的插入，那么将它们批处理起来通常更有效。事实上，如果添加的元素数量占列表的相当大的比例，那么仅仅调用extend然后sort实际上可能比insort每个元素更快。

如果你想两全其美，你需要一个更复杂的数据结构：

某种平衡的二叉搜索树(红黑，AVL等(是传统的答案，尽管在实践中往往很慢。
与任何 B 树变体一样，更广泛的搜索树避免了二叉树的大部分性能成本(并允许您使用更高的日志库进行搜索，以启动(。
skiplist 是一个链表，其中有日志 N 个"更高级别"的链表穿过它(或堆叠在它上面(，所以你可以把它一分为二。这个"索引列表"概念还有其他变体。
有多种复杂混合体的Python实现，例如在顶部堆叠了可选的B树变体的deque/rope结构。

流行的实现包括blist.sortedlist、sortedcontainers.SortedList、pybst.AVLTree等。

但实际上，你在Python中找到的几乎任何此类结构的实现都将内置这种行为。所以正确的答案可能就是这样：

lst.add(val)

试试这个：

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

平分模块支持按排序顺序维护列表，而无需必须在每次插入后对列表进行排序。

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']

在原始python中，你可以做：

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

为什么会这样？字符串可以像python中的数字一样进行比较！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

尝试使用平分库：

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

使用二叉树，可以在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']

相关内容

最新更新

热门标签：