First of all, this is not a Python issue. Rather this is an issue of the implementation itself.
I agree with @Gareth Rees . You should always provide a minimally working example of the code. This is true for StackOverflow and especially true for CodeReview. In that respect all we can review is the little snipped you provide under the assumption that the functions you don't provide do certain things.
The first thing that you can cut is the
else: block. It enters iff the last element of
neighbors is in
already_in_set and what it does is it adds the last element of
already_in_set; in other words: nothing. As a side effect you do pop the last element and since you do it in both cases it is better allocated above the
It looks like
search(tree, temp) will return an iterable thing containing all rank 1 neighbors of
temp. If you don't do any caching,
search is incredibly slow! Loosely speaking that's
O(len(dictionary.txt) * max([len(word) for word in dictionary.txt])^2) for the naive implementation and
O(max([len(word) for word in dictionary.txt]) * depth(tree)) for the one given in the blog post you mention.
To make matters worse, you do this for every friend of a word exactly one (since you prune duplicates). So what your running is
O(len(dictionary.txt)*max([friends(word) for word in dictionary.txt])*O(search)) which in the very crudest worst case can be
O(len(dictionary.txt)^4) (!); although this case is only relevant for theoretical considerations.
Here is a list of things you can do:
- Cache the Levenshtein distance of two words; also you don't need the actual value, rather the result of the expression
distance <= 1 so there is room for more optimization. Also this is symmetric:
distance(a,b) = distance(b,a) so you can cache two values for every computation
- Cache the result of
search(tree, temp). Again this is symmetric:
if b in search(tree,a) then a in search(tree,b) so you can cache this result for every element of
search(tree,a) without ever computing them [note that this is reflexive too:
a in search(tree,a)]
- Cache the result of
find defines a group relation on
dictionary.txt; hence if
b in find(a) and
c in find(a) then also:
a in find(b),
a in find(c),
c in find(b),
b in find(c). You can simply cache this number for every element in the network of a.
Doing all these things will reduce worst case performance to
O(O(find)+O(search)+O(distance)) = O(len(dictionary.txt)^2) and should make it substantially faster. You could think of ways to reduce the number of computations needed for
distance potentially reducing the overall complexity, but I didn't think into this further.