2

I'm trying to implement a sorted set data structure. The functionality I need is to insert a hash and a corresponding score. So the sorted set will be sorted based on the score, which is a number. When I search the sorted set by score, some of the scores I'm searching for won't be in the sorted set. I want to find the next-biggest score's hash.

For example, if the scores are 1, 3, and 4 in the sorted set and if I want to search for score 2, I want to return the hash at score 3.

To summarize: I have a data set of 11 million records so that's why I'm trying to implement a javascript sorted set that can search by score, and return the next biggest score's hash if the score I'm looking for doesn't exist.

Thank you!

PythonNoobile
  • 65
  • 1
  • 1
  • 9
  • I have been looking for such a data structure but with poor results :( Existing sorted set implementations seem to be designed for sorting by key instead of value, for example http://www.collectionsjs.com/sorted-map and https://www.npmjs.com/package/binary-sorted-set – Akseli Palén May 16 '17 at 19:00
  • Redis' sorted sets are backed by a variant of skip list, according to http://stackoverflow.com/questions/9625246/what-are-the-underlying-data-structures-used-for-redis – Akseli Palén May 16 '17 at 19:42
  • 1
    I managed to find [an abandoned Redis style sorted set project](https://www.npmjs.com/package/sorted-map) by [skeggse](https://stackoverflow.com/users/345645/skeggse). Forked it, polished it, and published it into NPM. Let us enjoy: https://www.npmjs.com/package/redis-sorted-set – Akseli Palén May 16 '17 at 21:44

1 Answers1

0

https://github.com/js-sdsl/js-sdsl

The OrderedSet in Js-sdsl may be helpful.

This is a really sorted-set which implement refer to C++ STL Set.

import { OrderedSet } from 'js-sdsl';
const st = new OrderedSet([1, 3, 4]);
const it = st.lowerBound(2);
console.log(it.pointer); // 3
Zilong Yao
  • 54
  • 4