瞭解使用對象作爲哈希值的JavaScript算法的複雜性

Question

我正在嘗試想出一種算法來解決以下問題。

給出一組ID

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)算法通過創建一個id到人的映射來改善這一點，然後我可以查找每個id的人。

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; 
}; 

但是，當我測試了這兩個算法似乎preform大致相同。 ＃1鉻更快，＃2在Firefox中稍快。

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

我越來越覺得插入場成一個對象是O(log n)不O(1)因爲我本來期望。我已閱讀了一些有衝突的帖子，但我不確定。我想這可能取決於瀏覽器。有沒有什麼辦法可以在JavaScript中用O（n）算法一致地解決這個問題？

Answer 1

首先，JavaScript不要求將對象實現爲散列（平均值爲O(1)查找），而不是使用其他結構（如O(log(n))的BTree）。所以沒有人能保證對象屬性查找的性能。

但通常人們使用哈希值。這是O(1)。

但正如笑話所說，對於所有意圖和目的，log（n）是一個常數。對於Google來說，這是一個稍微大一點的常量。捕捉到真實的真相。 log(1000)和log(1000000000)之間的區別是3倍於CPU的緩存與去RAM訪問的東西之間的差別是10倍。雖然理論上O(1)比O(log(n))更好，在實踐中數據的大小，我們實際上很可能會遇到，實施細節造成更大的差異。而且要麼能贏。

所以你的基準測試沒有提到理論縮放規則。而事實上，不同的實現有不同的表現獲獎者爲您的使用情況下，大約是世界上不幸的事實，你必須在工作中的一個