Эффективный в памяти большой массив слов - PullRequest
3 голосов
/ 12 августа 2011

Я ищу структуру данных Java для хранения большого текста (около миллиона слов), чтобы я мог получить слово по индексу (например, получить слово 531467).

ПроблемаString [] или ArrayList в том, что они занимают слишком много памяти - около 40 байт на слово в моей среде.

Я думал об использовании String [], где каждый элемент представляет собой кусок из 10 слов, соединенныхпространство.Это намного более эффективно использует память - около 20 байт на слово;но доступ намного медленнее.

Есть ли более эффективный способ решения этой проблемы?

Ответы [ 9 ]

3 голосов
/ 12 августа 2011

Как уже упоминал Джон Скит, 40 Мб не слишком велики.

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

Вы можете использовать String.intern () [1]. Это объединит вашу строку и вернет ссылку на уже существующую строку.

intern () довольно медленный, так что вы можете заменить его на HashMap, который сделает то же самое для вас.

[1] http://download.oracle.com/javase/6/docs/api/java/lang/String.html#intern%28%29

2 голосов
/ 12 августа 2011

Сохранить все слова в одной строке:

class WordList {

    private final String content;
    private final int[] indices;

    public WordList(Collection<String> words) {
        StringBuilder buf = new StringBuilder();
        indices = new int[words.size()];
        int currentWordIndex = 0;
        int previousPosition = 0;
        for (String word : words) {
            buf.append(word);
            indices[currentWordIndex++] = previousPosition;
            previousPosition += word.length();
        }
        content = buf.toString();
    }

    public String wordAt(int index) {
        if (index == indices.length - 1) return content.substring(indices[index]);
        return content.substring(indices[index], indices[index + 1]);
    }

    public static void main(String... args) {
        WordList list = new WordList(Arrays.asList(args));
        for (int i = 0; i < args.length; ++i) {
            System.out.printf("Word %d: %s%n", i, list.wordAt(i));
        }
    }

}

Помимо символов, которые они содержат, каждое слово использует служебную информацию в четыре байта, используя это решение (запись в indices). Извлечение слова с помощью wordAt всегда будет выделять новую строку; вы могли бы избежать этого, сохранив toString() StringBuilder, а не самого компоновщика, хотя он использует больше памяти при создании.

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

2 голосов
/ 12 августа 2011

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

1 голос
/ 17 августа 2011

ОК, я экспериментировал с несколькими вашими предложениями, и вот мои результаты (я проверил (Runtime.getRuntime (). TotalMemory () - Runtime.getRuntime (). FreeMemory ()) перед заполнением массива и проверил снова после заполнения массива и gc ()):

  • Оригинал (массив строк): 54 байта / слово (не 40, как я ошибочно написал)
  • Мое решение (массив кусков строк, разделенных пробелами):
    • 2 слова на кусок - 36 ч / б (но недопустимо исполнение)
    • 10 слов на кусок - 18 ч / б
    • 100 слов на кусок - 14 ч / б
  • массив байтов - 40 ч / б
  • массив символов - 36 ч / б
  • HashMap, либо сопоставление строки с самим собой, либо сопоставление строки с ее индексом - 26 ч / б
    • (не уверен, что я правильно это реализовал)
  • стажер - 10 ч / б
  • базовый уровень (пустой массив) - 4 ч / б

Средняя длина слова составляет около 3 символов, и большинство символов не ASCII, поэтому, вероятно, около 6 байтов. Итак, похоже, что стажер близок к оптимальному. Это имеет смысл, так как это набор слов, и многие слова появляются гораздо чаще, чем один раз.

1 голос
/ 12 августа 2011
-XX:+UseCompressedStrings

Используйте байт [] для строк, которые могут быть представлены как чистый ASCII. (Представлено в Java 6, обновление 21, выпуск Performance)

http://www.oracle.com/technetwork/java/javase/tech/vmoptions-jsp-140102.html

Похоже, интересная статья: http://www.javamex.com/tutorials/memory/string_saving_memory.shtml

Я слышал, что веревки довольно хороши с точки зрения скорости хранения больших струн, хотя и не уверены в памяти. Но вы можете проверить это. http://ahmadsoft.org/ropes/ http://en.wikipedia.org/wiki/Rope_%28computer_science%29

1 голос
/ 12 августа 2011

Вы можете создать такую ​​структуру данных:

  • List<string> wordlist
  • Dictionary<string, int> tsildrow // for reverse lookup while building the structure
  • List<int> wordindex

wordlist будет содержать список всех (уникальных) слов, tsildrow даст индекс слова в wordlist, а wordindex сообщит вам индекс в wordlist определенного индекса в вашем тексте.

Вы будете действовать следующим образом:

for word in text:
    if not word in tsildrow:
        wordlist.append(word)
        tsildrow.add(word, wordlist.last_index)
    wordindex.append(tsildrow[word])

это заполняет вашу структуру данных. Теперь, чтобы найти слово по индексу 531467:

print wordlist[wordindex[531467]]

Вы можете воспроизвести весь текст так:

for index in wordindex:
    print wordlist[index] + ' '

за исключением того, что у вас все еще будет проблема с пунктуацией и т. Д. *

если вы больше не будете добавлять слова (т. Е. Ваш текст стабилен), вы можете удалить tsildrow, чтобы освободить часть памяти, если вас это беспокоит.

1 голос
/ 12 августа 2011

Вместо этого можно хранить байтовые массивы с текстом, закодированным в UTF-8:

byte[][] words = ...;

Тогда:

public String getWord(int index)
{
   return new String(words[index], "UTF-8");
}

Это будет меньше двумя способами:

  • Данные для каждой строки непосредственно в байте [], а не строка, имеющая пару целочисленных членов и ссылку на отдельный объект char []
  • Если ваш текст в основном-ASCII, вы получите выгоду от UTF-8, использующего один байт на символ для этих символов ASCII

Хотя я бы не рекомендовал такой подход ...снова это будет медленнее при доступе, так как ему нужно каждый раз создавать новый String.По сути, если вам нужен миллион строковых объектов (так что вы не хотите каждый раз платить штраф за восстановление), вам придется использовать память для миллиона строковых объектов ...

0 голосов
/ 12 августа 2011

Если у вас есть мобильное устройство, вы можете использовать TIntArrayList, который будет использовать 4 байта на значение типа int. Если вы используете один индекс для каждого слова, потребуется пара МБ. Вы также можете использовать int[]

Если у вас есть компьютер или сервер, это тривиальный объем памяти. Стоимость памяти около £ 6 за ГБ или 1 цент за МБ.

0 голосов
/ 12 августа 2011

Я бы, вероятно, подумал об использовании файла со словами фиксированного размера или с каким-либо индексом. FileInputStream с пропуском может быть довольно эффективным

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