Ruslan’s Blog

Sometimes you may need to have nested dictionaries initialized without much hassle.

“Autovivication” comes in handy. What you want to achieve is:

>>> d = dict()
>>> d['q']['w']['r'] = 777

Of course what you’ll get will be:

>>> d['q']['w']['r'] = 777
Traceback (most recent call last):
  File “<stdin>”, line 1, in <module>
KeyError: ‘q’

If you don’t need deeply nested dictionaries defaultdict with dict default factory will do the job:

>>> from collections import defaultdict
>>> d = defaultdict(dict)
>>> d
defaultdict(<type ‘dict’>, {})
>>> d['a']['b'] = 33
>>> d
defaultdict(<type ‘dict’>, {’a': {’b': 33}})
>>> d['a']['b']
33

Here are another ways to have unlimited level of nested dictionaries.
1) Define custom class inheriting from built-in dict:

class default_dict(dict):
    def __missing__(self, key):
        self[key] = value = self.__class__()
        return value

>>> d = default_dict()
>>> d
{}
>>> d['q']['w']['r'] = 777
>>> d
{’q': {’w': {’r': 777}}}
>>> d['q']['w']['r']
777

2) Recursive function + defaultdict:

def make_dict():
    return defaultdict(make_dict)

>>> from collections import defaultdict
>>> d = defaultdict(make_dict)
>>> d
defaultdict(<function make_dict at 0xb7c5295c>, {})
>>> d['q']['w']['r'] = 777
>>> d
defaultdict(<function make_dict at 0xb7c5295c>, {’q': defaultdict(<function make_dict at 0xb7c5295c>, {’w': defaultdict(<function make_dict at 0xb7c5295c>, {’r': 777})})})
>>> d['q']['w']['r']
777

3) And for fun you can use Y Combinator (in short - making anonymous lambda recursive) which is actually as (2) but you don’t have to have recursive function defined:

def Y(g):
    return ((lambda f: f(f))
            (lambda f:
                 g(lambda x: f(f)
                   (x))))

defdict = Y(lambda mk_dict:
                lambda x=None: defaultdict(lambda x=None: mk_dict(x)))

>>> d = defdict()
>>> d
defaultdict(<function <lambda> at 0xb7c52a74>, {})
>>> d['q']['w']['r'] = 777
>>> d
defaultdict(<function <lambda> at 0xb7c52a74>, {’q': defaultdict(<function <lambda> at 0xb7c56c6c>, {’w': defaultdict(<function <lambda> at 0xb7c56a74>, {’r': 777})})})
>>> d['q']['w']['r']
777

Recent Erlang releases (since R12B) have array module included.

Now binary search algorithm can be implemented quite efficiently with functional arrays:

-module(bsa).
-export([binsearch/2]).

binsearch(Arr, Key) ->
    binsearch(Arr, Key, 0, array:size(Arr)).

binsearch(Arr, Key, LowerBound, UpperBound) ->
    Mid = (LowerBound + UpperBound) div 2,
    Item = array:get(Mid, Arr),
    if
        UpperBound < LowerBound -> -1;
        Key < Item ->
            binsearch(Arr, Key, LowerBound, Mid-1);
        Key > Item ->
            binsearch(Arr, Key, Mid+1, UpperBound);
        true ->
            Mid
    end.

Running time for lists based binary search (just for comparison):

56> {Time, Val} = timer:tc(search, binsearch,
56>                        [lists:seq(1, 1000000), 1000000]).
{506513,  1000000}

Running time for array based binary search:

57> f().
ok
58> {Time, Val} = timer:tc(bsa, binsearch,
58>               [array:from_list(lists:seq(1, 1000000)), 1000000]).
{17,  999999}