8 ms·
Counting Things in Python: A History
- mturmon 11y agoWhat a beautiful, understated piece of writing. This particular problem seems to come up a lot when thinking about how to use new Python classes (defaultdict, Counter) and affordances (list comprehensions, +=). It's nice to see it captured in timeline format.
- twblalock 11y agoThe try block method would be considered bad in most languages, and I hope it is considered bad in Python as well. Using exception handling as part of a normal flow of control is bad style, bad taste, and bad for performance. EDIT: I'm glad to see the Python documentation addresses this: https://docs.python.org/2/faq/design.html#how-fast-are-exceptions https://docs.python.org/2/faq/design.html#how-fast-are-excep...
- yeukhon 11y agoI would rephrase it. The try-block method in this example is not useful. There is only one exception we care about and that's 404 with key.
- jerf 11y agoEssentially, in CPython, you're already paying for an exception check on either a lot of the opcodes or all of them, so you might as well use it. Statements are very rich in Python, so generally to get the best CPython performance the name of the game is to get as much out of each one as you can, and minimize the total number of them. (I have to specify CPython because PyPy can be much more complicated.) Certainly nowadays that would be in bad style, but, back in 1.5 it wouldn't have been so bad. Also, when 1.5 was out, 200MHz was still a pretty decent machine! The little things could matter quite a lot.
- jfb 11y agoExceptions in python have historically been very cheap.
- dalke 11y agoThat's not true. There was a paper at the 1997 Python conference on this topic titled "Standard Class Exceptions in Python". A copy is at https://web.archive.org/web/20030610173145/http://barry.warsaw.us/papers/ecshort.pdf https://web.archive.org/web/20030610173145/http://barry.wars... . It evaluated the performance of try/except vs. has_key and concluded: > This indicates that the has_key() idiom is usually the best one to choose, both because it is usually faster than the exception idiom, and because its costs are less variable. The take-home lesson is that actually raising an exception in Python 1.5 was about 10x more expensive than a function call, but the try/except block when there is no exception was not expensive.
- jfb 11y agoInteresting. My information was not only out of date; it was also wrong. The dangers of cargo-culting, although in my case, more theoretical than real, as I never had performance-sensitive python code in production.
- deleted 11y ago[deleted]
- deleted 11y ago[deleted]
- deleted 11y ago[deleted]
- odonnellryan 11y agoIt really depends. Usually, you would do something like this in Python: def whatever(some_string): try: return some_string.split() except AttributeError: return some_other_parsing_stuff(some_string) Instead of checking the type of some_string, or seeing if it has the method split. Reason is: it's more straight forward, and it instantly tells the reader this function is meant to handle strings, and it will split them. If it gets a not-string for some reason, oh well, it'll still handle it. You would check for values in a circumstance like this: def dict_breaker(some_dict): if 'items' in some_dict: return parse_some_items(some_dict['items'])
- dbaupp 11y agoThe latter isn't actually the typical Python style. As the article discusses, Python generally prefers "EAFP"[1] to "LBYL"[2], e.g. def dict_breaker(some_dict): try: return parse_some_items(some_dict['items']) except KeyError: pass Or even def dict_breaker(some_dict): try: items = some_dict['items'] except KeyError: pass else: return parse_some_items(items) These versions may be more efficient (only have to do one hash and interaction with the hashmap, but this probably won't be visible with integers/short strings), and don't suffer from race conditions in concurrent code with the hashmap being modified between the check and the use (yes, this can occur even with GIL). [1]: https://docs.python.org/2/glossary.html#term-eafp https://docs.python.org/2/glossary.html#term-eafp [2]: https://docs.python.org/2/glossary.html#term-lbyl https://docs.python.org/2/glossary.html#term-lbyl
- kornish 11y agoIs there a reason you chose to `pass` instead of the more explicit `return None`? The former seems like it would be less idiomatic since its return value is not explicitly stated.
- dbaupp 11y agoTo emulate the parent exactly e.g. maybe it is just the prefix of the "dict_breaker" function and other things happen later if the key can't be found.
- pvg 11y agoIt's not considered quite that bad. In many languages, using exceptions for non-exceptional flow control is bad style. Python is a bit more ambivalent about this, for instance take a look at the iterator protocol which uses an exception to signal the iterator is done. https://docs.python.org/2/library/stdtypes.html#iterator-types https://docs.python.org/2/library/stdtypes.html#iterator-typ...
- nathancahill 11y agoThat turned out to be not that great of an idea, and it's changed in Python 3.5: https://www.python.org/dev/peps/pep-0479/ https://www.python.org/dev/peps/pep-0479/
- dalke 11y agoThat's not a change to the iterator protocol. It's a change to 'StopIteration handling inside generators'. The following will still raise a StopIteration in Python 3.5+: >>> next(iter([]))
- pvg 11y agoYep, the fundamental termination mechanism seems to be the same. Years and years ago I got into some silly irc nerdgument with a python expert (I think one of the twisted people) about the ugliness of this design and for a moment I thought I got to triumphantly yell 'Told you so!' a decade later. Alas, not the case.
- dalke 11y agoI take it you prefer the explicit test for the end of iteration? As an historic note, the StopIteration form grew out of the earlier iterator form, which called __getitem__ with successive integers until there was an IndexError. That may explain a bias towards an exception-based approach.
- pvg 11y ago
- qewrffewqwfqew 11y ago> Per the Zen of Python, “there should be one– and preferably only one– obvious way to do it”. This is an aspirational message. "aspirational" is an optimistic way to describe it. As the article illustrates, every ~2 years the "pythonic" approach is different. Innovation is good, but it hurts re-use of code and of skills.
- mgraczyk 11y agoWorth noting that Counter itself uses what the article calls get Method, but with a common performance optimization (caching a bound method). def _count_elements(mapping, iterable): mapping_get = mapping.get for elem in iterable: mapping[elem] = mapping_get(elem, 0) + 1
- raymondh 11y agoAlso worth noting that those lines are immediately followed by: try: # Load C helper function if available from _collections import _count_elements except ImportError: pass
- mkj 11y agoI was expecting a larger difference in times, about 3.5x is the largest spread. https://gist.github.com/treyhunner/0987601f960a5617a1be https://gist.github.com/treyhunner/0987601f960a5617a1be Nice article.
- kazinator 11y ago$ txr This is the TXR Lisp interactive listener of TXR 123. Use the :quit command or type Ctrl-D on empty line to exit. 1> [hash-update [group-by identity '(brown red green yellow yellow brown brown black)] length] #H(() (green 1) (red 1) (brown 3) (black 1) (yellow 2)) Form a hash by grouping like items into lists. The identity function is the key in the hash and the basis for equality, so the keys are colors, and the values are lists of colors. Then update the hash values by filtering through the length function.
- jlarocco 11y agoI guess this is off topic, but neat language. But that algorithm allocates a bunch of intermediate lists and iterates through the hash table when it doesn't need to. Here it is in common lisp: (defun count-elements (lst) (loop with rval = (make-hash-table) for val in lst do (incf (gethash val rval 0)) finally (return rval)))
- kazinator 11y agoIt's better (by default) to optimize for programmer time and succinct expression unless something else takes priority, like running time, memory use, image size, etc. The TXR version of the iterative approach: 1> (let ((h (hash))) (each ((c '(brown red green yellow yellow brown brown black))) (inc [h c 0])) ;; (inc (gethash c h 0)) can be used h) #H(() (black 1) (yellow 2) (green 1) (red 1) (brown 3)) Or: 2> (let ((h (hash))) (mapdo (do inc [h @1 0]) '(brown red green yellow yellow brown brown black)) h) #H(() (black 1) (yellow 2) (green 1) (red 1) (brown 3)) I toyed with porting some loop macro implementation to TXR Lisp. I looked at some historic sources and just went "gack". Followed by, "what am I thinking". I think in the end I would go for something like iterate, but even more Lispy. (Iterate still has "for x in y" type syntax in the clauses, just with parentheses around it; I would drop the infix "in" cruft and just have a symbol followed by nothing but semantic arguments)
- reikonomusha 11y agoPedantry: this won't work with strings if they're not EQL.
- mmytest 11y agovery cool
- d0mine 11y agocollections.Counter() was the slowest option according to the benchmark from 2010 http://stackoverflow.com/questions/2522152/python-is-a-dictionary-slow-to-find-frequency-of-each-character http://stackoverflow.com/questions/2522152/python-is-a-dicti...
- schmidtc 11y agojust for fun... import itertools colors = ["brown", "red", "green", "yellow", "yellow", "brown", "brown", "black"] dict([(color, len(list(grp))) for color, grp in itertools.groupby(sorted(colors))]) or dict([(color, len(filter(lambda c: c==color, colors))) for color in set(colors)]) ...because sometimes job security is important too.
- aldanor 11y agoOr this (not efficient but fun, and using a dict comprehension and no itertools): {a: sum(a == b for b in colors) for a in set(colors)}
- houselync 11y agoI like History Thank for history information!!!
- buzzdenver 11y agoThis makes me appreciate autovivification and casting in perl so that you can just say "$color_counts{$color} += 1" without all the initialization.
- collyw 11y agoI miss that in Perl a lot.
- jboggan 11y agoYes! This was one of the biggest things I missed when I moved to Ruby. I try and tell people how great autovivification is but unless they've coded with it the feature just sounds strange. But it lets you build some really great data structures on the fly!
- kbenson 11y agoI love it as well, and would hate to do without it, but it does come with it's own warts. Such as this: use Data::Dumper; my %h; if ( $h{foo}{bar}{baz} ) { say "Never happens"; } say Dumper \%h; And you get this: $VAR1 = { 'foo' => { 'bar' => {} } };
- colonelguy 11y agoYou'd want to use the exists operator in that case. It checks if the hash key is present without auto vivifying it. my %hash = (); if (exists $hash{foo}) {print "This doesn't run!";}
- kbenson 11y agoI'm well aware of exists, and how it functions, and that it in no way solves the problem presented. Exists tests for the existence of a hash key, so you can tell if it exists but is possibly undefined, but it does not stop autovivification in any way. Your example doesn't cause autovivification even without exists. Autovivification is the automatic creation of the underlying hashes and arrays in a multiple level data structure when they are used while accessing a nested data-structure. For example, given an empty hash %hash, $hash{foo} does not cause autovivification, but $hash{foo}{bar} will automatically create an empty hash and assign a reference to it to $hash{foo}.
- vog 11y agoThe author seems to misunderstand one part of The Zen of Python: | Simple is better than complex. by saying: > Our code is more complex (O(n2) instead of O(n)), less beautiful, and less readable The Zen is not about computation complexity! It's about complexity of the source code. The code in question is: color_counts = dict((c, colors.count(c)) for c in set(colors)) And while I agree that this is inefficient and shouldn't be used in a library, I find this to be very readable and would always prefer that code if I know that I'm dealing only with small lists. It translates neatly to a natural-language description of the problem: Give me a dictionary that maps each distinct color to the number of times it occurs in the list. So I don't think this violates the guide "Simple is better than complex". Rather, it is a good example where it makes sense to introduce additional complexity to improve the performance of an often-used helper function.
- adrianN 11y agoI don't think you should get into the habit of writing O(n^2) algorithms if the O(n) solution is not much more complex. Unless the constants are very dissimilar, you probably hurt your performance already for a few hundred elements. Writing reusable code includes using algorithms that are ok for a wide range of input sizes.
- deleted 11y ago[deleted]
- deleted 11y ago[deleted]
- SZJX 11y agoI have no idea how the author found this code more complex. Probably he's still more used to imperative programming, but functional programming styles and one liners will mostly greatly simply the understanding of the code.
- esfandia 11y agoWould be interesting doing the same exercise for Java as well. We've been through Hashtable, HashMap, basic for loops, Enumeration, Iterator, foreach loops, generics, and now we have lambdas.
- dec0dedab0de 11y agoI thought this was going to end around 2.4 with the .count(c) method, since you don't really need the dict at that point.
- kendallchuang 11y agoGreat blog post Trey!