More about binary search in Erlang

In my previous post My Erlang binary search I’ve implemented binary search in Python and Erlang as small exercise for myself after reading Half-baked Ideas blog post. Good article pointing to specifics of implementation of that algorithm in Erlang was posted on Erlane’s blog which is in a nutshell: binary search in Erlang implemented on list data structure is less efficient than linear search.

So to grasp why linear search which is O(N) is faster in Erlang then binary search which is in theory O(logN) go and read that article.
In Python list data structure (I’m talking here about CPython) is implemented as mutable and extensible vector of references to objects(we might say array of pointers), here is the excerpt from listobject.h:

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

So Python version works as expected regarding efficiency.  While my goal of implementing binary search algorithm in Erlang was learning Erlang and not particulary developing optimized version of that algorithm or using another one it’s always good to pick new tricks of the trade along the way and for me the issue with my implementation of binary search in Erlang just boils down to: your experience and know your tools (language, os, editor(emacs , etc )

As Aldous Huxly said: “Experience is not what happens to you; it’s what you do with what happens to you.”. So make errors (not many   in your programs, fix them and gain new experience with your new language.

Another post by Erlane team  is good reading describing paradigm shifts when you are newbie and are on your own way to Erlang/OTP wizardry.