StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The difference is in algorithms complexities. Your algorithm, if I am not mistaken, is <strong>O(m^2*n)</strong> where <strong>n</strong> is the length of the inner list and <strong>m</strong> is the number inner lists in the input list. This is because your function effectively traverses the entire list of the inner lists to produce one element of the resulting list. So for your test example the run-time is proportional to <strong>C1*N^3</strong> (where C1 is some constant < 1 in this case).</p> <p>However, normally merging operation of pre-sorted lists has a complexity of <strong>O(n)</strong> where <strong>n</strong> is the total length of all lists. Hence for your test case the complexity should be <strong>O(n*m)</strong> i.e. it should be proportional to <strong>C2*N^2</strong>.</p> <p>And indeed as you can see when the <strong>N</strong> in your tests is increased 10 times it takes 860 times more time for your implementation to produce the result while 'lists:merge/1' needs only 53 times more time to merge the input. The ratios will differ depending on the actual input size and "shape" but the general trend is still N^3 vs N^2.</p> <p>The standard 'lists:merge/1' is not that straightforward: <a href="https://github.com/erlang/otp/blob/maint/lib/stdlib/src/lists.erl#L1441" rel="nofollow">https://github.com/erlang/otp/blob/maint/lib/stdlib/src/lists.erl#L1441</a> ('merge/1' just calls 'mergel/1') but in fact even a simple, not optimised, not tail-recursive "just merge the head list with merged tail" performs much better than your implementation:</p> <pre><code>merge2([]) -> []; merge2([Ls|Lss]) -> merge2(Ls,merge2(Lss), []). merge2([], Ls, Acc) -> lists:reverse(Acc) ++ Ls; merge2(Ls, [], Acc) -> lists:reverse(Acc) ++ Ls; merge2([H1|Ls1], [H2|_] = Ls2, Acc) when H1 =< H2 -> merge2(Ls1, Ls2, [H1|Acc]); merge2(Ls1, [H2|Ls2], Acc) -> merge2(Ls1, Ls2, [H2|Acc]). </code></pre> <p>So once again, as it is often the case in practise: the first step in any optimisation is to look at the algorithm.</p> <p><strong>UPD:</strong> Well, my example is in fact also <strong>O(m^2*n)</strong> - not better then yours in terms of complexity. What we probably need here is "divide and conquer" approach which should improve the compexity to <strong>O(m*n*ln(n))</strong></p> <p><strong>UPD2:</strong> Correction and clarification of the previous update: By "divide and conquer" I mean the following algorithm:</p> <p>Let say we have <strong>m</strong> sorted lists in our input list each consisted of <strong>n</strong> elements. Then:</p> <ol> <li>Split input list into two sublists with <strong>m/2</strong> lists in each</li> <li>Apply this algorithm recursively on each of them.</li> <li>Merge two resulting sorted lists using standard 2-list merge.</li> </ol> <p>The asymptotic complexity of this algorithms is actually <strong>O(n*m*ln(m))</strong> because: 1. Split operation is <strong>O(m)</strong> on every split-level so it can be ignored. 2. Merge operation is <strong>O(m*n)</strong> on every level: on the upper (first split) level we need to merge two lists each of <strong>n*m/2</strong> elements which has <strong>O(n*m)</strong>; on the next level (second split) we need to do two independent merges each merging two lists of <strong>n*m/4</strong> elements which is also <strong>O(m*n)</strong> and so on until <strong>m=2</strong> or <strong>m=1</strong> 3. The number of levels is obviously <strong>log2(m)</strong> so the resulting complexity is <strong>O(n*m*ln(m))</strong></p> <p>In fact this algorithm can be considered just a variant of <a href="http://en.wikipedia.org/wiki/Merge_sort" rel="nofollow">merge sort</a> that "stops" splitting slightly earlier (hence it has <strong>ln(m)</strong> not <strong>ln(m*n)</strong>) and it becomes the full-blown merge sort when <strong>n=1</strong> (while your first algorithm effectively becomes <a href="http://en.wikipedia.org/wiki/Selection_sort" rel="nofollow">selection sort</a>)</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