在尋找完美的數據結構

每個數據結構都有它自己的時間複雜性。跳出你最大的是哈希表。插入，刪除和搜索的平均時間都是O（1）。但它確實是不變的時間，因爲可以通過多個代表來找到正確的位置。真正的問題是，如果空間不是問題，我們是否可以在一個操作中完成每個操作？在尋找完美的數據結構

最近我正在研究基數排序，並想出如何儘可能地加快它的速度。我決定做的一件事是做一個2字節的計數排序，因此你只需要循環一次。然後，我開始思考我以前使用的線索，整數在每次修改數字10次後遍歷。這似乎比我嘗試過的任何其他數據結構都要快，但希望使其更快。我今天所嘗試的是將樹狀結構視爲有保證的二級樹。每個節點有2^16（65536）個孩子。這樣我可以像這樣引用每個數字：root-> link [twoByte1] - > link [twoByte2]。其中twoByte1是前16位，2是他第二位。問題是，這是很多記憶。相反，我決定創建一個結構數組，並使用2^16 bool（uint8_t）值，並運行相同的問題。爲了解決這個問題，我做了以下結構。

struct trie { 
    unsigned int link[2048]; 
};

我決定使用2048個無符號整數（或簽名，不知道是否會有區別）。這樣我可以在查找過程中將每一位看作真/假值。爲了引用每個位置，我將採用前16個字節，並以前面的方式引用元素，但第二個元素將被32除以找出要使用的整數數組的哪個元素，並再次對該數字進行mod編碼通過32找出哪個位要看。以下是我用來引用它的代碼：

uint8_t getData (int data, uint16_t& dir, uint16_t& pos, uint8_t& x) { 
    dir = (data >> 0) & 0xffff; 
    pos = (data >> 16) & 0xffff; 
    x = pos/32; 
    return pos % 32; 
}

插入功能只是找到點並打開位。要做到這一點，我會從上面的函數中獲取數據，然後或者將特定位與1進行比較。與刪除類似，只有我會反轉位串，然後將其與其關閉。然後爲了搜索那個元素，我只返回特定的位。在這裏找到了如何清除該位的幫助：How do you set, clear, and toggle a single bit?下面是這三個函數的代碼。

void insert(trie *root, int data) { 
    uint16_t dir, pos; 
    uint8_t x, y = getData(data, dir, pos, x); 
    root[dir].link[x] |= 1 << y; 
} 
bool find(trie *root, int data) { 
    uint16_t dir, pos; 
    uint8_t x, y = getData(data, dir, pos, x); 
    return root[dir].link[x] & (1 << y); 
} 
void remove(trie *root, int data) { 
    uint16_t dir, pos; 
    uint8_t x, y = getData(data, dir, pos, x); 
    root[dir].link[x] &= ~(1 << y); 
}

從這裏就像初始化結構數組一樣簡單。重要的是，隨着元素數量的增加，數據結構將永遠不會進一步擴大。此外，在線程的情況下，因爲我只是在插入過程中打開位，所以我不認爲我需要同步任何線程。因此，它可以加快線程。你對此有什麼想法，我在這裏做了一個測試用例：http://ideone.com/McwWTV。我在運行在i7上的Linux機器上運行測試，並且每2.5秒就能處理2.5億個整數。

來源

2013-07-13 Kevin Melkowski

對於散列表，如果提前知道可能的輸入數據集（鍵），則可以生成完美散列函數。這樣就不會有任何碰撞。 – 2013-07-13 19:35:23

你的問題是什麼？ – delnan

這聽起來更像是你正在尋找http://codereview.stackexchange.com/而不是stackoverflow ... –

任何關於複雜性的討論都會在您對輸入量進行任何限制的時刻出現。時間複雜性的定義與當你耗盡所有可能的低懸果子時發生的事情有關。低懸的成果最顯着的例子是使用哈希數據結構的技術。哈希表不是O(1)，因爲隨意增加數據量，足夠的值將映射到同一個存儲桶。

這並不是說散列表沒有用處，而是說你不應該把它們包含在任何時間複雜度計算中。

就您提到的時空折衷而言，通常可能會使用指數量的空間來實現操作。例如，您可以使用2^n位置實現一個集合，其中n是輸入中可能的位數。然後插入一個值x該操作是s[x] = true，雖然存在如何將該集初始化爲空的問題，其本身可能需要指數時間。

我建議閱讀以欣賞時間複雜性的一件事是證明爲什麼最佳通用排序算法不會比O(n * log(n))更好。證明的本質是，如果你有一個算法來排序n數字，你基本上有一個算法來檢測你的輸入序列是否是可能的排列之一。如果是的話，那麼你就會吐出排序後的序列。

n!之間的一般決策問題的可能性不能比O(n * log(n))更快解決。

底線 - 你做的東西很酷，但它不是時間複雜性的改善。這只是性能上的調整，儘管它很重要。

來源

2013-07-13 20:48:57 necromancer

散列表是_amortized_O（1），就像向量推回是_amortized_O（1）。 –

@MooingDuck大哦，是最壞的情況。給我一個散列函數，我會給你一個任意數量的數據，將進入一個桶。如果你做了一個平均案例分析，假設你的散列函數將統一分配價值，那麼你可能會得到你所說的攤銷。說分期償還的'O（1）'實際上是一種濫用符號的方式。對於程序可能遇到的數據，運行時性能沒有保證。 – necromancer

@MooingDuck另外你的類比是絕對錯誤的。向量推回是真正的，非概率性的，最壞的情況是攤銷'O（1）'。哈希表根本不是，即使添加了任意數量的空間。 – necromancer

我不知道你問什麼，但我會以此爲一個問題：

真正的問題是，我們可以做的每一個操作都必須在只有一個操作，如果空間不是問題？

答案是肯定的，但是以一種相當理論化和無用的方式。想象一下，我們有一個無限位數組，b[i]。您可能想要插入到數據結構中的每個元素e都是一系列字節，因此它是一個任意大小的整數。要插入此元素，只需將b[e]設置爲1即可。要將其刪除，請將b[e]設置爲0。要檢查是否存在e，只需檢索b[e]的值。

這給你一個設置數據結構。如果我們用指針替換這些位，我們可以將它變成一個鍵值對應的映射（「哈希表」）。

來源

2013-07-13 21:28:14 Thomas

在尋找完美的數據結構

回答

相關問題