查找數字最快的方法是什麼？

我正在存儲數字（範圍從1到小於100,000），然後以一個數字作爲參數進行調用，並且必須將其用作查找中的鍵。在過去，當獲取短char *字符串作爲查找鍵時，我使用了一個trie實現。我想知道我是否也應該使用一個數字，如果也許有一些更快的方式來研究/考慮/調查？查找數字最快的方法是什麼？

來源

2013-10-03 Palace Chan

這真的取決於你想要做什麼。

如果你有很多內存，你可以建立一個包含100,000個元素的數組，並且只需要在查看錶時使用該數字作爲索引。這可能是最快的方法（查找都是具有極低常數因子的O（1）），儘管它並不是最高的內存效率。如果內存稀少，一個標準的哈希表將是一個很好的折衷;您將獲得所有操作的預期O（1）運行時間。

如果您需要能夠執行「什麼數字最接近x？」形式的查詢，那麼您可能需要使用一個平衡二叉搜索樹來保存整數。這可以讓你在時間O（log n）中進行後繼和前任搜索和查找。如果您有興趣嘗試更復雜的數據結構，則可以使用van Emde Boas tree，它可以在時間O（log log U）中進行插入，刪除，查找，前置和後繼搜索，其中U是可能的最大值值。

希望這會有所幫助！

來源

2013-10-03 00:18:45 templatetypedef

哦直線陣列不是一個壞主意！我其實知道100000是一個合理的上限 –

你必須考慮到，如果多個對象有一個共同的密鑰，碰撞解決的成本可能會相當大。 – 3yakuya

哦不，這是不是這種情況..對象的鑰匙是唯一的 –

我會建議使用散列表。每個值都將放置在一個可以使用密鑰引用的獨特存儲區中。如果您的數據可以按照這種方式進行組織，這將是最快的查找方式。

來源

2013-10-03 00:18:11 TGH

事情是散列的代價是非平凡的，即使我使用超快速哈希像FNV，而通常與短的字符串或知道我的密鑰的屬性（他們是小數字）我可以利用小試避免緩存未命中的跳轉很少 –

散列表版本之一是直接尋址表，其中「散列」成本實際上是微不足道的。它可以正常工作，除非有多個對象具有相同的密鑰的可能性很高。 – 3yakuya

價值的關鍵是獨一無二的，直接尋址表是一樣的上述答案是的，我同意將是最快的方式 –

查找數字最快的方法是什麼？

回答

相關問題