我有一个字符串列表已经按不区分大小写的顺序排序.我想在列表中插入一个新字符串.一种方法是附加项目,然后对列表进行排序,如下所示：
myList.append('Something')
myList.sort(key=lambda s: s.lower())
但我想知道是否有办法将项目插入正确的位置而不再重新整理整个事物.
我发现了这个问题：Insert an item into a sorted list in Python.它指向Python的bisect模块.但该模块看起来不像是支持不区分大小写.
编辑：我测试了这里列出的几个答案.
>将项目追加到最后并对整个列表进行排序(如原始问题中所提出的)是最慢的.
> Moinuddin Quadri的答案比排序整个列表更快,但由于在列表上的每个项目上运行lower(),它仍然很慢.
> Stefan Pochmann的回答比整个列表排序快了一个数量级.
> Jared Goguen的答案是重复插入的最快速度.但是,它第一次在每个元素上运行lower().
这是一个接听答案的接近电话.最后,我选择了Stefan Pochmann的答案,因为它是一次性插入的最佳选择,访问结果列表不需要访问成员变量.但是,用例会有所不同,因此请务必检查所有答案.
解决方法
这是再次练习二进制搜索的好机会(或者只是复制并粘贴和修改bisect.insort,这就是我所做的)：
def insort_case_insensitive(a,x):
key = x.lower()
lo,hi = 0,len(myList)
while lo < hi:
mid = (lo + hi) // 2
if key < a[mid].lower():
hi = mid
else:
lo = mid + 1
a.insert(lo,x)
演示：
myList = ['a','b','c','d','e']
for x in 'A','B','C','D','E':
insort_case_insensitive(myList,x)
print myList
打印：
['a','A','e','E']
它是O(n),就像追加排序一样,但只是因为最后的a.insert(lo,x).这很简单,用C语言完成,所以速度非常快.二进制搜索当然只需要O(log n)步,因此也非常快.追加排序方式会在所有元素上调用.lower()并对它们进行比较,两者都要慢得多.由于在所有元素上调用.lower(),@ MoinuddinQuadri的第一个解决方案也慢得多.
请参阅我的其他答案进行基准比较.