2016-01-24 28 views
2

是否有JavaScript搜索的數據的更快的方式(經由node.js具體上V8,但沒有C/C++模塊)比使用JavaScriptObjectV8 JavaScript對象VS二叉樹

This may be outdated但它建議爲每個屬性動態生成一個新的類。這讓我想知道二叉樹實現可能會更快,但this does not appear to be the case

二叉樹實現不是很好的平衡,因此可能會用更好的平衡(只有前26個值由手大致平衡。)

有沒有人對爲什麼或如何可能得到改善的想法?另一個說明:動態類的概念是否意味着實際上有〜260,000個屬性(在第二個鏈接的jsperf基準測試中),並且隨後在內存中保留動態類定義鏈?

+2

這看起來像一個XY問題。你的用例是什麼?你有沒有進行基準測試,以確定普通對象絕對不適合你的用例? – mscdex

+0

你確實需要描述一個特定的用例。 「更快的搜索數據方式」並不能描述你實際想要解決的問題。這個問題,現在太不確定了。 – jfriend00

+0

用例在數十萬條記錄中搜索關鍵字。我認爲這將從附加的自定義jsperf性能測試中明顯看出差異。 – CoryG

回答

2

V8使用「地圖」的概念,它描述了對象中數據的佈局。

這些映射可以是「快速映射」,它指定從可以找到特定屬性的對象開始的固定偏移量,或者它們可以是「字典映射」,它使用散列表來提供查找機制。

每個對象都有一個指向描述它的地圖的指針。

通常情況下,對象以快速地圖開始。將屬性添加到具有快速映射的對象時,映射將轉換爲描述對象內新屬性位置的新映射。如有必要,該對象將被重新分配足夠的空間用於新數據項目,並且該對象的地圖指針將被設置爲新地圖。

舊地圖會記錄從其轉換的記錄,包括指向新地圖的指針以及其添加導致地圖過渡的屬性的說明。

如果另一個具有舊地圖的對象獲得相同的屬性(這是非常常見的,因爲相同類型的對象傾向於以相同的方式使用),該對象將只使用新地圖 - V8不會在這種情況下,不會創建新地圖。

但是,一旦屬性的數量超過某個閾值(實際上,當前的度量標準是關於使用的存儲空間而不是實際的屬性數量),該對象將更改爲使用字典映射。此時使用散列表重寫對象。一般來說,它不會經歷任何更多的地圖轉換 - 所添加的任何其他屬性將只進入散列表。

快速映射允許V8生成優化代碼(使用曲軸),其中對象內的屬性偏移被硬編碼到機器代碼中。這使得它可以做到這一點非常快速 - 它避免了查找的需要。

顯然,生成的機器代碼依賴於映射 - 如果對象的數據佈局發生變化,代碼必須在必要時丟棄並重新優化。 V8有一個類型分析機制,用於收集有關執行未優化代碼期間各種對象類型的信息。在達到某些穩定性約束條件之前,它不會觸發代碼的優化 - 其中之一就是函數中使用的對象映射不會頻繁變化。

Here's a more detailed description of how this stuff works.

Here's a video where one of the lead developers of V8 describes stuff like map transitions and lots more.

爲您的特定的測試情況下,我認爲它會經過一個幾百地圖轉換,而屬性在編制循環被添加,那麼它最終將過渡到一個字典基於對象。它當然不會通過260,000。

關於你關於二叉樹的問題:一個正確大小的散列表(有一個合理的散列函數和大量的對象)總是會比二叉樹好,因爲你只是在尋找一個用例,因爲你的測試代碼似乎這樣做(所有插入都在安裝階段完成)。