erikrose/more-itertools — pull request #20 by abarnert (2012-11-22 01:03:04+00:00)
Title: Make unique_everseen work with unhashable values

For sequences with unhashable values, fall back to a list instead of a set for caching seen values.

This means the worst case is now O(N^2) instead of O(N). However, any case that would take longer than O(N) would have failed with the original version.

Of course in some use cases, failing rather than silently taking longer is a good thing, but that's probably not typical for uses of this function.

For sequences that work with the original version, there is a tiny performance overhead caused by having to put each `if element in seen:` check inside a try block, but it's under 1%.

The change also requires switching from `for element in ifilterfalse(seen.__contains__, iterable):` to `for element in iterable: if element in seen:`, but that turned out to be faster in Py3 anyway (enough so to outweigh the cost of the try block).

Because sequences can be a mix of hashable and unhashable, test each one, instead of switching to the list on the first unhashable value. This slightly increases the overhead for the all- or mostly-unhashable cases (about 5% in 3.3, 9% in 2.7), but it dramatically improves the performance of mostly-hashable cases.

I also did some testing with a three-cache version, using a sorted sequence for values that are orderable but not hashable, but decided that wasn't worth including in general purpose code.

See the thread beginning at http://mail.python.org/pipermail/python-ideas/2012-November/017881.html for more info.