Databases
StackOverflow2013
Postsdbo
POMerge list of lists from scratch
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POMerge list of lists from scratch
    text
    copied!<p>I needed to merge sorted lists into one list (number of lists may vary). As I new to Erlang - I didn't know about pretty function <code>lists:merge/1</code>. So I implemented own <code>merge/1</code> function. It's complexity is O(m*n) (m - number of lists, n - average number of elements in list), and I use tail recursion. Here is my function:</p> <pre><code>-module( merge ). -export( [ merge/1 ] ). merge( ListOfLists ) -&gt; merge( ListOfLists, [] ). merge( [], Merged ) -&gt; lists:reverse( Merged ); merge( ListOfLists, Merged ) -&gt; [ [ Hfirst | Tfirst ] | ListOfLists_Tail ] = ListOfLists, % let's find list, which has minimal value of head % result would be a tuple { ListWithMinimalHead, Remainder_ListOfLists } { [ Hmin | Tmin ], ListOfLists_WithoutMinimalHead } = lists:foldl( fun( [ Hi | Ti ] = IncomingList, { [ Hmin | Tmin ], Acc } ) -&gt; case Hi &lt; Hmin of true -&gt; % if incoming list has less value of head then swap it { [ Hi | Ti ], [ [ Hmin | Tmin ] | Acc ] }; false -&gt; { [ Hmin | Tmin ], [ IncomingList | Acc ] } end end, { [ Hfirst | Tfirst ], [] }, ListOfLists_Tail ), % add minimal-valued head to accumulator, and go to next iteration case Tmin == [] of true -&gt; merge( ListOfLists_WithoutMinimalHead, [ Hmin | Merged ] ); false -&gt; merge( [ Tmin | ListOfLists_WithoutMinimalHead ], [ Hmin | Merged ] ) end. </code></pre> <p>But, after I knew about <code>lists:merge/1</code> - I decided to test performance of my solution.</p> <p>Here is some results:</p> <pre><code>1&gt; c(merge). {ok,merge} 2&gt; 2&gt; 3&gt; timer:tc( lists, merge, [ [ lists:seq(1,N) || N &lt;- lists:seq(1,5) ] ] ). {5,[1,1,1,1,1,2,2,2,2,3,3,3,4,4,5]} 3&gt; 3&gt; timer:tc( merge, merge, [ [ lists:seq(1,N) || N &lt;- lists:seq(1,5) ] ] ). {564,[1,1,1,1,1,2,2,2,2,3,3,3,4,4,5]} 4&gt; 4&gt; 4&gt; timer:tc( lists, merge, [ [ lists:seq(1,N) || N &lt;- lists:seq(1,100) ] ] ). {2559, [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1|...]} 5&gt; 5&gt; timer:tc( merge, merge, [ [ lists:seq(1,N) || N &lt;- lists:seq(1,100) ] ] ). {25186, [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1|...]} 6&gt; 6&gt; 6&gt; timer:tc( lists, merge, [ [ lists:seq(1,N) || N &lt;- lists:seq(1,1000) ] ] ). {153283, [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1|...]} 7&gt; 7&gt; timer:tc( merge, merge, [ [ lists:seq(1,N) || N &lt;- lists:seq(1,1000) ] ] ). {21676268, [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1|...]} 8&gt; </code></pre> <p>I've been impressed by <strong>0.153 sec. vs 21.676 sec.</strong> My function works extremly slow.</p> <p>I thought that using of anonymous function slow down performance, but getting rid of <code>fun</code> doesn't helped.</p> <p>Could you point me, where I did principal mistake? Or why function from module lists so much faster?</p> <p>Thanks</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload