JavaScript:对象键的快速随机索引

问题描述

我试图从用作快速索引的字典的对象中随机选择一个随机属性.

I am attempting to randomly select a random property from an object that I use as a dictionary for fast indexing.

考虑以下代码:

//Create test dictionary
var dict = {};
for(var i = 0; i < 10000; i++) {
  var num = Math.random() * 1000000 << 0;
  dict[num] = { Id: num };
}

//Fuzz
const NUM_RUNS = 1000;
var start = new Date();
for(var i = 0; i < NUM_RUNS; i++)
  getRandom(dict);
var end = new Date();

var runTime = (end.getTime() - start.getTime()) / 1000;
var timePerCall = (runTime / NUM_RUNS) * Math.pow(10,9);
console.log('Total Calls: ' + NUM_RUNS);
console.log('Total Runtime: ' + runTime + ' seconds');
console.log('Time Per Call: ' + timePerCall + ' nanoseconds');



function getRandom(dict) {
  var keys = Object.keys(dict);
  var index = keys[Math.random() * keys.length << 0];
  return dict[index];
}

如您所见，使用 Object.keys() 的成本非常，尤其是随着字典的增长.

As you can see, using Object.keys() is very expensive, especially as the dictionary grows.

我正在寻找一种最佳方法来实现字典中元素的随机选择.当然，字典中有 10000 多个元素是极端情况，但我仍然希望能够处理它.

I am looking for an optimal way to achieve random selection of an element in the dictionary. Of course, having 10000+ elements in the dictionary is an extreme edge case, but I would like to be able to handle it nonetheless.

推荐答案

如果缓存 Object.keys 数组不可行，您可以使用 Proxy:

If caching the Object.keys array is infeasible, you can maintain your own copy with a Proxy:

function generateKeyTracker (keysPropertyName) {
  const set = new Set();
  function defineProperty (target, property, descriptor) {
    target[property] = descriptor.value;

    if (set.has(property)) return true;

    set.add(property);
    target[keysPropertyName].push(property);
    return true;
  }
  function deleteProperty (target, property) {
    delete target[property];
    
    if (!set.delete(property)) return true;

    target[keysPropertyName] = target[keysPropertyName].filter(key => key !== property);
    return true;
  }
  return {defineProperty, deleteProperty};
}

//Create test dictionary
var dict = new Proxy(
  Object.defineProperty({}, '__keys', {
    configurable: true,
    enumerable: false,
    writable: true,
    value: []
  }),
  generateKeyTracker('__keys')
);

for(var i = 0; i < 1e4; i++) {
  var num = Math.random() * 1e6 << 0;
  dict[num] = { Id: num };
}

//Fuzz
const NUM_RUNS = 1e6;
var start = performance.now();
for(var i = 0; i < NUM_RUNS; i++)
  getRandom(dict);
var end = performance.now();

var runTime = end - start;
var timePerCall = (runTime / NUM_RUNS);
console.log(`Total Calls: ${NUM_RUNS}`);
console.log(`Total Runtime: ${runTime} ms`);
console.log(`Time Per Call: ${timePerCall * 1e6} ns`);

function getRandom(dict) {
  var index = Math.random() * dict.__keys.length << 0;
  return dict[dict.__keys[index]];
}

这在 property 上使用陷阱创建和删除 跟踪 dict 的属性键，这些键存储在 不可枚举 属性dict.__keys.

This uses traps on property creation and deletion to keep track of dict's property keys, which are stored in the non-enumerable property dict.__keys.

这篇关于JavaScript:对象键的快速随机索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！