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

Question

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

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

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

(Другое решение - отслеживать количество строк в дереве с помощью атрибута, но, поскольку я хочу вернуть только часть дерева, это тоже не идеальное решение)

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

Два очевидных варианта: ArrayList и LinkedList.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: add: 5.52ms;повторение: 7,66 мс (50000 строк)
LinkedList: добавление: 7,79 мс;итерация: 8,32 мс (50000 строк)

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

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

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

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

ArrayList: добавление: 0,45 мс;повторение: 0,60 мс (50000 строк)
LinkedList: добавление: 0,84 мс;итерация: 5,35 мс (50000 строк)

ArrayList: добавление: 0,52 мс;итерация: 0,72 мс (50000 строк)
LinkedList: добавление: 0,81 мс;итерация: 5,57 мс (50000 строк)

ArrayList: добавить: 3,77 мс;итерация: 0,71 мс (50000 строк)
LinkedList: добавить: 3,35 мс;итерация: 0,93 мс (50000 строк)

ArrayList: добавление: 3,39 мс;итерация: 0,87 мс (50000 строк)
LinkedList: добавить: 3,38 мс;итерация: 0,86 мс (50000 строк)

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

Answer 4

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