4 ms·

Skip Lists. Seem handy for increasing access times on ordered lists... Any Lispers care to comment?

andars 10y ago
what's your method for quickly searching an ordered list? Binary search falls apart since you don't have free random access.
- qwertyuiop924 10y ago
  Skip lists allow for that, sort of. In Lisp, most people would just, you know, not use a list for that. You can do that, you know... The only reason I asked about lispers is that lispers really like lisps, and I was curious if any of them had implemented skip lists for some reason, and if so, how.
  - andars 10y ago
    > ... just, you know ... you know ... Yes, I know. Do you? You made the suggestion that skip lists are inferior to ordered lists, not me. (good for "increasing access times on ordered lists") I'm still perplexed as to your rationale for that statement.
    - qwertyuiop924 10y ago
      No, I didn't, AFAIK. I'm baffled as to where you drew that from...
      - cronjobber 10y ago
        Maybe because you wrote "increasing access times", which could be read as "skip lists are slower." Not what you meant, probably.
        andars 10y ago
        This was my understanding of that comment. How else could that be read? I am not able to think of another interpretation of that statement or a context when increased access times would be desired.
        qwertyuiop924 10y ago
        The intended interpretation is that skip lists make access to specific items in ordered lists faster. I am actually a native speaker, so I have no excuse here. I just suck at writing, I guess...
kazinator 10y ago
Skip lists are container data structures for keeping items in order, an alternative to various balanced trees like red-black. The funny thing is how rarely you need that sort of thing if you have an unordered associative container, and a sorting function. It's possible to combine a hash table with a list. E.g. the hash table references not the items directly, but the conses of a list in which those items are stored as the cdr. Then you have keyed random access to the list, as well as a particular order. Finding a spot where to insert is linear, of course. A container which keeps items in order is useful primarily for real-time programming, for implementing a priority queue: the situation is that a dynamic set of items is in constant churn, and needs to be in order all the time (where the order is different from the order in which those items come to life or arrive or whatever). For performance, we don't want to just add an item to the end of the queue and then call sort. If we don't care about this real time aspect, we can just accumulate items and then sort them. Even if we sort a list several times, that may not be of consequence if it is bounded to a small length. Unix treats directories like this: the "dents" are not ordered in any way: globbing expansion and the "ls" utility accumulate names and sort them. Unix could keep directories in sorted order (and there are, I think, some file systems which actually do). There is an anti-pattern of abusing sorting when people don't have an associative container. An example of this is shell scripts which use sorting to help de-duplicate items, instead of an obvious awk job with an associative array. Another anti-pattern occurred in C++: for long time C++ had only std::map and std::set: ordered containers. These were used all the time, even when order was not required (Now there is std::unordered_map). In the late 1990's, I wrote a pretty nice red-black tree data structure in C, which ended up used in various places, such as in ext2fs tools. one company I worked for used it for the basis of a "real-time database" for software running on a switch node for real time packet inspection and processing. The implementation had to be modified to allow for shared memory. I don't miss that kind of container in everyday Lisp programming somehow. I have a several years old branch where that code is half-added to my Lisp dialect. There isn't much motivation to finish the job; the need for that just somehow doesn't arise. Most of the time, either you're dealing with dynamic sets which are unordered (by definition of "set", practically), or else with lists which are ordered, but don't have to be constructed by out-of-order insertions. A lot of the time, the order of a list doesn't actually follow any predicate: the only specification of order is that list instance itself and its actual order. (The order came from somewhere, but its reason is not necessarily known, only that it should be preserved.) ANSI CL doesn't have any optimized ordered list container, only hashes. Why? It seems like nothing notable of that sort originated in any of the base dialects from which CL was formed. Suppose you needed some real-time database for some service application: it would make a lot of sense to just pick one and make Lisp bindings to it.

what's your method for quickly searching an ordered list? Binary search falls apart since you don't have free random access.

qwertyuiop924 10y ago
Skip lists allow for that, sort of. In Lisp, most people would just, you know, not use a list for that. You can do that, you know... The only reason I asked about lispers is that lispers really like lisps, and I was curious if any of them had implemented skip lists for some reason, and if so, how.
- andars 10y ago
  > ... just, you know ... you know ... Yes, I know. Do you? You made the suggestion that skip lists are inferior to ordered lists, not me. (good for "increasing access times on ordered lists") I'm still perplexed as to your rationale for that statement.
  - qwertyuiop924 10y ago
    No, I didn't, AFAIK. I'm baffled as to where you drew that from...
    - cronjobber 10y ago
      Maybe because you wrote "increasing access times", which could be read as "skip lists are slower." Not what you meant, probably.
      - andars 10y ago
        This was my understanding of that comment. How else could that be read? I am not able to think of another interpretation of that statement or a context when increased access times would be desired.
        qwertyuiop924 10y ago
        The intended interpretation is that skip lists make access to specific items in ordered lists faster. I am actually a native speaker, so I have no excuse here. I just suck at writing, I guess...

kazinator 10y ago

Skip lists are container data structures for keeping items in order, an alternative to various balanced trees like red-black. The funny thing is how rarely you need that sort of thing if you have an unordered associative container, and a sorting function. It's possible to combine a hash table with a list. E.g. the hash table references not the items directly, but the conses of a list in which those items are stored as the cdr. Then you have keyed random access to the list, as well as a particular order. Finding a spot where to insert is linear, of course. A container which keeps items in order is useful primarily for real-time programming, for implementing a priority queue: the situation is that a dynamic set of items is in constant churn, and needs to be in order all the time (where the order is different from the order in which those items come to life or arrive or whatever). For performance, we don't want to just add an item to the end of the queue and then call sort. If we don't care about this real time aspect, we can just accumulate items and then sort them. Even if we sort a list several times, that may not be of consequence if it is bounded to a small length. Unix treats directories like this: the "dents" are not ordered in any way: globbing expansion and the "ls" utility accumulate names and sort them. Unix could keep directories in sorted order (and there are, I think, some file systems which actually do). There is an anti-pattern of abusing sorting when people don't have an associative container. An example of this is shell scripts which use sorting to help de-duplicate items, instead of an obvious awk job with an associative array. Another anti-pattern occurred in C++: for long time C++ had only std::map and std::set: ordered containers. These were used all the time, even when order was not required (Now there is std::unordered_map). In the late 1990's, I wrote a pretty nice red-black tree data structure in C, which ended up used in various places, such as in ext2fs tools. one company I worked for used it for the basis of a "real-time database" for software running on a switch node for real time packet inspection and processing. The implementation had to be modified to allow for shared memory. I don't miss that kind of container in everyday Lisp programming somehow. I have a several years old branch where that code is half-added to my Lisp dialect. There isn't much motivation to finish the job; the need for that just somehow doesn't arise. Most of the time, either you're dealing with dynamic sets which are unordered (by definition of "set", practically), or else with lists which are ordered, but don't have to be constructed by out-of-order insertions. A lot of the time, the order of a list doesn't actually follow any predicate: the only specification of order is that list instance itself and its actual order. (The order came from somewhere, but its reason is not necessarily known, only that it should be preserved.) ANSI CL doesn't have any optimized ordered list container, only hashes. Why? It seems like nothing notable of that sort originated in any of the base dialects from which CL was formed. Suppose you needed some real-time database for some service application: it would make a lot of sense to just pick one and make Lisp bindings to it.