HashMap на Java, 100 миллионов записей

Question

Я хочу сохранить 100 миллионов терминов и их частоты (в текстовой базе данных) в HashMap <String, Double>. Это дает мне ошибку «Недостаточно памяти». Я пытался увеличить кучу пространства до -Xmx15000M. Однако он работает полчаса, затем снова выдает то же исключение. Размер файла, из которого я пытаюсь прочитать слова и частоты, составляет 1,7 ГБ.

Любая помощь будет высоко ценится.

Спасибо :-)

Answer 1

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

В зависимости от ввода, дерево Патриции может быть даже лучше.

(Кроме того, если это действительно такслова из естественного языка, вы уверены, что вам действительно нужно 100 000 000 записей? Большинство часто используемых слов удивительно мало, коммерческие решения (предсказание слов, исправление орфографии) редко используют более 100 000 слов независимо от языка.)

Answer 2

Ваша проблема в том, что 1,7 ГБ необработанного текста - это более 1500 МБ, даже без дополнительных затрат, добавляемых отдельными строковыми объектами. Для огромных отображений вы должны использовать либо базу данных, либо карту с файловой поддержкой, они будут использовать дисковую память вместо кучи.

Обновление

Я не думаю, что выделение 15 ГБ для кучи возможно для большинства jvms. Это не будет работать с любой 32-битной JVM, и я не думаю, что 64-битная JVM будет работать также. 15 ГБ памяти должны работать на 64-битной jvm при наличии достаточного объема оперативной памяти.

Answer 3

Файл размером 1,7 ГБ - это относительно небольшой файл для хранения и сохранения в ОЗУ. Я делаю это с гораздо большими файлами и сохраняю их в памяти без проблем. База данных может использоваться, но может быть излишней или может быть идеальной в зависимости от того, что вы планируете делать с данными.

Как уже говорили другие, на естественном языке, вероятно, будет относительно небольшое количество уникальных значений, поэтому карта на самом деле не будет такой большой. Я не стал бы использовать java.util.HashMap, поскольку он очень неэффективен с точки зрения использования памяти , особенно при хранении примитивных значений, таких как целые числа. java.util.HashMap хранит примитивы как объекты. Он также хранит каждое значение внутри объекта HashMap.Entry, который тратит впустую память. Из-за этих двух факторов java.util.HashMap использует намного больше памяти, чем альтернативы, такие как Trove , Fastutil и другие:

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

Как уже упоминалось, есть несколько реализаций карт, у которых нет этих проблем. Поскольку вы храните числа на своей карте, дополнительное преимущество заключается в том, что вы получите повышение производительности, поскольку нет необходимости постоянно переключаться между объектами и примитивами (т. Е. Помещать / распаковывать), когда вы вводите новые значения в карту или обновляете старые ценности. Эталон различных примитивных хэш-карт, которые лучше подходят для больших объемов данных, можно найти в этом посте в Руководстве по настройке производительности Java :

Answer 4

С 100 миллионами терминов вы почти наверняка превысили предел того, что должно храниться в памяти.Храните свои термины в какой-то базе данных.Либо используйте коммерческую базу данных, либо напишите что-нибудь, что позволит вам получить доступ к файлу, чтобы получить необходимую информацию.Если формат файла, который у вас есть, не позволяет быстро получить доступ к файлу, преобразуйте его в тот, который имеет, например, установите для каждой записи фиксированный размер, чтобы вы могли мгновенно рассчитать смещение файла для любого номера записи.Сортировка записей позволит вам быстро выполнить бинарный поиск.Вы также можете написать код, чтобы значительно ускорить доступ к файлам без необходимости хранить весь файл в памяти.

Answer 5

Если вы хотите просто облегченное хранилище KeyValue (Map), я бы хотел использовать Redis. Это очень быстро и имеет возможность сохранять данные, если это необходимо. Единственным недостатком является то, что вам нужно запустить магазин Redis на машине с Linux.

Если вы ограничены в Windows, MongoDB является хорошим вариантом, если вы можете запустить его в 64-битной версии.

Answer 6

Вы также можете попробовать остановить, чтобы увеличить количество дубликатов.

Например, кошка = кошка = кошка = кошка

или

плавать = плавать = плавать

попробуйте поискать в Google "Porter Stemmer"

Answer 7

Удалите HashMap и загрузите все эти данные в HBase или в один из других хранилищ данных NoSQL и запишите свои запросы в терминах MapReduce операций. Это подход, используемый Google Search и многими другими сайтами, работающими с огромными объемами данных. Он доказал, что масштабируется практически до бесконечного размера.

Answer 8

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

public class Phrase {
  private final String[] interned;

  public Phrase(String phrase) {
    String[] tmp = phrase.split(phrase, "\\s");

    this.interned = new String[tmp.length];

    for (int i=0; i<tmp.length; ++i) {
      this.interned[i] = tmp[i].intern();
    }
  }

  public boolean equals(Object o) { /* TODO */ }
  public int hashCode() { /* TODO */ }
}

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

Answer 9

Trove THashMap использует намного меньше памяти. Тем не менее, сомневаюсь, что этого будет достаточно для уменьшения размера. Вам нужно где-то еще хранить эту информацию для поиска, кроме строго в памяти.

Answer 10

В Java у объекта как минимум 16 байтов Размер, прежде чем рассмотреть, какой другой контент он содержит.

1e8 элементов в хэш-карте имеют заниженное требование к размеру 1e8 * 2 * 16 байт, и это предполагает, что ваши ключи и значения являются числами, поэтому требуется несколько ГБ доступной кучи в вашей куче и с вашего компьютера.

Строка - это объект, содержащий массив символов, поэтому ваши строки как уже упоминалось многими выше, может быть больше, чем двойной объект например, следовательно, вам нужно больше памяти, доступной для куча.

Обратите внимание, что программы начинают работать плохо, когда вы приближаетесь к пределу вашего компьютера тоже.

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