我有 2 个列表。第一个只是一个字符串列表。第二个是字符串元组列表。假设我有第一个列表中的字符串 s
。我想在第二个列表中找到 s
按字母顺序排列的所有对。一个具体的例子:
s = "QZ123DEF"
("QZ123ABC", "QZ125ZEQ") # would return as a positive match
("QF12", "QY22") # would not return as a positive match
我想到了一种蛮力方法,即检查 s
是否大于第一个字符串且第二个列表中的所有元组是否小于一秒,但我想知道是否有一个更好的办法。顺便说一下,我正在使用 python。
最佳答案
这是使用 bisect 模块的一种方法,这需要首先对 S
进行排序:
import bisect
import pprint
S = ['b', 'd', 'j', 'n', 's']
pairs = [('a', 'c'), ('a', 'e'), ('a', 'z')]
output = {}
for a, b in pairs:
# Here `a_ind` and `b_ind` are the indices where `a` and `b` will fit in
# the list `S`. Using these indices we can find the items from the list that will lie
# under `a` and `b`.
a_ind = bisect.bisect_left(S, a)
b_ind = bisect.bisect_right(S, b)
for x in S[a_ind : b_ind]:
output.setdefault(x, []).append((a, b))
pprint.pprint(output)
输出:
{'b': [('a', 'c'), ('a', 'e'), ('a', 'z')],
'd': [('a', 'e'), ('a', 'z')],
'j': [('a', 'z')],
'n': [('a', 'z')],
's': [('a', 'z')]}
与针对随机数据的蛮力法相比,这要快 2-3 倍:
def solve(S, pairs):
S.sort()
output = {}
for a, b in pairs:
a_ind = bisect.bisect_left(S, a)
b_ind = bisect.bisect_right(S, b)
for x in S[a_ind : b_ind]:
output.setdefault(x, []).append((a, b))
def brute_force(S, pairs):
output = {}
for s in S:
for a, b in pairs:
if a <= s <= b:
output.setdefault(s, []).append((a, b))
def get_word():
return ''.join(random.choice(string.letters))
S = [get_word() for _ in xrange(10000)]
pairs = [sorted((get_word(), get_word())) for _ in xrange(1000)]
时序比较:
In [1]: %timeit brute_force(S, pairs)
1 loops, best of 3: 10.2 s per loop
In [2]: %timeit solve(S, pairs)
1 loops, best of 3: 3.94 s per loop
关于python - 确定一个字符串是否按字母顺序位于其他两个字符串之间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21391864/