Понимание сложности алгоритма JavaScript с использованием объекта как хеша

Question

Я пытаюсь найти алгоритм для решения следующей проблемы.

Учитывая массив идентификаторов

var ids = [8098272281362432, 7824519999782912]; 

Найти все матчи в массиве элементов.

var people = [ 
    { 
     "id": 8098272281362432, 
     "age": 59, 
     "name": "Douglas Hunter" 
    }, 
    { 
     "id": 625873891885056, 
     "age": 1, 
     "name": "Lottie Owen" 
    }, 
    { 
     "id": 7824519999782912, 
     "age": 100, 
     "name": "Maud Wise" 
    }, 
    { 
     "id": 2561552265773056, 
     "age": 115, 
     "name": "Annie Bennett" 
    } 
]; 

Подход 1 я мог бы решить эту проблему путем сортировки обоих массивов по id (O(n log n)), а затем переборе обоих массивов один раз сверху вниз (O(n))

var alg1 = function(people, ids) { 
    var matches = []; 

    var sortedPeople = people.sort(function(a, b) { 
    return a.id - b.id 
    }); 
    var sortedIds = ids.sort(function(a, b) { 
    return a - b 
    }); 
    var curPersonIndex = 0; 

    sortedIds.forEach(function(id) { 
    while (sortedPeople[curPersonIndex].id !== id) { 
     curPersonIndex++; 
    } 

    matches.push(sortedPeople[curPersonIndex]); 
    }); 

    return matches; 
}; 

Подход 2 Я мог бы улучшить это с помощью алгоритма O(n), создав отображение идентификаторов для людей, а затем я могу просто найти человека для каждого идентификатора.

var alg2 = function(people, ids) { 
    var matches = []; 

    peopleMap = {}; 

    people.forEach(function(person) { 
    //Is this O(1) or O(log n)? 
    peopleMap[person.id] = person; 
    }); 

    ids.forEach(function(id) { 
    matches.push(peopleMap[id]); 
    }); 

    return matches; 
}; 

Однако, когда я проверяю это, оба алгоритма кажутся заготовкой примерно одинаковыми. # 1 быстрее в хроме и # 2 немного быстрее в Firefox.

http://plnkr.co/edit/FidAdBqS98RKebxaIlva?p=preview

Я получаю ощущение, что вставка поля в объект является O(log n) не O(1), как я ожидал бы. Я прочитал некоторые противоречивые сообщения об этом, хотя я не уверен. И я думаю, это может зависеть от браузера. Есть ли способ последовательно решить эту проблему с помощью алгоритма O (n) в JavaScript?

Answer 1

Прежде всего, JavaScript не требует, чтобы объекты были реализованы как хеширования (в среднем O(1)), а не с использованием какой-либо другой структуры, такой как BTree, которая равна O(log(n)). Поэтому никто не может гарантировать производительность поиска атрибутов объекта.

Но обычно люди используют хеши. Который O(1).

Но, как говорится в шутке, Во всех смыслах log (n) является константой. Для Google это немного большая константа. Это захватывает настоящую правду. Разница между log(1000) и log(1000000000) является фактором 3. Разница в доступе к чему-либо в кэше ЦП против работы в ОЗУ является фактором 10. Хотя теоретически O(1) лучше, чем O(log(n)), на практике с размерами данных, которые мы фактически скорее всего, столкнется, детали реализации сделают гораздо большую разницу. И любой может победить.

Итак, ваши тесты не говорят ничего полезного о теоретических правилах масштабирования. И тот факт, что разные реализации имеют разные победители производительности для вашего случая использования, является одним из неудачных фактов о мире, в котором вы должны работать.