存儲一百萬個值的最佳數據結構？

請註明時間複雜度和最佳的數據結構來存儲這些值，當值是：存儲一百萬個值的最佳數據結構？

整數
字符串（詞典如排序）

我知道，當整數是在Counting sort優先一個小範圍。

謝謝。

編輯： 對不起，我問了一個不同的問題。實際問題是，如果整數是電話號碼（並且字符串是名稱），那麼存儲這些值的最佳數據結構是什麼，然後找到最佳排序算法。

來源

2010-08-23 understack

其他人聞到功課？ – 2010-08-23 19:23:20

按照現行標準，一百萬個項目是一個相當平均的數字 - 選擇（無雙關語）排序算法的常用標準很可能適用。 – 2010-08-23 19:24:27

@Justin - 是不是又一次呢？ @understack - SO社區不介意幫助做家庭作業的問題，如果我們可以通過其他方式在大學裏繼續生活，我相信我們會，但是我們希望看到在我們離開之前你已經做出了什麼努力爲你做功課（例如，我看過@ bubblesort和快速排序，但我不確定選擇哪種存儲機制的選項會更快）。 – Tommy 2010-08-23 19:27:11

看一看： Btrees和red-black trees。

你應該能夠找到這的開源實現。（請注意，我假設你要保持一個有序的結構，而不是隻一次排序和遺忘。）

來源

2010-08-23 20:38:44

排序算法維基鏈接：Sorting Algorithm Wiki

歸併排序和快速排序是相當不錯的，他們的n log n個最好的情況下。

來源

2010-08-23 19:22:06 Holystream

我想我沒有正確地問我的問題。重點在於存儲值。 – understack 2010-08-23 19:34:58

怎麼樣heap？相對容易實施，速度相當快。對於字符串，你可以使用Trie以及類似Burst類的東西，它應該是同類中最快的字符串排序算法。

來源

2010-08-23 20:49:58

對於大多數排序算法有就地版本，所以一個簡單的陣列就足夠了。對於字符串，你可以考慮一個http://en.wikipedia.org/wiki/Trie，這可以節省空間。正確的排序算法取決於很多因素，例如如果結果可能已經排序或部分排序。當然，如果你只有幾個不同的值，可以使用Countingsort，Bucketsort等。

來源

2010-08-23 20:50:13 Landei

在32位機，一百萬個整數可以容納4個百萬字節的陣列。 4MB並不是那麼多;它可以適應500次這個系統的內存（現代標準並不那麼強大）。一百萬個字符串將具有相同的大小，除了這些字符串的存儲空間之外;對於短字符串它仍然是沒有問題的，所以啜這一切在你甚至可以有一個指針數組持有一個整數，一個字符串的參考結構。它都將適合很好。只有當你處理的數據比那個數據多得多（例如，10億項）時，你才需要採取特殊的措施，數據結構明智。

對於分選許多事情，選擇的算法的O（Ñ日誌Ñ），而不是一個是O（Ñ ）。將O，當你有特別緊湊的鍵位，這是非常罕見的做法（ñ）算法是唯一有用的。選擇O中的哪個算法（ n log n）是平衡速度和其他良好性能（如穩定性）的問題。

如果您真的這樣做，請使用具有適當索引的數據庫，而不是一個人手動完成。

來源

2010-08-23 21:09:00

存儲一百萬個值的最佳數據結構？

回答

相關問題