Subscribe: Mostly Maths
http://www.mostlymaths.net/feeds/posts/default
Language: English
Tags:
code  design  documentation  email  fast  find  lists  maybe  mostlymaths  new design  python  reading  side  slightly  started  tree
Rate this Feed

Feed Details and Statistics
Preview: Mostly Maths

# Mostly Maths

## Programming for backyard gardeners, cooking for linux users, drawing for mathematicians. WTF?

Updated: 2018-04-18T13:42:20.372+02:00

A Slightly Better reddit Upvote/Downvote Widget (button)

2018-04-15T22:23:46.877+02:00

A subtitle to this post could be More yak shaving

A few days go I played a bit with a naive implementation of Bloom filters in Python. I wanted to time them against just checking whether a field is in a set/collection. I found something slightly puzzling: it looked like `in` worked too fast for smaller lists. And I wondered: maybe small lists are special internally, and allow for really fast lookups? Maybe they have some internal index? This raised the question: how does `in` find stuff in sequences?

Instead of reading the documentation I delved into the cpython source. Skipping the documentation was a bad idea, since it is not only pretty comprehensive but explains everything... if you know what you are looking for. But a dive into this big pile of C was more fun. I was also stupid enough to not Google the answer until I was editing this post... This excellent Stack Overflow answer covers more or less what I explain here.

The `in` keyword (defined here) is actually a shorthand for running `__contains__` from the target object, you probably know this already. Your class will be able to provide `in` if you add this magic method, you can read about this in the first chapter of Fluent Python. But tracing this inside `cpython` is a bit cumbersome and got me diving into interesting pieces of the code. By the way, how the Python compiler works is documented here.

First, after we have parsed the code and generated a parse tree from our text, we go to the abstract syntax tree. Converting the string `in` as part of some node of Python source in this tree into an `In` here:

(image)

New Design: I hope you like it

2013-08-19T22:39:13.378+02:00