JavaScript的設定數據結構，對數搜索時間

可能重複：
Is there a library for a Set data type in Javascript?JavaScript的設定數據結構，對數搜索時間

有沒有一種方法來創建模仿C++設置一個JavaScript數據結構？我需要在log（n）時間內執行搜索，但找不到任何適合使用的語言。我見過幾個問題，說我應該把這套作爲一個對象。這會工作嗎？數組的鍵和有效載荷是數字。

2012-08-14 Josh

類似的問題是：http://stackoverflow.com/questions/2342749/is-there-a-library-for-a-set-data-type-in-javascript也許看看源代碼JS.Set庫的代碼會給你一些想法？ http://jsclass.jcoglan.com/set.html – River 2012-08-14 17:34:02

它將不得不在JavaScript中一切都是一個對象。

來源

2012-08-14 16:42:58 GitaarLAB

我的意思是通過做'var set = {};' – Josh 2012-08-14 16:44:19

這樣的東西來創建我自己的，請參閱[JavaScript上的Crockford - 第2章：然後是JavaScript ]（http://www.youtube.com/watch?v=RO1Wnu-xKoY），你就會明白。需要注意的是：如果需要，可以在使用/讀取之前檢查（設置/轉換）值的類型，而不是在聲明值時檢查（設置/轉換）值的類型。 – GitaarLAB 2012-08-14 16:45:05

請注意，我的問題的主要部分是如果有可能搜索這些對象或數組在O（nlogn）時間 – Josh 2012-08-14 16:51:14

如果您需要有序集（它允許您按照您定義的順序從最小元素循環到最大元素），您可以在JS中實現自己的數據結構。我不能在這方面提供更多的信息，因爲我沒有這樣做。

如果您滿意無序設置，可以實現它如下：

定義對象的規範化字符串表示要存儲在集合。如果你需要一個帶數字的集合，只需使用數字的字符串表示。如果您需要一組用戶定義的對象，您可以挑選出定義對象身份的屬性，並在標準化的字符串表示中使用它們。
通過將規範化的字符串表示映射到實際對象，創建一個JS對象以用作set。
可以通過使用字符串表示檢查屬性名稱來完成搜索。
插入到集合可以通過以下方式完成：首先檢查字符串表示是否已經存在，然後將字符串表示映射到實際對象，如果該對象尚不在集合中。
刪除可以通過使用delete完成，屬性名稱是要刪除的對象的字符串表示形式。

來源

2012-08-14 16:55:24 nhahtdh

我會嘗試，因爲我實際上需要一個無序集。然後我希望我可以實現一個對數時間搜索方法。謝謝 – Josh 2012-08-14 16:57:18

@Josh：出於性能原因，訪問Javascript屬性至少爲O（log n）。根據實現情況，它可能比這更好，但我們至少期望像結構這樣的字典支持屬性查找。 – nhahtdh 2012-08-14 17:11:01

對於無序集合，使用散列表實現可能會更好。這些做O（1）查找，只要散列表不會重載。

對於有序的內存集合，標準答案似乎是treaps（良好的平均時間，高標準偏差）和紅黑樹（差的平均時間，低的標準偏差）。這些都是O（logn）查找。

來源

2012-08-14 17:25:00 user1277476

JavaScript的設定數據結構，對數搜索時間

回答

相關問題