什麼是返回列表A和列表B中存在的x，y座標的最快方法？

我有兩個列表（列表A和列表B）的x，y座標，其中0 < x < 4000,0 < y < 4000，它們將始終是整數。我需要知道這兩個列表中的座標。如何處理這個問題，你會有什麼建議？什麼是返回列表A和列表B中存在的x，y座標的最快方法？

我一直在想代表列爲位的兩個網格，做按位&可能？

列表A有大約1000個條目，每10,000個請求可能會有一次更改。 B列表的長度會有很大的不同，並且在每次穿行時都會有所不同。

編輯：我應該提到，沒有座標將在列表中兩次;例如，1,1不能在列表A中超過一次。

來源

2011-03-24 boodle

你打算如何使用intersec重刑？ – EvilTeach 2011-03-24 16:56:38

由於範圍是固定的，因此可以將（x，y）表示爲單個24位數字。使用x範圍的前12位（給你0-4096）和餘下的y範圍。那麼問題就是兩個列表的交集。 – 2011-03-24 16:56:39

放列表A的座標轉換成某種類型的集合（可能是一個哈希，BST，或堆）的，那麼你就可以快速查看是否從名單B的座標是存在的。

根據您是否希望列表存在或不存在於列表中，將確定您使用的基礎數據結構。

哈希是善於告訴你，如果事情是它，雖然這取決於它是如何實現的，可以設法找到的東西，是不是在這時候表現不佳。

BST和堆是在告訴你，如果事情是與否同樣出色，但是當事情是在它不執行理論以及哈希值。

來源

2011-03-24 16:57:12 helloworld922

根據它們的字典順序來定義一個排序（先在x上排序然後在y上排序）。根據O（n log n）時間中的排序對兩個列表進行排序，其中n是每個列表的元素數量中較大的一個。設置一個指向每個列表的第一個元素的指針，並提前指向較小元素的指針;當指針引用具有相同值的元素時，將它們放入一個集合中（以避免每個列表中的多重性）。最後一部分可以在O（n）時間（或O（m log m））中完成，其中m是兩個列表共有的元素數量。

更新（基於下面的評論和編輯以上）：由於沒有點多次出現在每個列表中，那麼你可以使用列表或向量或離隊抱到兩個或一些其他常見的點（攤銷）恆定時間插入實現O（n）時間性能，而不管共同元素的數量。

來源

2011-03-24 16:57:22 andand

啊，這實際上是一個非常漂亮的解決方案：P在沒有增加內存開銷的情況下獲得與bst（我認爲）相同的理論性能，並且我懷疑它在實踐中更好，因爲您不必擔心平衡樹。 – helloworld922 2011-03-24 17:05:29

我喜歡這個解決方案 - 感謝提及可能的重複;我已經編輯了這個問題來澄清這個問題，因爲問題的本質不會有任何問題。 – boodle 2011-03-24 17:23:57

由於A是相當靜態的，他們是否發生在A.一個例子是一個std ::設置>答：您可以考慮建立一個查詢結構和B中的所有元素的檢查，你可以查詢像A.find（element_from_b ）！= A.end（）...

所以在總的運行時間爲最壞的情況下O（b日誌一）（其中b是在乙元件的數目，和一個分別地）。還要注意，因爲a總是大約10000，所以log a基本上是不變的。

來源

2011-03-24 16:58:15 dcn

這是一個問題，只是尖叫「Bloom Filter」在我身上。

來源

2011-03-24 16:59:31

如果數據很小，使用bloom過濾器似乎毫無意義。它可以給出錯誤的答案... – 2011-03-24 20:02:45

如果我理解正確，你想在X和Y的公共座標 - 交集（集）列表A和B？如果正在使用STL：

#include <vector> 
#include <std> 
using namespace std; 
// ... 
set<int> a; // x coord (assumed populated elsewhere) 
set<int> b; // y coord (assumed populated elsewhere) 
set<int> in; // intersection 
// ... 
set_intersection(a.begin(), a.end(), b.begin(), b.end(), insert_iterator<set<int> >(in,in.begin()));

來源

2011-03-24 17:00:22 Ryan

代表（X，Y）作爲如在註釋中描述的單個24比特數。

以數字順序維護A（你說它變化不大，所以這應該幾乎沒有任何成本）。

對於每個B在列表上執行二進制搜索。由於A大約有1000個條目，因此最多需要10個整數比較（在最壞的情況下）才能檢查成員資格。

如果你有更多的內存（大約2MB）可以創建一個位向量來支持所有可能的24位數，然後每個項目執行一個位操作來測試成員資格。所以如果值在那裏（否則爲0），則A將由具有位集的單個2^24位數表示。要測試成員資格，您只需使用適當的位和操作。

來源

2011-03-24 17:02:41

我從來沒有想過將座標表示爲單個數字。聰明！我會對這個建議進行修改，看看它是如何發展的。謝謝！ – boodle 2011-03-24 17:11:40

這讓我對最後一段的3次重讀，然後它終於點擊了。我認爲這是迄今爲止最好的解決方案。我會試試這個和andand的下面，看看他們如何從我們身上剔除這些垃圾。 – boodle 2011-03-24 17:37:12

好的方法; +1 – andand 2011-03-24 19:50:06

我認爲散列是你最好的選擇。

//僞碼：

輸入：兩個列表，每個（X，Y）座標
發現是長名單，稱其爲
散列中的每個元素
轉到另一個列表中，將其稱爲B
散列B中的每個元素並在表中查找它。
，如果有一個匹配，返回/存儲（X，Y）的某處
重複＃4，直到結束

假設A的長度爲M和B的長度爲n時，運行時間爲O（米+ N） - > O（n）的

來源

2011-03-24 23:15:28

如果要實現STL斷言這派兩個對（即return (R.x < L.x || (R.x==L.x && R.y < L.y)你可以調用std::list::sort命令他們，並std::set_intersection找到共同的元素這是很容易沒有必要。寫出算法

來源

2011-03-25 10:14:18 MSalters

什麼是返回列表A和列表B中存在的x，y座標的最快方法？

回答

相關問題