Лучший способ хранить и получать доступ к 120000 слов в Java

Question

Я программирую Java-приложение, которое читает только текстовые файлы (.txt). Эти файлы могут содержать более 120000 слов.

Приложение должно хранить все +120 000 слов. Ему нужно назвать их word_1, word_2 и т. Д. И ему также нужно получить доступ к этим словам, чтобы выполнять с ними различные методы.

Все методы связаны со строками. Например, будет вызван метод для определения количества букв в word_80. Будет вызван другой метод, чтобы сказать, какие именно буквы есть в word_2200.

Кроме того, некоторые методы будут сравнивать два слова. Например, будет вызван метод для сравнения word_80 с word_2200, и его необходимо вернуть, у которого больше букв. Для сравнения word_80 с word_2200 будет вызван другой метод, который должен возвращать конкретные буквы, которые разделяют оба слова.

Мой вопрос: поскольку я работаю почти исключительно со строками, лучше ли хранить эти слова в одном большом ArrayList? Несколько маленьких ArrayLists? Или я должен использовать одну из многих других возможностей хранения, таких как Векторы, HashSets, LinkedLists?

Мои две основные проблемы: 1.) скорость доступа и 2.) наличие в моем распоряжении максимально возможного количества предварительно созданных методов.

Заранее спасибо за помощь !!

---

Вау! Спасибо всем за столь быстрый ответ на мой вопрос. Все ваши предложения очень помогли мне. Я продумываю и рассматриваю все варианты, указанные в вашем отзыве.

Пожалуйста, прости меня за любую нечеткость; и позвольте мне ответить на ваши вопросы:

1. Q) Английский?
   А) Текстовые файлы на самом деле книги, написанные на английском языке. Появление слова на втором языке будет редким, но не невозможным. Я бы поставил процент неанглоязычных слов в текстовых файлах на 0,0001%

2. Q) Домашнее задание?
   А) Я с улыбкой смотрю на формулировку своего вопроса сейчас. Да, это похоже на школьное задание. Но нет, это не домашнее задание.

3. Q) Дубликаты?
   А) да. И, вероятно, каждые пять или около того слов с учетом союзов, статей и т. Д.

4. Q) Доступ?
   А) И случайные, и последовательные. Конечно, возможно, что метод найдет слово в случайном порядке. В равной степени возможно, что метод захочет последовательно найти подходящее слово между word_1 и word_120000. Что приводит к последнему вопросу ...

5. Q) Перебирать весь список?
   А) Да.

Кроме того, я планирую расширить эту программу для выполнения многих других методов над словами. Я снова прошу прощения за мою нечеткость. (Детали действительно имеют значение, не так ли?)

Ура!

Answer 1

Я бы сохранил их в одном большом ArrayList и позже позаботился о (возможно, ненужных) оптимизациях.

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

На самом деле, если вы можете установить верхнюю границу для количества слов и вам не нужны какие-либо необычные операции List, я бы выбрал обычный (нативный) массив строковых объектов с целым числом, содержащим фактический номер. Вероятно, это будет быстрее, чем подход на основе классов.

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

Примечание. Я не сравнивал собственные массивы с ArrayLists. Они могут быть такими же быстрыми, как и нативные массивы, поэтому вы должны проверить это сами, если у вас меньше слепой веры в мои способности, чем у меня: -).

Если они do оказываются такими же быстрыми (или даже близкими), дополнительных преимуществ (например, расширяемости) может быть достаточно, чтобы оправдать их использование.

Answer 2

Просто подтверждение предположений Пакс с очень наивным тестом

public static void main(String[] args)
{
    int size = 120000;
    String[] arr = new String[size];
    ArrayList al = new ArrayList(size);
    for (int i = 0; i < size; i++)
    {
        String put = Integer.toHexString(i).toString();
        // System.out.print(put + " ");
        al.add(put);
        arr[i] = put;
    }

    Random rand = new Random();
    Date start = new Date();
    for (int i = 0; i < 10000000; i++)
    {
        int get = rand.nextInt(size);
        String fetch = arr[get];

    }
    Date end = new Date();
    long diff = end.getTime() - start.getTime();
    System.out.println("array access took " + diff + " ms");

    start = new Date();
    for (int i = 0; i < 10000000; i++)
    {
        int get = rand.nextInt(size);
        String fetch = (String) al.get(get);

    }
    end = new Date();
    diff = end.getTime() - start.getTime();
    System.out.println("array list access took " + diff + " ms");
}

и вывод:
доступ к массиву занял 578 мс
доступ к списку массивов занял 907 мс

запуск его несколько раз реальное время, кажется, несколько различается, но обычно доступ к массиву происходит на 200–400 мс быстрее, более 10 000 000 итераций.

Answer 3

Если вы будете обращаться к этим строкам последовательно, лучшим выбором будет LinkedList.

Для произвольного доступа ArrayLists имеют хороший обмен памятью / скорость доступа.

Answer 4

Если вы стремитесь к быстрому обходу, а также к компактному размеру, используйте DAWG (Направленный ациклический граф слов). Эта структура данных берет идею дерева и улучшает ее, находя и выявляя общие суффиксы, а также общие префиксы.

http://en.wikipedia.org/wiki/Directed_acyclic_word_graph

Answer 5

Мой дубль:

Для непоточной программы Arraylist всегда самый быстрый и простой.

Для многопоточной программы java.util.concurrent.ConcurrentHashMap или java.util.concurrent.ConcurrentSkipListMap является отличным. Возможно, позже вы захотите разрешить потоки для одновременного выполнения нескольких запросов к этой огромной вещи.

Answer 6

Единственным преимуществом связанного списка над массивом или списком массивов будет наличие вставок и удалений в произвольных местах. Я не думаю, что это так: вы читаете документ и строите список по порядку.

Я ДУМАЮ, что когда в оригинальном постере говорилось о поиске "word_2200", он имел в виду просто 2200-е слово в документе, а не то, что с каждым словом связаны произвольные метки. Если это так, то все, что ему нужно, это индексированный доступ ко всем словам. Следовательно, массив или список массивов. Если действительно есть что-то более сложное, если одно слово может быть помечено «word_2200», а следующее слово - «foobar_42» или что-то подобное, тогда да, ему понадобится более сложная структура.

Эй, вы хотите дать нам подсказку, ПОЧЕМУ вы хотите сделать что-нибудь из этого? Мне трудно вспомнить последний раз, когда я сказал себе: «Эй, мне интересно, длиннее ли 1237-е слово в этом документе, которое я читаю, или 842-е слово?»

Answer 7

Как насчет корня дерева или Патрисии Три?

http://en.wikipedia.org/wiki/Radix_tree

Answer 8

Зависит от того, в чем проблема - скорость или память.

Если это память, минимальное решение - написать функцию getWord (n), которая сканирует весь файл при каждом запуске и извлекает слово n.

Теперь - это не очень хорошее решение. Лучшее решение - решить, сколько памяти вы хотите использовать: скажем, 1000 элементов. Сканируйте файл на наличие слов один раз при запуске приложения и сохраняйте серию закладок, содержащих номер слова и позицию в файле, в котором оно находится. Сделайте это так, чтобы закладки были более или менее равномерно распределены файл.

Затем откройте файл для произвольного доступа. Функция getWord (n) теперь просматривает закладки, чтобы найти самое большое слово # <= n (используйте бинарный поиск), выполняет поиск, чтобы добраться до указанного места, и сканирует файл, считая слова, чтобы найти запрошенное слово. </p>

Еще более быстрое решение, использующее больше памяти, состоит в том, чтобы создать своего рода кеш для блоков - на основе того, что запросы getWord () обычно проходят в кластерах. Вы можете настроить все так, чтобы, если кто-то запрашивает слово # X, а его нет в закладках, вы ищете его и помещаете в закладки, сохраняя память путем объединения той закладки, которая использовалась меньше всего.

И так далее. На самом деле это зависит от того, в чем проблема - от того, какие закономерности возрождения вероятны.

Answer 9

Я не понимаю, почему так много людей предлагают Arraylist или тому подобное, поскольку вы не упоминаете, что вам когда-либо приходилось перебирать весь список. Кроме того, кажется, что вы хотите получить к ним доступ в виде пар ключ / значение ("word_348" = "pedantic").

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

http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html

Answer 10

ArrayList / Vector, если порядок имеет значение (кажется, поскольку вы называете слова «word_xxx»), или HashTable / HashMap, если это не так.

Я оставлю упражнение, чтобы выяснить, почему вы захотите использовать ArrayList против Vector или HashTable против HashMap, поскольку у меня есть подозрение, что это ваша домашняя работа. Проверьте Javadocs.

Вы не получите никаких методов, которые помогут вам, как вы просили в приведенных выше примерах, из вашего класса Collections Framework, поскольку ни один из них не выполняет операции сравнения строк. Если вы просто не хотите упорядочить их в алфавитном порядке или что-то подобное, в этом случае вы будете использовать одну из реализаций дерева в структуре коллекций.