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}

This entry was posted on Sunday, April 13th, 2008 at 10:47 pm and is filed under erlang. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “Array module in Erlang”

  1. Witold Baryluk says:
    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

Leave a Reply