确定一个字符串是否在另外两个字符串之间

Question

我有两张单子。第一个是字符串列表。第二个是字符串元组的列表。假设我有第一个列表中的字符串s。我想在第二个列表中找到s按字母顺序排列的所有对。一个具体的例子：

s = "QZ123DEF"

("QZ123ABC", "QZ125ZEQ") # would return as a positive match
("QF12", "QY22") # would not return as a positive match

我想到了一种蛮力方法，即检查第二个列表中所有元组的s是否大于第一个字符串而小于1秒，但我想知道是否有更好的方法。顺便说一下，我使用的是python。在

Answer 1

因此，假设元组中只有两个条目，您可以稍微理解一下：

>>> s = "QZ123DEF"
>>> testList = [("QZ123ABC", "QZ125ZEQ"), ("QF12", "QY22")]
>>> [test[0] <= s <= test[1] for test in testList]
[True, False]

这可以扩展为s的列表，结果存储在dict中：

^{pr2}$

Answer 2

def between((tupa,tupb),val):
    return tupa <= val <= tupb

s = "QZ123DEF"
print filter(lambda tup:between(tup,s),my_list_tuples)

也许。。。但它仍然是“蛮力”

Answer 3

这里有一种使用对分模块的方法，这需要先对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)

输出：

^{pr2}$

---

与随机数据上的暴力方法相比，该方法快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