Ruslan's Blog Ruslan's Blog
Search
Array module in Erlang

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}

arrow3 Responses

  1. Witold Baryluk
    55 mos, 1 wk ago

    Using binsearch for lists isn’t very clever (in fact it is stupid ;) . For lists it is much better to just use linear search. Using binsearch of lists in erlang will lead to O(N^2) algorithm, instand of expected O(log N). Use linear search which is O(N), then compare.

  2. Ruslan Spivak
    55 mos, 1 wk ago

    Hi Witold,

    I’m not encouraging to use binsearch for lists in Erlang, that was just my experiment :)

    Actually I wrote about the fact that linear search is faster for lists in Erlang than binsearch:
    http://ruslanspivak.com/2007/08/17/more-about-binary-search-in-erlang/

  3. Witold Baryluk
    49 mos, 1 wk ago

    This topic is quite old. But you my find the random access lists a interesting topic. I implemented them in Erlang and have O(1) cons, head, tail operations, and log(n) for accessing any element. Yep! :)

    http://github.com/baryluk/ral

Leave A Comment