Laurent Luce

My gut-ballpark was going to be around an order of magnitude, not two. Here's are two naive comparisons (granted, from the late aughts and not a direct comparison but a more general one) that show ~7-8x[0,1]. The overhead of PyStringObject is not trivial[2] (though the implementation details likely have changed between Py2.x and Python 3).

For things like building accumulators a set of data/log parsing rather than data munging (hits per hour or enumerative tasks), I'd imagine (g|n)?awk might hit your 100x since you'd just grab the fd and traverse being IO bound. I'm not sure how awk does it, but if it's just saving an accumulator value (or 10) in a register. Assuming x64-64 treats, say, an r3 fetch analogously to a fetch to ecx (err..rcx now I guess), rather than having to keep a full object in L1 cache, awk has a huge advantage.

---

N.b., if you're benching tasks like this, don't use 'time' and STDOUT and think you're getting real performance numbers. Your bottleneck (terminals can only render $x lines a minute, so the kernel call to write(STDOUT, ....) will be where you choke, not at the language. Also disk fragmentation would be another issue. Put the both the test file and the output file on a RAMdisk.) Cache flush with Something like sync; echo 3 > /proc/sys/vm/drop_caches (on Linux, I forget the BSD way of doing it) then `time benchmark.py /mnt/ramdisk1/file > /mnt/ramdisk2' over multiple runs, under various loads, with different data sets, etc

Another interesting…

These kinds of diagrams are OK for the most basic introduction to data structures, but they're not much help when it comes to creating an efficient implementation. Learning about data structure implementation without using a relatively low-level language that allows pointers seems to be a recipe for confusion.

Hence, one is probably always better off using the built-ins or libraries for any data structure in a higher-level language rather than implementing them from scratch. For example, here's a nice blog post on how Python dicts are implemented using hash tables written in C.

https://www.laurentluce.com/posts/python-dictionary-implementation/

While it's possible to build something like a binary search tree from scratch in Python using classes for nodes and with references instead of pointers, along with recursive algorithms for traversing it, it doesn't seem like that great of an idea to teach students in this manner. If the goal is to really teach students how to do this, C or similar (Rust?) is probably the better option for code examples, and a lot of time would have to be spent on memory management concepts (i.e. have students build their own dynamically allocated stack for the traversal, to avoid blowing through the stack, maybe).

So likely thinking of it in terms of checking a tree based on characters instead of hashes of full words. Which is more viable would likely depend on what kind of memory constraints and dictionary size was being considered. Also very implementation dependent, what's the size of the hashes generated?

Edit: curiosity got me looking at this for Python, with an answer of "it depends, and both have correct aspects" based on Python's implementation [1]. The hashing varies by string length, the lookup is fixed unless there's a collision and probing, probing will be minimized by growing the dictionary as items are added. In any case, better than O(n) but worse than O(1) and with some possible slowdowns during loading unless you can set an expected final size during initialization.

Edit again: since I brought it up, turns out initialization doesn't really matter, resizing is not a speed factor. Relevant discussion starts from https://stackoverflow.com/questions/1298636/how-to-set-initial-size-for-a-dictionary-in-python

[1] http://www.laurentluce.com/posts/python-dictionary-implementation/

It's puzzling that "x is 17" should work but then "1000 + 1 is 1001" doesn't.

The reason is that Python pre-allocates 262 numbers at initialization (-5 to 256) and the allocation uses a different method/structure for bigger numbers.

>>> x = 256
>>> x is 256
True
>>> id(x)
94900419138400
>>> id(256)
94900419138400

>>> x = 257
>>> x is 257
False
>>> id(x)
94900419504344
>>> id(257)
94900419504368

Reference: https://www.laurentluce.com/posts/python-integer-objects-implementation/