索引映射的高效算法

假設您遇到以下問題。您有兩個具有一對一映射的索引集。爲了簡單起見，假設您有一個數組，如int a [] = {21, 30, 45, 78}這個列表將{1,2,3,4}映射到{21,30,45,78}。什麼是獲得反向映射的最有效方式，即給定索引30，如果想要算法返回2，則需要45，您需要3等等。我可以想到以下內容：索引映射的高效算法

索引的二進制搜索。這是有效的內存，並且具有複雜性O(log n)。
有一個數組有79元素，並有reverseMap[21] = 1, reverseMap[30] = 2, reverseMap[45] = 3, reverseMap[78] = 4。這是O(1)，因此速度更快，但不是有效的內存。

對於我的應用程序來說，內存和速度都很重要。我缺乏記憶，因爲這是一個數字處理代碼，因此可以使用數億個點。速度也很重要，因爲算法會被調用很多次。

我覺得哈希表在這裏很有用，但我不太瞭解它的評論。我希望對這個問題有所瞭解。此外，由於編碼是在c++完成的，我希望看到使用STL而不是外部庫的方法。

來源

2012-02-24 GradGuy

這功課嗎？ – 2012-02-24 20:22:39

@LightnessRacesin不是真的 - 只是正在進行的項目中的一部分。我有一個解決方案，但什麼要知道別人的想法 – GradGuy 2012-02-24 20:23:49

然後，我相信你正在尋找http://codereview.stackexchange.com – 2012-02-24 20:24:20

一如既往：簡介。我們可以猜測，但沒有運行你的代碼，我們可能是錯的。我做了一個rough benchmark on ideone（時間是基於我的電腦）。我做的unsigned int十萬查找數組中的十萬臺（我厭倦等待你的「億萬」），而這些是我的結果：

unsorted vector found 1633382974 in 2140 ticks. 
sorted vector found 1633382974 in 62 ticks. 
unordered_map found 1633382974 in 16 ticks. 
std::map found 1633382974 in 172 ticks. //that's half the time of a blink

但是我必須指出，保持這些在你的程序的內存中將有一些開銷超過未排序的向量。如果我們創建時間添加到十萬查找的時機，我們得到：

unsorted vector found 1633382974 in 2141 ticks. 
sorted vector found 1633382974 in 1797 ticks. 
unordered_map found 1633382974 in 16218 ticks. 
std::map found 1633382974 in 30749 ticks. //a full thirty seconds

所以，你可以看到，時序依賴完全在你在你的代碼做什麼。嘗試不同的東西，在上優化，然後以最快的速度執行代碼。

來源

2012-02-24 22:05:53

我會的。感謝您的有益討論:) – GradGuy 2012-02-24 22:29:18

什麼是獲得反向映射

雙std::map<value, value>最有效的方式。或std::unordered_map即，任何地圖類，雙。也就是說第一個映射將來自arrayA的值映射到arrayB，第二個映射將來自arrayB的值映射到arrayA。或者先將地圖索引映射到值，然後將第二個映射值映射到索引。

您可以使用std::lower_bound（二分查找）和兩個std::vector<std::pair<value, value> >做同樣的事情，但您需要確保所有數據都已排序。它將使用比兩個std::map更少的內存，但是你很可能會花更多的時間來確保數據被排序。

對於我的應用程序內存和速度是很重要的

你忘了開發時間。如果您的完美解決方案需要3個月的時間才能完成，那可能不值得。
你需要告訴你有多少內存，你使用的是什麼類型的數據，以及需要多少數據。
總是有平衡。「速度」或「記憶」。或者是中間的東西。

數億點

切換到64位的，購買額外的內存。或者將已排序的數據存儲在磁盤上（允許對部分加載的數據進行二進制搜索）並忘記速度，或嘗試使用「從標準輸入讀取，立即寫入標準輸出」方式進行處理。請注意，硬件比開發時間便宜。在不知道數據類型的情況下，不可能推薦其他任何東西。

來源

2012-02-24 21:38:01 SigTerm

索引映射的高效算法

回答

相關問題