Каков самый быстрый способ хранить неизвестное количество строк в java?

Question

Я хочу сохранить неизвестное количество строк, а затем прочитать их в том порядке, в котором они были добавлены. Как я сказал, что только особенности мне нужно это:

• Возможность добавить неизвестное количество строк без замедления из-за изменения размера
• Возможность читать элементы в порядке их добавления

Проблема в том, что я хочу вывести строки из части trie. Поэтому подсчет строк перед их возвратом удвоил бы количество времени, необходимого для операции.

(Другое решение было бы следить за количество строк в использовании синтаксического дерева атрибута, но, как я хочу вернуть только часть из синтаксического дерева, это не идеальное решение либо)

Answer 1

ArrayList обычно быстрее, чем LinkedList. Если вы не укажете соответствующий размер, каждый раз, когда мощность будет исчерпана, ему придется переназначить новый массив (с двойным размером) и скопировать элементы в новый массив.

Вы можете использовать LinkedList, чтобы избежать этой стоимости, но среднее время, вероятно, будет больше.

Независимо от используемой вами коллекции, если у вас недостаточно памяти, GC запустится, что также может привести к некоторой задержке. «Неизвестная сумма», без каких-либо ограничений, невозможно хранить в любой коллекции в памяти. Если «неизвестный» может быть очень большим и запретить использование коллекции в памяти, вам понадобится файл или база данных.

Answer 2

LinkedList<string> звуков как хорошая ставка для меня ...

• Поддерживает порядок
• O (1) добавление в голову или хвост
• O (1) удаление в голову или хвост
• Дешевая итерация

Это дорого, чтобы получить произвольный элемент, что является обычной причиной не использовать его ... но похоже, что это не проблема в вашем случае.

Answer 3

Используйте реализацию интерфейса List. Это generallyconsidered что ArrayList это лучшая коллекция общего назначения для использования, так что-то же просто, как это для хранения ваших строк:

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

Answer 4

два очевидных варианта является 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,66 мс (50000 строк)
LinkedList: add: 7.79ms; итерация: 8.32ms (50000 строк)

Это было на компьютере с процессором Intel Core2 Quad Q6600 с тактовой частотой 2,4 ГГц.

Обратите внимание, что это измеряет общее время. Он не измеряет изменение времени добавления отдельных строк, что я ожидал бы выше для ArrayList, чем для LinkedList, из-за необходимости перераспределения внутреннего массива.

EDIT: Если я изменить main повторить тест пять раз подряд, с вызовом System.gc() после каждого вызова benchmark, то я получить некоторые интересные результаты:

ArrayList: добавить: 5.84ms ; итерация: 7,88 мс (50000 строк)
LinkedList: add: 7.24ms; итерация: 8,27 мс (50000 строк)

ArrayList: add: 0.45ms; итерация: 0,60 мс (50000 строк)
LinkedList: add: 0.84ms; итерация: 5,35 мс (50000 строк)

ArrayList: add: 0.52ms; итерация: 0,72 мс (50000 строк)
LinkedList: add: 0.81ms; итерация: 5,57 мс (50000 строк)

ArrayList: add: 3.77ms; итерация: 0,71 мс (50000 строк)
LinkedList: add: 3.35ms; итерация: 0,93 мс (50000 строк)

ArrayList: add: 3.39ms; итерация: 0,87 мс (50000 строк)
LinkedList: add: 3.38ms; итерация: 0,86 мс (50000 строк)

Возможно, это связано с кэшированием процессором. Обратите внимание: LinkedList может быть немного быстрее (например, последним для итераций) для добавления строк, хотя он также может быть намного медленнее. Итерация также может быть значительно медленнее для LinkedList, также, вероятно, из-за отсутствия локальности.