将项目插入 Python 中不区分大小写的排序列表
Insert item into case-insensitive sorted list in Python
我有一个已按不区分大小写顺序排序的字符串列表。我想在列表中插入一个新字符串。一种方法是附加项目，然后对列表进行排序，如下所示：
myList.append('Something')
myList.sort(key=lambda s: s.lower())
但我想知道是否有一种方法可以将项目插入正确的位置而无需再次对整个项目进行排序。
我发现了这个问题：Insert an item into a sorted list in Python. It points towards Python's bisect 模块。但是那个模块看起来不支持不区分大小写。
编辑：我测试了这里列出的几个答案。
- 将项目附加到末尾并对整个列表进行排序（如原始问题中所建议的那样）是最慢的。
- Moinuddin Quadri 的回答比对整个列表进行排序要快，但仍然很慢，因为列表中的每个项目都 运行
lower()。
- Stefan Pochmann 的回答比对整个列表排序快一个数量级。
- Jared Goguen 的回答是重复插入最快的。但是，第一次，它在每个元素上运行
lower()。
勉强接受一个答案。最后，我接受了 Stefan Pochmann 的回答，因为它是一次性插入的最佳选择，并且访问结果列表不需要访问成员变量。但是，用例各不相同，因此请务必检查所有答案。
您可以在 lower-cased 排序列表中使用 bisect.bisect 作为：
from bisect import bisect
my_list = ["aa", "bb", "Dd", "ee"]
insert_string = "CC"
# convert all the items in list to lower case for
# v finding the correct location via. bisect
index = bisect([i.lower() for i in my_list], insert_string.lower())
# bisect based on lower-cased string for ^
# case-insensitive behavior
my_list.insert(index, insert_string)
my_list 的更新内容将是：
['aa', 'bb', 'CC', 'Dd', 'ee']
我从未使用过 bisect，但这是我的尝试。我直接从您链接的 bisect 页面获取的第一个函数：
def index(a, x):
'Locate the leftmost value exactly equal to x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
def insert_into_sorted(char, my_list):
marker = chr(ord(char) + 1)
spot = index(my_list, marker)
my_list[spot:spot] = char
return my_list
x = ['a', 'b', 'd', 'e']
insert_into_sorted('c', x)
>>['a', 'b', 'c', 'd', 'e']
根据 OP 的评论，因为可以维护中间列表来保存 lower-cased 个字符串 （一次性操作）；它可以实现为：
from bisect import bisect
my_list = ["aa", "bb", "Dd", "ee"]
lower_list = [i.lower() for i in my_list] # list of lower-cased strings.
# one time operation
insert_string = "CC" # word to insert
# find index based on lower-cased list
index = bisect(lower_list, insert_string.lower())
my_list.insert(index, insert_string) # insert word in original list
lower_list.insert(index, insert_string.lower()) # insert lower-cased word
# in lower-cased list
my_list 的最终值将是 lower_list 将是：
>>> my_list # original list
['aa', 'bb', 'CC', 'Dd', 'ee']
>>> lower_list
['aa', 'bb', 'cc', 'dd', 'ee']
这里我们将 lower-cased 个单词的列表一分为二以找到索引并根据索引将字符串插入到原始列表中。
又是练习二分查找的好机会（或者只是复制&粘贴&修改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)。这是 dead-simple 并且是用 C 语言完成的，所以速度非常快。二分查找当然只需要 O(log n) 步，所以速度也非常快。 append+sort 方式会在所有元素上调用 .lower() 并比较它们，这两种方式都慢得多。 @MoinuddinQuadri 的第一个解决方案也慢得多，因为在所有元素上调用 .lower()。
查看我的其他答案以进行基准比较。
您可以创建自己的类型来封装此行为（按照另一个答案中的建议与 bisect 结合）。
from bisect import bisect
class CaseInsensitiveSortedList:
def __init__(self, iterable):
self.with_case = list(sorted(iterable, key=lambda s: s.lower()))
self.without_case = [s.lower() for s in self.with_case]
def insert_in_order(self, s):
s_lower = s.lower()
index = bisect(self.without_case, s_lower)
self.without_case.insert(index, s_lower)
self.with_case.insert(index, s)
test_list = CaseInsensitiveSortedList(['a', 'B', 'cd', 'E', 'fff'])
test_list.insert_in_order('D')
print(test_list.with_case) # ['a', 'B', 'cd', 'D', 'E', 'fff']
test_list.insert_in_order('ee')
print(test_list.with_case) # ['a', 'B', 'cd', 'D', 'E', 'ee', 'fff']
您可以直接扩展 list 并使它变得稍微 "more natural" 或者用它做任何您想做的事情。这只是一个避免在每个插入的每个元素上调用 str.lower 的想法。
我看到你在问题中添加了测试结果。我现在也做了一些基准测试并得到了类似的图片：
Insorting 20000 words:
80.224 seconds with insort_sorting
0.166 seconds with insort_own_binary_search
70.294 seconds with insort_lower_all
0.094 seconds with insort_keep_lower
不过，你对快二的看法有点不对。随着更多的插入，我的变得更快。大约快两倍：
Insorting 1000000 words:
92.712 seconds with insort_own_binary_search
173.577 seconds with insort_keep_lower
这是因为搜索索引的 O(log n) 时间变得可以忽略不计，而时间主要由 insert 调用的 O(n) 时间决定。而我的解决方案只有其中一个，而另一个解决方案有两个。
另一个区别是 space 复杂性，保留所有字符串的降低版本的额外列表并不好。
这是我的基准测试代码：
import random, string, time
#--------------------------------------------------------------
def insort_sorting(a, x):
a.append(x)
a.sort(key=str.lower)
#--------------------------------------------------------------
def insort_own_binary_search(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)
#--------------------------------------------------------------
from bisect import bisect
def insort_lower_all(a, x):
index = bisect([i.lower() for i in a], x.lower())
a.insert(index, x)
#--------------------------------------------------------------
from bisect import bisect
def insort_keep_lower(a, x, lower=[]):
x_lower = x.lower()
index = bisect(lower, x_lower)
a.insert(index, x)
lower.insert(index, x_lower)
#--------------------------------------------------------------
# Generate random words
words = [''.join(random.choice(string.ascii_letters) for _ in range(10))
for _ in range(20000)]
# for _ in range(1000000)]
# Compare the solutions
print 'Insorting', len(words), 'words:'
reference = None
for insort in insort_sorting, insort_own_binary_search, insort_lower_all, insort_keep_lower:
#for insort in insort_own_binary_search, insort_keep_lower:
t0 = time.time()
myList = []
for word in words:
insort(myList, word)
print '%7.3f seconds with %s' % (time.time() - t0, insort.__name__)
if reference is None:
reference = myList
else:
assert myList == reference
我有一个已按不区分大小写顺序排序的字符串列表。我想在列表中插入一个新字符串。一种方法是附加项目，然后对列表进行排序，如下所示：
myList.append('Something')
myList.sort(key=lambda s: s.lower())
但我想知道是否有一种方法可以将项目插入正确的位置而无需再次对整个项目进行排序。
我发现了这个问题：Insert an item into a sorted list in Python. It points towards Python's bisect 模块。但是那个模块看起来不支持不区分大小写。
编辑：我测试了这里列出的几个答案。
- 将项目附加到末尾并对整个列表进行排序（如原始问题中所建议的那样）是最慢的。
- Moinuddin Quadri 的回答比对整个列表进行排序要快，但仍然很慢，因为列表中的每个项目都 运行
lower()。 - Stefan Pochmann 的回答比对整个列表排序快一个数量级。
- Jared Goguen 的回答是重复插入最快的。但是，第一次，它在每个元素上运行
lower()。
勉强接受一个答案。最后，我接受了 Stefan Pochmann 的回答，因为它是一次性插入的最佳选择，并且访问结果列表不需要访问成员变量。但是，用例各不相同，因此请务必检查所有答案。
您可以在 lower-cased 排序列表中使用 bisect.bisect 作为：
from bisect import bisect
my_list = ["aa", "bb", "Dd", "ee"]
insert_string = "CC"
# convert all the items in list to lower case for
# v finding the correct location via. bisect
index = bisect([i.lower() for i in my_list], insert_string.lower())
# bisect based on lower-cased string for ^
# case-insensitive behavior
my_list.insert(index, insert_string)
my_list 的更新内容将是：
['aa', 'bb', 'CC', 'Dd', 'ee']
我从未使用过 bisect，但这是我的尝试。我直接从您链接的 bisect 页面获取的第一个函数：
def index(a, x):
'Locate the leftmost value exactly equal to x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
def insert_into_sorted(char, my_list):
marker = chr(ord(char) + 1)
spot = index(my_list, marker)
my_list[spot:spot] = char
return my_list
x = ['a', 'b', 'd', 'e']
insert_into_sorted('c', x)
>>['a', 'b', 'c', 'd', 'e']
根据 OP 的评论，因为可以维护中间列表来保存 lower-cased 个字符串 （一次性操作）；它可以实现为：
from bisect import bisect
my_list = ["aa", "bb", "Dd", "ee"]
lower_list = [i.lower() for i in my_list] # list of lower-cased strings.
# one time operation
insert_string = "CC" # word to insert
# find index based on lower-cased list
index = bisect(lower_list, insert_string.lower())
my_list.insert(index, insert_string) # insert word in original list
lower_list.insert(index, insert_string.lower()) # insert lower-cased word
# in lower-cased list
my_list 的最终值将是 lower_list 将是：
>>> my_list # original list
['aa', 'bb', 'CC', 'Dd', 'ee']
>>> lower_list
['aa', 'bb', 'cc', 'dd', 'ee']
这里我们将 lower-cased 个单词的列表一分为二以找到索引并根据索引将字符串插入到原始列表中。
又是练习二分查找的好机会（或者只是复制&粘贴&修改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)。这是 dead-simple 并且是用 C 语言完成的，所以速度非常快。二分查找当然只需要 O(log n) 步，所以速度也非常快。 append+sort 方式会在所有元素上调用 .lower() 并比较它们，这两种方式都慢得多。 @MoinuddinQuadri 的第一个解决方案也慢得多，因为在所有元素上调用 .lower()。
查看我的其他答案以进行基准比较。
您可以创建自己的类型来封装此行为（按照另一个答案中的建议与 bisect 结合）。
from bisect import bisect
class CaseInsensitiveSortedList:
def __init__(self, iterable):
self.with_case = list(sorted(iterable, key=lambda s: s.lower()))
self.without_case = [s.lower() for s in self.with_case]
def insert_in_order(self, s):
s_lower = s.lower()
index = bisect(self.without_case, s_lower)
self.without_case.insert(index, s_lower)
self.with_case.insert(index, s)
test_list = CaseInsensitiveSortedList(['a', 'B', 'cd', 'E', 'fff'])
test_list.insert_in_order('D')
print(test_list.with_case) # ['a', 'B', 'cd', 'D', 'E', 'fff']
test_list.insert_in_order('ee')
print(test_list.with_case) # ['a', 'B', 'cd', 'D', 'E', 'ee', 'fff']
您可以直接扩展 list 并使它变得稍微 "more natural" 或者用它做任何您想做的事情。这只是一个避免在每个插入的每个元素上调用 str.lower 的想法。
我看到你在问题中添加了测试结果。我现在也做了一些基准测试并得到了类似的图片：
Insorting 20000 words:
80.224 seconds with insort_sorting
0.166 seconds with insort_own_binary_search
70.294 seconds with insort_lower_all
0.094 seconds with insort_keep_lower
不过，你对快二的看法有点不对。随着更多的插入，我的变得更快。大约快两倍：
Insorting 1000000 words:
92.712 seconds with insort_own_binary_search
173.577 seconds with insort_keep_lower
这是因为搜索索引的 O(log n) 时间变得可以忽略不计，而时间主要由 insert 调用的 O(n) 时间决定。而我的解决方案只有其中一个，而另一个解决方案有两个。
另一个区别是 space 复杂性，保留所有字符串的降低版本的额外列表并不好。
这是我的基准测试代码：
import random, string, time
#--------------------------------------------------------------
def insort_sorting(a, x):
a.append(x)
a.sort(key=str.lower)
#--------------------------------------------------------------
def insort_own_binary_search(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)
#--------------------------------------------------------------
from bisect import bisect
def insort_lower_all(a, x):
index = bisect([i.lower() for i in a], x.lower())
a.insert(index, x)
#--------------------------------------------------------------
from bisect import bisect
def insort_keep_lower(a, x, lower=[]):
x_lower = x.lower()
index = bisect(lower, x_lower)
a.insert(index, x)
lower.insert(index, x_lower)
#--------------------------------------------------------------
# Generate random words
words = [''.join(random.choice(string.ascii_letters) for _ in range(10))
for _ in range(20000)]
# for _ in range(1000000)]
# Compare the solutions
print 'Insorting', len(words), 'words:'
reference = None
for insort in insort_sorting, insort_own_binary_search, insort_lower_all, insort_keep_lower:
#for insort in insort_own_binary_search, insort_keep_lower:
t0 = time.time()
myList = []
for word in words:
insort(myList, word)
print '%7.3f seconds with %s' % (time.time() - t0, insort.__name__)
if reference is None:
reference = myList
else:
assert myList == reference