Just to throw in one more alternative, if you sort your list, you only need to test adjacent items for equality rather than needing a search for each unique item found. You should get O(n log n) rather than O(n^2), since the performance bottleneck is now the sorting rather than the searching for duplicates. Also, since the sort method is built into the list, sorting performance should be very good.
The dictionary version Chris suggests (and the essentially equivalent set-based approach) is doing essentially the same thing in a way, but using hashing rather than ordering to organise the list and spot duplicates. This is *not* O(n) due to the rate of collisions increasing as the hash table fills. If collisions are handled by building a linked list for each hash table entry, the performance overall is still O(n^2) since (for large amounts of data) there is still a linear search on each collision. If collisions are handled by building binary trees, the performance is back to O(n log n). That is, for large enough datasets, the performance of hash tables is basically the performance of the collision handling data structure (ignoring scaling constants). I suspect Python handles collisions using linked lists, since using trees would require that all dictionary keys support ordered comparisons. Using a dictionary or set to eliminate duplicates therefore gives O(n^2) performance. That said, hash tables have very good scaling constants to their performance, so the dictionary technique will be a very good performer in general. And if the lists are reasonably small the performance will often seem like O(n) in practice. The sort-then-filter approach should still be competitive, but of course it requires that the contents of the list can be ordered consistently. An inappropriate hash function can similarly cause problems for the dictionary approach, causing that theoretical O(n^2) performance to become apparent very quickly. This is probably one reason why the cookbook recipe recommends an O(n^2) searching-based approach. -- http://mail.python.org/mailman/listinfo/python-list
