On 5/7/07, Hugo Ferreira <[EMAIL PROTECTED]> wrote: > Hello, > > Olivier Andrieu wrote: > > On 5/7/07, Hugo Ferreira <[EMAIL PROTECTED]> wrote: > >> > >> Hello, > >> > >> I would like to know if anyone has implemented or knows of a freely > >> available functional implementation of skip-lists (probabilistic or > >> deterministic). I know only of one in [1], but it is not persistent. > > > > hmm do you really absolutely need a skip-list or is it simply that you > > want a list data-structure with fast access to the nth element ? > > Actually, I am looking for fast inserts, deletes ands searches. But I > must also obtain the list of all elements in set and append those to a > list (in reverse order). > > My understanding is that (imperative) Skip lists have the performance of > balanced trees but also allow for iterating over all elements in O(N), > which is what I want (but not necessarily in order).
Balanced trees also allow for iterating over all elements in O(N) ! The advantage of skip lists IMO is that they are easy to understand and implement, that's all. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "ocaml-developer" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/ocaml-developer?hl=en For other OCaml forums, see http://caml.inria.fr/resources/forums.en.html -~----------~----~----~----~------~----~------~--~---
