<p>这里有一种使用对分模块的方法,这需要先对<code>S</code>排序:</p>
<pre><code>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)
</code></pre>
<p><strong>输出:</strong></p>
^{pr2}$
<hr/>
<p>与随机数据上的暴力方法相比,该方法快2-3倍:</p>
<pre><code>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)]
</code></pre>
<h3>定时比较:</h3>
<pre><code>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
</code></pre>