Timeline for Implementing a function which generalizes the merging step in merge sort
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 17, 2012 at 12:15 | comment | added | Leonid Shifrin |
You can easily cure your solution by passing just the starting positions from where to read the lists, and using Do loops instead of LengthWhile to read elements - so that you will never copy lists but always read from the same lista and listb. One other thing though would be to make the function tail-recursive, but I think this is also doable, given that it anyway works by side-effects.
|
|
| Jun 17, 2012 at 12:08 | comment | added | Heike | @LeonidShifrin I didn't take it that way. I was a bit surprised by the speed myself so I suspected that there was catch somewhere anyway. | |
| Jun 17, 2012 at 11:36 | comment | added | Leonid Shifrin | Heike, I did not have a motivation to kill your code, really. I just could not understand why it worked so fast on the rather large data I tried. Also, make sure you don't have anything worth saving in the session when trying my test code from the previous comment - it eats up my 8Gb of RAM very quickly and then quits the kernel. | |
| Jun 17, 2012 at 11:35 | comment | added | Leonid Shifrin |
Ok, I got it. Statistically, the purely random data is such that very soon you get the number close to a maximal, so your function does not perform many recursive steps. This will be a killer though: ls1 = Flatten[RandomSample /@ Partition[Range[100000], 5]]; ls2 = Flatten[RandomSample /@ Partition[Range[100000], 5]];Block[{$RecursionLimit = Infinity}, mergeLists[ls1, ls2, Less]]; // AbsoluteTiming (Note that you have to lift the $RecursionLimit in general - which was another thing I initially did not understand - how could you avoid that with your function not being tail-recursive).
|
|
| Jun 17, 2012 at 11:24 | comment | added | Leonid Shifrin |
Actually, your code is remarkably fast, I can only beat it when I enable the compilation to C, and it is more compact, since what I do explicitly with type-identification and Dispatch, is done implicitly by LengthWhile here. I was initially suspecting that your version might be slower because typically rule-based varsions not using linked lists are slow due to excessive copying of elements. But in your case, for some reason which I don't yet understand this only becomes noticable for truly huge lists, and is not dominating the running time in any case. Will have to think more about it.
|
|
| Jun 17, 2012 at 10:10 | history | answered | Heike | CC BY-SA 3.0 |