在java中存儲未知數量字符串的最快方法是什麼？

我想存儲未知數量的字符串，然後按照它們添加的順序讀取它們。正如我所說的，我需要的唯一特點是：在java中存儲未知數量字符串的最快方法是什麼？

可能性添加字符串的未知量，而不會減緩，因爲調整
可能性讀取它們添加

順序的元素向下問題是我想從一個trie的一部分輸出字符串。因此，在返回字符串之前計算字符串會使操作所需的時間增加一倍。

（另一個解決方案是使用屬性來跟蹤線索串的數量而是我想回到線索的只是一部分，這是不是一個完美的解決辦法）

2012-02-26 w1th0utnam3

您考慮過哪些選項？ – 2012-02-26 18:50:27

預期平均有多少（數量級）的琴絃？閱讀前在運行時已知數字嗎？我們是在談論一個很難實時的應用程序，還是隻是過早地進行優化？我可以根據每個問題的答案給出截然不同的答案（以及受過良好教育的猜測），並且可能還有更多因素。此外，唯一的答案是「哪個更快？」是「嘗試和配置！」。 – delnan 2012-02-26 18:51:06

@delnan經過一些測試，似乎ArrayList速度更快。如果有不同的可能性，你可以告訴我他們每一個的速度。 – w1th0utnam3 2012-02-26 20:58:11

ArrayList通常比LinkedList更快。如果你沒有指定一個合適的大小，每次容量耗盡時，它將不得不重新分配一個新的數組（雙倍大小），然後將這些元素複製到一個新的數組中。

您可以使用LinkedList來避免這種成本，但平均時間可能會更長。

無論您使用的是什麼樣的集合，如果您沒有足夠的內存，GC會觸發，這也會引入一些延遲。「未知數量」沒有任何限制，不可能存儲在任何內存中。如果「未知」可能非常大，並且禁止使用內存中的集合，那麼您將不得不使用文件或數據庫。

來源

2012-02-26 18:53:16

LinkedList<string>聲音像一個不錯的選擇，我...

維持秩序
O（1）除在頭部或尾部
O（1）去除在頭部或尾部
廉價的迭代

得到一個任意元素是昂貴的，這是不使用它的正常原因......但它聽起來像這不是你的情況的問題。

來源

2012-02-26 18:50:21

當然，複雜性並不是一切。假定，爲了論證的緣故，OP嚴重需要N-M字符串的最快（如以毫秒爲單位）的方法。如果在讀取第一個字符串之前已知實際數字，則不需要調整數組大小並且是單個分配。類似地，如果M相當小，那麼可以通過僅考慮最壞情況的大小來避免重新分配。可能有更多的例外。我並沒有反對你的回答或任何其他答案，只針對這種問題（「我需要做X;我不知道Y和Z，但我真的需要加快速度！」）。 – delnan 2012-02-26 18:55:50

對於基本操作，[LinkedList比ArrayList慢得多]（http://ideone.com/Uq7oc）。 'LinkedList'爲每個元素創建一個新的對象，這比'ArrayList'做的工作要多。 – 2012-02-26 19:21:03

儘管'LinkedList'可能會顯示更穩定的添加時間，但用於插入許多元素的'LinkedList'的整體性能似乎比'ArrayList'稍差。（請參閱我的答案以獲得一些基準測試結果。）'LinkedList'的迭代速度也稍慢（使用迭代器 - 使用顯式索引進行迭代會慢得多）;以下引用並不像索引到數組中那麼快。 – 2012-02-26 19:35:07

使用List接口的實現。這是generally considered是ArrayList是最好的通用集合使用，因此用於存儲你的字符串做這樣簡單的東西：

List<String> stringList = new ArrayList<String>();

來源

2012-02-26 18:53:46

兩個明顯的選擇是ArrayList和LinkedList。 A LinkedList似乎比ArrayList稍慢。這裏是我的基準測試代碼：

import java.util.*; 

public class ListTest { 
    private static final int N = 50000; 
    private static final float NANO_TO_MILLI = 1.0e-6f; 

    public static void main(String[] args) { 
     String[] strings = new String[N]; 
     for (int i = 0; i < N; ++i) { 
      strings[i] = Integer.toString(i); 
     } 

     System.out.print("ArrayList: "); 
     benchmark(strings, new ArrayList<String>()); 

     System.out.print("LinkedList: "); 
     benchmark(strings, new LinkedList<String>()); 
    } 

    private static void benchmark(String[] strings, List<String> list) { 
     // measure how long it takes to add the strings 
     long start = System.nanoTime(); 
     for (String s : strings) { 
      list.add(s); 
     } 
     long addTime = System.nanoTime() - start; 

     // measure how long it takes to iterate the list 
     start = System.nanoTime(); 
     int i = 0; 
     for (String s : list) { 
      ++i; 
     } 
     long iterateTime = System.nanoTime() - start; 

     // report the results 
     System.out.println(String.format("add: %.2fms; iterate: %.2fms (%d strings)", 
      addTime * NANO_TO_MILLI, 
      iterateTime * NANO_TO_MILLI, 
      i)); 
    } 
}

，這裏是一個典型的運行結果：

的ArrayList：地址：5.52ms;迭代：7.66ms（50000個字符串）
LinkedList：add：7.79ms;迭代：8。32毫秒（50000字符串）

這是在Windows機器上使用Intel Core2 Quad Q6600 2.4GHz cpu。

請注意，這隻能衡量整個時間。它不會測量單個字符串添加時間的變化，由於需要重新分配內部數組，因此我認爲ArrayList會比LinkedList更高。

編輯：如果我修改main重複五次測試成一排，通過調用System.gc()每次調用benchmark後，然後我得到了一些有趣的結果：

的ArrayList：地址：5.84ms ;迭代：7.84ms（50000字符串）
LinkedList：add：7.24ms;迭代次數：8.27ms（50000個字符串）

ArrayList：add：0.45ms;迭代：0.60ms（50000個字符串）
LinkedList：add：0.84ms;迭代次數：5.35ms（50000個字符串）

ArrayList：add：0.52ms;迭代：0.72ms（50000字符串）
LinkedList：add：0.81ms;迭代次數：5.57ms（50000個字符串）

ArrayList：add：3.77ms;迭代：0.71ms（50000個字符串）
LinkedList：add：3.35ms;迭代：0.93ms（50000個字符串）

ArrayList：add：3.39ms;迭代：0.87ms（50000字符串）
LinkedList：add：3.38ms;迭代：0.86ms（50000字符串）

這可能是由於cpu緩存。請注意，LinkedList可以稍快（例如，最後一次迭代）添加字符串，但它也可能慢得多。對於LinkedList，迭代也可能會大大減慢，也可能是因爲缺乏局部性。

來源

2012-02-26 19:29:42

感謝您的發佈。目前我使用的是ArrayList，所以我會堅持下去。 – w1th0utnam3 2012-02-26 20:33:46

在java中存儲未知數量字符串的最快方法是什麼？

回答

相關問題