Какой ключ Javascript: структура данных значения, встроенная или иная, где ключ является объектом, обеспечивает наилучшую производительность? - PullRequest
Новая
       7

Какой ключ Javascript: структура данных значения, встроенная или иная, где ключ является объектом, обеспечивает наилучшую производительность?

0 голосов
/ 06 мая 2018

Представьте, что вам нужна структура данных ключ: значение, где находятся ключи, значение (не ссылка) объектов JavaScript этого типа: 

{board: string, player: number}

и значения являются объектами JavaScript этого типа: 

{
  state:{
    board: string, 
    player: number 
  }, 
  score: number
}

Какая структура данных предложит вам лучшую скорость установки / получения производительности? Карта , где вам нужно было бы упорядочить объекты, прежде чем использовать их в качестве ключей, или какая-то хэш-карта, где вы фактически используете хеш-функцию для ключевых объектов, а затем используете хеш-код в качестве ключа в массиве или карта? Или, может быть, вы можете подумать о какой-то другой реализации, которая предложила бы лучшую производительность?

Просто чтобы прояснить, в нашей структуре данных, когда речь идет о ключах, хотя 

const object1 = {board:'123456789', player: 1}

и 

const object2 = {board:'123456789', player: 1}

относятся к двум отдельным объектам JavaScript, если они используются в качестве ключей, они указывают на одно и то же значение в нашей структуре данных ключ: значение. Они будут частью одной пары ключ: значение. Вот почему в случае с картой вам нужно было бы упорядочить объекты, прежде чем использовать их в качестве ключей.

Разыскиваемое поведение: 

myDataCollection.set(object1, someValue)
myDataCollection.get(object2) // -> someValue

Текущая реализация Map для JavaScript делает это 

 myMap.set(object1, someValue)
 myMap.get(object2) // -> undefined

1 Ответ

0 голосов
/ 06 мая 2018

Попробовав несколько вещей, я пришел к выводу, что хэш-таблица с хэш-функцией работает быстрее, чем Map. Вот моя реализация тестового кода: 

function generateKeyObject() {
    const board = Math.random().toString(36).substring(2, 15) + Math.random().toString(36).substring(2, 15);
    const player = Math.random();
    return {board, player}
}

function generateValueObject(key) {
    const score = Math.random();
    return {state: {board: key.board, player: key.player}, score}
}

const getRandomIntInclusive = (min, max) => {
    min = Math.ceil(min)
    max = Math.floor(max)
    return Math.floor(Math.random() * (max - min + 1)) + min // The maximum is inclusive and the minimum is inclusive
  }

let numberOfEntries = 1000000;

// Generate an array of keys
let keys = [];

for (let i = 0; i < numberOfEntries; i++) {
    keys.push(generateKeyObject());
}

// Generate an array of values
let values = [];

for (let i = 0; i < numberOfEntries; i++) {
    values.push(generateValueObject(keys[i]));
}


/********************** MAP **********************************/ 

const map = new Map();

let elapsedTime = 0;
// Set
for (let i = 0; i < numberOfEntries; i++) { 
    const start = Date.now()
    const keyString = JSON.stringify(keys[i]);
    map.set(keyString, values[i]);
    const stop = Date.now()
    elapsedTime += stop-start;
}
console.log(`Map set total time: ${(elapsedTime / 1000)}`);


// Get
elapsedTime = 0;
for (let i = 0; i < numberOfEntries; i++) {
    const index = getRandomIntInclusive(0, numberOfEntries - 1);
    const start = Date.now()
    const keyString = JSON.stringify(keys[index]);
    const result = map.get(keyString);
    const stop = Date.now()
    elapsedTime += stop-start;
    if (result !== values[index]) throw new Error('Oops, there is a problem with the Get operation of Map');
}
console.log(`Map get total time: ${(elapsedTime / 1000)}`);


/********************** HASHTABLE  ****************************/


class HashTable {    
    constructor(bucketCount) {
        this.buckets_ = []
        this.bucketCount_ = bucketCount
        for (let i=0; i< this.bucketCount_;i++){
            this.buckets_.push(new Map());
        }
    }

    hashFunction_(obj) {
        let key = JSON.stringify(obj);
        let hash = 0;
        if (key.length === 0) return hash;
        for (let i = 0; i < key.length; i++) {
            hash = (hash<<5) - hash;
            hash = hash + key.charCodeAt(i);
            hash = hash & hash; // Convert to 32bit integer
        }
        return Math.abs(hash);
    }

    getBucketIndex_(obj) {
        return this.hashFunction_(obj) % this.bucketCount_;
    }

    getBucket_(obj) {
        return this.buckets_[this.getBucketIndex_(obj)];
    }

    set(key, value) {
        this.getBucket_(key).set(key, value);
    }
    get(lookupKey) {
        return this.getBucket_(lookupKey).get(lookupKey);
    }
}

const hashTable = new HashTable(numberOfEntries);

elapsedTime = 0;
// Set
for (let i = 0; i < numberOfEntries; i++) { 
    const start = Date.now()    
    hashTable.set(keys[i], values[i]);
    const stop = Date.now()
    elapsedTime += stop-start;
}
console.log(`Hashtable set total time: ${(elapsedTime / 1000)}`);

// Get
elapsedTime = 0;
for (let i = 0; i < numberOfEntries; i++) {
    const index = getRandomIntInclusive(0, numberOfEntries - 1);
    const start = Date.now()
    const result = hashTable.get(keys[index])
    const stop = Date.now()
    elapsedTime += stop-start;
    if (result !== values[index]) throw new Error('Oops, there is a problem with the Get operation of HashTable');
}
console.log(`Hashtable get total time: ${(elapsedTime / 1000)}`);
...