在Python中将项插入到不区分大小写的排序列表中

Question

我有一个字符串列表已经按不区分大小写的顺序排序.我想在列表中插入一个新字符串.一种方法是附加项目,然后对列表进行排序,如下所示:

myList.append('Something')
myList.sort(key=lambda s: s.lower())

但我想知道是否有办法将项目插入正确的位置而不再重新整理整个事物.

我发现了这个问题:在Python中将项目插入到排序列表中.它指向Python的 bisect模块.但该模块看起来不像是支持不区分大小写.

---

编辑:我测试了这里列出的几个答案.

• 将项目追加到最后并对整个列表进行排序(如原始问题中所提出的)是最慢的.
• Moinuddin Quadri的答案比排序整个列表更快,但由于lower()列表上的每个项目都运行,它仍然很慢.
• Stefan Pochmann的答案比整个列表排序快了一个数量级.
• Jared Goguen的回答是重复插入的最快速度.但是,第一次,它运行lower()在每个元素上.

这是一个接听答案的接近电话.最后,我选择了Stefan Pochmann的答案,因为它是一次性插入的最佳选择,访问结果列表不需要访问成员变量.但是,用例会有所不同,因此请务必检查所有答案.

Answer 1

这是再次练习二分搜索的好机会（或者只是 copy&paste&modify 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', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E']

它是 O(n)，就像 append+sort 一样，但只是因为a.insert(lo, x)最后。这非常简单，并且是用 C 语言完成的，所以速度非常快。二分查找当然只需要 O(log n) 步，所以速度也非常快。append+sort 方式会调用.lower()所有元素并比较它们，这两者都慢得多。由于调用.lower()所有元素，@MoinuddinQuadri 的第一个解决方案也慢得多。

有关基准比较，请参阅我的其他答案。