Ответ 1
Удвоение в памяти от Map до Set в вашей версии node происходит из-за плохой реализации. Ну, не "плохо", как таковое, просто не подходит для миллионов записей. Более простая обработка Set приобретается с памятью. Там нет бесплатного обеда, как всегда, извините.
Почему они так много используют? Они должны обрабатывать любой объект, и метод, позволяющий обрабатывать все возможные варианты, действительно дорог. Можно оптимизировать, если все, что у вас есть, имеет один вид, но вы должны его проверить, и в 99,99% всех случаев это не стоит хлопот, потому что карты и наборы и массивы коротки, несколько тысяч записей на большинство. Быть мягким: время разработчика дорого и лучше тратить в другом месте. Я мог бы добавить: это с открытым исходным кодом, сделай это сам! но я знаю, что это проще сказать, чем сделать, -)
Вам нужно бросить это самостоятельно. Вы можете использовать Uint32Array для этого и построить вокруг него таблицу хешей.
Bing-Maps кодируются строками базовых 4 цифр (не более 23) в соответствии с MS и Четырехзначное описание. Используя кодировку последнего (не прочитав первого, так что это может быть неправильно в деталях), мы можем поместить его в два 32-битных целых числа:
function quadToInts(quad, zoom){
var high,low, qlen, i, c;
high = 0>>>0;
low = 0>>>0
zoom = zoom>>>0;
// checks & balances omitted!
qlen = quad.length;
for(i = 0; i < 16 && i < qlen ;i++){
c = parseInt(quad.charAt(i));
high |= c << (32-(i*2 + 2));
}
// max = 23 characters (says MS)
for(i = 0; i < 8 && i < qlen - 16 ;i++){
c = parseInt(quad.charAt(16 + i));
low |= c << (32-(i*2 + 2));
}
low |= zoom;
return [high,low];
}
И обратно
// obligatory https://graphics.stanford.edu/~seander/bithacks.html
function rev(v){
var s = 32;
var mask = (~0)>>>0;
while ((s >>>= 1) > 0) {
mask ^= (mask << s)>>>0;
v = ((v >>> s) & mask) | ((v << s) & (~mask)>>>0);
}
return v;
}
function intsToQuad(k1,k2){
var r, high, low, zoom, c, mask;
r = "";
mask = 0x3; // 0b11
high = k1>>>0;
low = k2>>>0;
zoom = low & (0x20 - 1);
low ^= zoom;
high = rev(high);
for(var i = 0;i<16;i++){
c = high & mask;
c = (c<<1 | c>>>1) & mask;
r += c.toString(10);
high >>>= 2;
}
low = rev(low);
for(var i = 0;i<16;i++){
c = low & mask;
c = (c<<1 | c>>>1) & mask;
r += c.toString(10);
low >>>= 2;
}
return [r,zoom];
}
(Все быстрые хаки, пожалуйста, проверьте перед использованием! И дьявол C & P, возможно, тоже был здесь)
Грубый эскиз для базы хэш-таблицы на следующей хэш-функции
// shamelessly stolen from http://www.burtleburtle.net/bob/c/lookup3.c
function hashword(k1, // high word of 64 bit value
k2, // low word of 64 bit value
seed // the seed
){
var a,b,c;
var rot = function(x,k){
return (((x)<<(k)) | ((x)>>>(32-(k))));
};
/* Set up the internal state */
a = b = c = 0xdeadbeef + ((2<<2)>>>0) + seed>>>0;
if(arguments.length === 2){
seed = k1^k2;
}
b+=k2;
a+=k1;
c ^= b; c -= rot(b,14)>>>0;
a ^= c; a -= rot(c,11)>>>0;
b ^= a; b -= rot(a,25)>>>0;
c ^= b; c -= rot(b,16)>>>0;
a ^= c; a -= rot(c,4)>>>0;
b ^= a; b -= rot(a,14)>>>0;
c ^= b; c -= rot(b,24)>>>0;
return c;
}
function hashsize(N){
var highbit = function(n) {
var r = 0 >>> 0;
var m = n >>> 0;
while (m >>>= 1) {
r++;
}
return r;
};
return (1<<(highbit(N)+1))>>>0;
}
function hashmask(N){
return (hashsize(N)-1)>>>0;
}
И (довольно неполный) код для обработки таблиц
/*
Room for 8-byte (64-bit) entries
Table pos. Array pos.
0 0 high, low
1 2 high, low
2 4 high, lowl
...
n n*2 high, low
*/
function HashTable(N){
var buf;
if(!N)
return null;
N = (N+1) * 2;
buf = new ArrayBuffer(hashsize(N) * 8);
this.table = new Uint32Array(buf);
this.mask = hashmask(N);
this.length = this.table.length;
}
HashTable.prototype.set = function(s,z){
var hash, quad, entry, check, i;
entry = null;
quad = quadToInts(s,z);
hash = hashword(quad[0],quad[1]);
entry = hash & this.mask;
check = entry * 2;
if(this.table[check] != 0 || this.table[check + 1] != 0){
//handle collisions here
console.log("collision in SET found")
return null;
} else {
this.table[check] = quad[0];
this.table[check + 1] = quad[1];
}
return entry;
};
HashTable.prototype.exists = function(s,z){
var hash, quad, entry, check, i;
entry = null;
quad = quadToInts(s,z);
hash = hashword(quad[0],quad[1]);
entry = hash & this.mask;
check = entry * 2;
if(this.table[check] != 0 || this.table[check + 1] != 0){
return entry;
}
return -1;
};
HashTable.prototype.get = function(index){
var entry = [0,0];
if(index > this.length)
return null;
entry[0] = this.table[index * 2];
entry[1] = this.table[index * 2 + 1];
return entry;
};
// short test
var ht = new HashTable(100);
ht.set("01231031020112310",17);
ht.set("11231031020112311",12);
ht.set("21231033020112310",1);
ht.set("31231031220112311321312",23);
var s = "";
for(var i=0;i<ht.table.length;i+=2){
if(ht.table[i] !== 0){
var e = intsToQuad(ht.table[i],ht.table[i+1]);
s += e[0] +", " +e[1] + "\n";
}
}
console.log(s)
Столкновения должны быть редкими, поэтому пара коротких стандартных массивов сделает их поймать. Чтобы справиться с этим, вам нужно добавить еще один байт в 8 байтов для двух целых чисел, представляющих Quad, или, лучше, установить второе целое число для всех (не будет с Quad), а первое - в позиции (-ы) в массив столкновения.
Добавление полезной нагрузки немного сложнее, потому что у вас есть только фиксированная длина.
Я установил размер таблицы для следующей более высокой мощности двух. Это может быть слишком много или даже слишком велико, и у вас может возникнуть соблазн адаптировать его, поэтому имейте в виду, что маскировка не работает так, как ожидалось, больше вам нужно сделать по модулю.