David Su added the comment: Here are some tests that I ran:
Using current naive viewkeys intersection: $ python -m timeit -n 100 -s "d = dict.fromkeys(xrange(10000000), 0)" "d.viewkeys() & {0}" 100 loops, best of 3: 447 msec per loop Nearly half a second per iteration is unacceptably slow. Solution 1 from my previous comment: $ python -m timeit -n 100 -s "d = dict.fromkeys(xrange(10000000), 0); s = set(d)" "s & {0}" 100 loops, best of 3: 0.391 usec per loop This solution caches the keys of the dict in a set, then performs all intersections on that set. The initial creation of the set is slow, and it wastes a lot of memory, but each iteration is much faster. The workaround that I ended up using: $ python -m timeit -n 100 -s "d = dict.fromkeys(xrange(10000000), 0)" "{item for item in {0} if item in d}" 100 loops, best of 3: 0.629 usec per loop This solution just looks up each value in the set to see if it is also in the dict using a set comprehension. This avoids wasting time and space on creating a set. For my use case, memory was a bigger issue as my dictionary can approach tens of GBs in size, and almost doubling the memory consumption from creating a cache set was unacceptable. Of course, in the set comprehension, the smaller of the dict/set should be iterated over to satisfy the O(min(len(d), len(s))) condition as specified in https://wiki.python.org/moin/TimeComplexity. A implementation would look something like this: def efficient_intersection(smaller_dict_or_set, bigger_dict_or_set): if len(bigger_dict_or_set) < len(smaller_dict_or_set): bigger_dict_or_set, smaller_dict_or_set = smaller_dict_or_set, bigger_dict_or_set return {item for item in smaller_dict_or_set if item in bigger_dict_or_set} In conclusion, porting over the set intersection logic to viewkeys would be the ideal solution. It avoids wasting memory like in the set cache solution, and I am sure the C implementation will be much faster than my workaround of manually performing an intersection using set comprehensions. My view is that dict.viewkeys() & set(...) should be as performant as the syntax suggests. ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue27575> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com