New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Add efficient functions to create sets from lists or arrays #4986
Comments
Comment author: @damiendoligez Note: the code looks wrong, nl should probably be something like (i0 + n) / 2. |
Comment author: @alainfrisch Why is it wrong? nl represents the length of the subarray, i0 the index of its first element. |
Comment author: @damiendoligez I don't know what I was thinking when I wrote that. The code looks fine. |
Comment author: @alainfrisch A patch is attached, with also a new List.sort_dedup functions (like List.sort, but removes duplicates). Performance compared to an implementation based on folding Set.add is usually improved in a significant way, especially for long Examples:
|
Comment author: @alainfrisch Commit 13876 on trunk adds List.sort_uniq and Set.of_list. |
Original bug ID: 4986
Reporter: @alainfrisch
Status: resolved (set by @alainfrisch on 2013-07-09T11:02:47Z)
Resolution: open
Priority: normal
Severity: feature
Fixed in version: 4.02.0+dev
Category: ~DO NOT USE (was: OCaml general)
Monitored by: mehdi @hcarty
Bug description
Creating a set from a list or an array is quite common. It could be useful
to add such functions in the Set module.
A trivial implementation is:
let of_array a =
Array.fold_right add a empty
A more efficient implementation is to sort the array first, and then build the balanced tree directly:
(The cases for n=1,2,3 are just extra optimizations.)
When creating sets from arrays of random integers of size 100000,
the optimized version is almost twice as fast as the naive one (ocamlopt, x86).
File attachments
The text was updated successfully, but these errors were encountered: