Array module in Erlang

by Ruslan Spivak on April 13, 2008

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}
If you enjoyed this post why not subscribe via email or my RSS feed and get the latest updates immediately. You can also follow me on GitHub or Twitter.

{ 3 comments… read them below or add one }

Witold Baryluk April 13, 2010 at 11:15 PM

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.

Reply

Ruslan Spivak April 13, 2010 at 11:34 PM

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/

Reply

Witold Baryluk October 9, 2010 at 5:43 PM

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

Reply

Speak your mind

Previous post:

Next post: