StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Of course you can easily write this as a list comprehension:</p> <pre><code>[(a, b) for a in A for b in B if a in b] </code></pre> <p>This might slightly speed up the loop, but don't expect too much. I doubt using regular expressions will help in any way with this one.</p> <p><strong>Edit</strong>: Here are some timings:</p> <pre><code>import itertools import timeit import re import collections with open("/usr/share/dict/british-english") as f: A = [s.strip() for s in itertools.islice(f, 28000, 30000)] B = [s.strip() for s in itertools.islice(f, 23000, 25000)] def f(): result = [] for a in A: for b in B: if a in b: result.append((a, b)) return result def g(): return [(a, b) for a in A for b in B if a in b] def h(): res = [re.compile(re.escape(a)) for a in A] return [(a, b) for a in res for b in B if a.search(b)] def ninjagecko(): d = collections.defaultdict(set) for k, b in enumerate(B): for i, j in itertools.combinations(range(len(b) + 1), 2): d[b[i:j]].add(k) return [(a, B[k]) for a in A for k in d[a]] print "Nested loop", timeit.repeat(f, number=1) print "List comprehension", timeit.repeat(g, number=1) print "Regular expressions", timeit.repeat(h, number=1) print "ninjagecko", timeit.repeat(ninjagecko, number=1) </code></pre> <p>Results:</p> <pre><code>Nested loop [0.3641810417175293, 0.36279606819152832, 0.36295199394226074] List comprehension [0.362030029296875, 0.36148500442504883, 0.36158299446105957] Regular expressions [1.6498990058898926, 1.6494300365447998, 1.6480278968811035] ninjagecko [0.06402897834777832, 0.063711881637573242, 0.06389307975769043] </code></pre> <p><strong>Edit 2:</strong> Added a variant of the <a href="https://stackoverflow.com/q/8289119/279627">alogrithm suggested by ninjagecko</a> to the timings. You can see it is much better than all the brute force approaches.</p> <p><strong>Edit 3:</strong> Used sets instead of lists to eliminate the duplicates. (I did not update the timings -- they remained essentially unchanged.)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload