3 ms·
And for priority queues, there's a wonderfully clever scheme which involves using a skiplist: http://www-cs-students.stanford.edu/~itayl/ipdps.pdf http://www-c
by pjscott 15y ago
And for priority queues, there's a wonderfully clever scheme which involves using a skiplist:
http://www-cs-students.stanford.edu/~itayl/ipdps.pdf http://www-cs-students.stanford.edu/~itayl/ipdps.pdf
The probabilistic nature of the data structure lets them get those nice O(lg n) and O(1) expected times without the wide-ranging memory conflicts that slow down concurrent min-heaps. Some more basic info on skiplists for people who aren't familiar with them:
http://en.wikipedia.org/wiki/Skip_list http://en.wikipedia.org/wiki/Skip_list
- marshray 15y agoYes I'm working on an implementation of those myself. There are even designs for lock-free skiplist priorty queues, but they tend to be a little slower than the locking versions.
- pjscott 15y agoLock-free skiplist priority queues, incidentally, become very elegant if your processor supports even the most basic hardware transactional memory.