We can be a lot faster, at the expense of longer code. Reusing Raymond's benchmark and solutions (mine are prefixed with Kelly_):
Timings with string_size=20 and words_size=100000
154 ms ± 3 ms match_sort
31 ms ± 3 ms Kelly_match_sort
291 ms ± 12 ms match_multiset
26 ms ± 0 ms Kelly_match_counts
424 ms ± 15 ms match_perfect_hash
207 ms ± 7 ms Kelly_match_perfect_hash
164 ms ± 9 ms Kelly_match_perfect_hash2
Timings with string_size=5 and words_size=100000
7 ms ± 0 ms match_sort
3 ms ± 0 ms Kelly_match_sort
26 ms ± 0 ms match_multiset
3 ms ± 0 ms Kelly_match_counts
21 ms ± 0 ms match_perfect_hash
10 ms ± 0 ms Kelly_match_perfect_hash
9 ms ± 0 ms Kelly_match_perfect_hash2
My Kelly_match_sort is like Raymond's match_sort, but for each word, I first check whether its count of the search string's most common letter matches. Only if it does, I then also do the sorting check. In the above two benchmarks, this pre-check already rules out about 94% and 86% of the words, respectively.
My Kelly_match_counts is similar to match_multiset in that it compares letter counts. But instead of using Counter(word) to count all letters, I count them individually with word.count(). From most to least common letter in the search string. And as soon as I find a mismatch, I reject the word and move on to the next word. As mentioned above, very often that already happens at the first letter.
My Kelly_match_perfect_hash is like match_perfect_hash, but uses math.prod instead of reduce with mul, and maps letters to primes directly, using a dictionary (instead of going through ord to index a list). And I use map with the dictionary's get method instead of a generator expressions.
The Kelly_match_perfect_hash2 version maps only letters, so it doesn't waste the smallest primes on characters that don't even appear in words.
Full code (Try it online!):
from collections import Counter
from itertools import permutations
from string import ascii_letters as letters
from random import choice
from operator import mul
from time import time
from functools import reduce
from math import prod
from statistics import mean, stdev
def match_sort(string, words):
target = sorted(string)
return sorted(word for word in words if sorted(word) == target)
def match_multiset(string, words):
target = Counter(string)
return sorted(word for word in words if Counter(word) == target)
primes = [2, 3, 5, 7, 11]
primes += [p for p in range(13, 1620) if all(pow(b, p-1, p) == 1 for b in (5, 11))]
anagram_hash = lambda s: reduce(mul, (primes[ord(c)] for c in s))
def match_perfect_hash(string, words):
target = anagram_hash(string)
return sorted(word for word in words if anagram_hash(word) == target)
def Kelly_match_sort(string, words):
if not string:
return [''] * words.count('')
K = max(string, key=string.count)
V = string.count(K)
target = sorted(string)
return sorted(
word for word in words
if word.count(K) == V
if sorted(word) == target
)
def Kelly_match_counts(string, words):
if not string:
return [''] * words.count('')
(K, V), *kvs = Counter(string).most_common()
matches = []
for word in words:
if word.count(K) == V:
for k, v in kvs:
if word.count(k) != v:
break
else:
if len(word) == len(string):
matches.append(word)
matches.sort()
return matches
primes2 = {chr(i): p for i, p in enumerate(primes)}.get
anagram_hash2 = lambda s: prod(map(primes2, s))
def Kelly_match_perfect_hash(string, words):
target = anagram_hash2(string)
return sorted(word for word in words if anagram_hash2(word) == target)
primes3 = dict(zip(letters, primes)).get
anagram_hash3 = lambda s: prod(map(primes3, s))
def Kelly_match_perfect_hash2(string, words):
target = anagram_hash3(string)
return sorted(word for word in words if anagram_hash3(word) == target)
funcs = [
match_sort,
Kelly_match_sort,
match_multiset,
Kelly_match_counts,
match_perfect_hash,
Kelly_match_perfect_hash,
Kelly_match_perfect_hash2,
]
string_size = 20
words_size = 100000
print('Timings with string_size=%d and words_size=%d' % (string_size, words_size))
times = {func: [] for func in funcs}
for _ in range(10):
population = letters[:
string_size+2]
words = set()
for i in range(words_size):
word = ''.join([choice(population) for i in range(string_size)])
words.add(word)
string = word # Arbitrarily search use the last word as the target
for func in funcs:
start = time()
func(string, words)
end = time()
times[func].append(end - start)
for func in funcs:
ts = [t * 1e3 for t in times[func]]
print('%3d ms ± %2d ms ' % (mean(ts), stdev(ts)), func.__name__)
