Вопрос о производительности словаря Javascript

Question

Прямо сейчас у меня есть следующий словарь javascript

var a = {};
a['SVG343'] = 1942;
a['UAL534'] = 2153;

Эти цифры справа представляют времена, а ключи - уникальные идентификаторы. Я хотел сделать идентификаторы ключей, поскольку они уникальны. Моей проблеме дается время найти соответствующий идентификатор. Как я собирался это сделать, проходил каждую запись в словаре, пока не нашел правильное время и не использовал текущий ключ, чтобы получить идентификатор.

Тем не менее, я беспокоюсь о производительности, мой вопрос: проходит ли каждая запись в словаре (O (n)) значительно медленнее, чем любой другой метод?

Answer 1

Вы можете построить индекс из времен:

var indexByTimes = {};
for (var prop in a) {
    if (a.hasOwnProperty(prop)) {
        indexByTimes[a[prop]] = prop;
    }
}

И для нескольких значений времени используйте массив для идентификаторов:

for (var prop in a) {
    if (a.hasOwnProperty(prop)) {
        if (indexByTimes.hasOwnProperty(a[prop])) {
            indexByTimes[a[prop]].push(prop);
        } else {
            indexByTimes[a[prop]] = [prop];
        }
    }
}

Затем вы можете получить доступ ко всем идентификаторам, соответствующим времени 1942 года, с помощью indexByTimes['1942'] в O (1).

Answer 2

Итерация по всем ключам словаря - O(n).Таким образом, итерация по a.items() также будет O(n).Но итерация всех ключей с последующим поиском значения (то есть for(var key in a) { x += a[key]; }) составляет O(n*log(n)).Так что было бы предпочтительнее либо повторить хотя бы a.items(), либо просто использовать список