Я хочу хранить 100 миллионов терминов и их частоты (в текстовой базе данных) в HashMap <String, Double>. Это дает мне ошибку "Недостаточно памяти". Я попытался увеличить кучу пространства до -Xmx15000M. Однако он проходит полчаса, а затем снова бросает одно и то же исключение. Размер файла, с которого я пытаюсь читать слова и частоты, составляет 1,7 ГБ.
Любая помощь будет высоко оценена.
Спасибо:-)
Для текстовой обработки ответ обычно является деревом, а не hashmap, если вы можете жить с более длительным временем поиска. Эта структура достаточно эффективна для памяти для естественных языков, где многие слова имеют общие начальные строки.
В зависимости от ввода дерево Патрисии может быть еще лучше.
(Кроме того, если это действительно слова с естественного языка, вы уверены, что вам действительно нужно 100 000 000 записей? Большинство часто используемых слов на удивление низкое, коммерческие решения (предсказание слов, коррекция орфографии) редко используют более 100 000 слов независимо от языка.)
Ваша проблема заключается в том, что сырой текст объемом 1,7 Гбайт составляет более 1500 МБ, даже без накладных расходов, добавленных отдельными строковыми объектами. Для огромных сопоставлений вам нужно либо использовать базу данных, либо карту с поддержкой файлов, это будет использовать дисковое пространство вместо кучи.
Обновление
Я не думаю, что выделение 15 ГБ для кучи возможно для большинства jvms. Он не будет работать с любым 32-битным jvm, и я не думаю, что будет работать 64-битный jvm. 15 ГБ памяти должны работать на 64-битном jvm, когда доступно достаточное количество ОЗУ.
1,7 ГБ файл является относительно небольшим файлом для этого и хранить в ОЗУ. Я делаю это с гораздо большими файлами и сохраняю их в памяти без проблем. База данных может быть использована, но может быть чрезмерной или может быть идеальной в зависимости от того, что вы планируете делать с данными.
Как говорили другие, с естественным языком, скорее всего, будет относительно небольшое количество уникальных значений, поэтому на самом деле карта не будет настолько большой. Я бы не использовал java.util.HashMap, поскольку он очень неэффективный с точки зрения использования памяти, особенно при хранении примитивных значений, таких как int. java.util.HashMap хранит примитивы как объекты. Он также сохраняет каждое значение внутри объекта HashMap.Entry, который отнимает память. Из-за этих двух факторов java.util.HashMap использует гораздо больше памяти, чем альтернативы, такие как Trove, Fastutil и другие:
Как уже упоминалось, существует несколько реализаций карт, которые не имеют этих проблем. Поскольку вы храните цифры на карте, дополнительное преимущество в том, что вы получите повышение производительности, потому что нет необходимости постоянно переключаться между объектами и примитивами (например, бокс/распаковка), поскольку вы добавляете новые значения на карту или обновляете старые значения. В этом руководстве в Руководстве по настройке производительности Java можно найти тест различных примитивных хэш-карт, которые лучше подходят для больших объемов данных :
С 100 миллионами терминов вы почти наверняка превыше того, что должно храниться в памяти. Сохраните свои условия в какой-либо базе данных. Либо используйте коммерческую базу данных, либо напишите что-нибудь, что позволит вам получить доступ к файлу, чтобы получить нужную вам информацию. Если формат файла, который у вас есть, не позволяет быстро получить доступ к файлу, а затем преобразовать его в тот, который делает - например, сделать каждую запись фиксированным размером, чтобы вы могли мгновенно вычислить смещение файла для любого номера записи. Сортировка записей позволит вам быстро выполнить двоичный поиск. Вы также можете написать код, чтобы значительно ускорить доступ к файлам без необходимости хранить весь файл в памяти.
Если вам нужен только легкий магазин KeyValue (Map), я бы посмотрел на Redis. Это очень быстро и имеет возможность сохранять данные в случае необходимости. Единственным недостатком является то, что вам нужно запустить хранилище Redis на Linux-машине.
Если вы ограничены Windows, MongoDB является хорошим вариантом, если вы можете запустить его на 64-разрядной версии.
Вы также можете попытаться увеличить количество дубликатов.
Например, cat = Cats = cats = Cat
или
плавать = плавание = плавает
попробуйте Googling "Портер-стриммер"
Тройка ThashMap использует намного меньше памяти. Тем не менее, сомневаюсь, что этого будет достаточно для уменьшения размера. Вам нужно где-то еще хранить эту информацию для извлечения, кроме строго в памяти.
Другие ответы уже указывали, что проблема связана с использованием памяти. В зависимости от вашей проблемной области вы можете создать ключевой класс, который уменьшил общий объем памяти. Например, если ваш ключ состоит из фраз естественного языка, вы можете разделить и ставить слова, составляющие фразу; например.
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 */ }
}
Фактически это решение может работать, даже если строки не представляют собой естественный язык, при условии, что существует значительное совпадение, которое может быть использовано между строк.
Отбросьте HashMap и загрузите все эти данные в HBase или один из других хранилищ данных NoSQL и напишите ваши запросы в терминах MapReduce операций. Это подход, используемый Google Search и многими другими сайтами, использующими огромные объемы данных. Он доказал, что он масштабируется до практически бесконечного размера.
Плохой дизайн. Имея 1,7 ГБ данных в памяти на HashMap, я бы сделал один из двух:
Сохранять все данные (файл/базу данных) и иметь верхний 1% или что-то в памяти. Используйте некоторый алгоритм для определения, какие идентификаторы будут в памяти и когда.
Используйте memcached. Самый простой выход. Распределенная хешируемая память. Это именно то, для чего используются DHT.
Подумайте о замене его cdb. До 4 ГБ и:
Успешный поиск в большой базе данных обычно занимает всего два обращения к диску. Неудачный поиск занимает только один.
Существует интересное предложение от Terracotta - BigMemory, которое, похоже, именно то, что вы хотите. Я сам не пробовал и не знаю лицензионных терминов и т.д.
Задняя сторона конверта: 1.7Gb/100M = avg 18 байтов = за период и частоту
Мы можем использовать handcoded hashmap, поддерживаемый двумя логическими массивами.
Один, чтобы удерживать int frequency (values), а другой - построить массив стиля char C, чтобы имитировать двухмерный массив c (массив массивов char). поэтому мы индексируем вычисление. мы не можем использовать двумерный массив java, поскольку он имеет слишком много накладных расходов на объект. Этот массив char может содержать массивы с фиксированным размером char для представления ключей. Поэтому мы вычисляем хэш ключа и помещаем его в этот "двумерный массив", и если у нас есть конфликт, он может быть разрешен, скажем, линейным зондированием. пары ключей и значений связаны общим индексом массивов.
Хешмап должен использовать открытую адресацию, так как у нас недостаточно памяти для цепочки.
Мы можем сказать 10 экземпляров этого хэш файла на основе длины ключей; не может быть уверенным, поскольку я не знаю характеристик данных.
Используемое пространство = 2 мощность 29 для массива int + (2 мощности 4 (16 байт на строку) * 2 pow 27) = 3,5 gig
Если нам нужны двойные частоты вместо ints, нам может понадобиться соответственно уменьшить размер строк.
В java у объекта есть служебные данные из 16 байтов как минимум до того, как вы рассмотрите, какой другой контент он содержит.
1e8 элементов на карте хэша имеет заниженное требование размера из 1e8 * 2 * 16 байтов, и это предполагает ваши ключи и значения - это числа, для которых требуется наличие нескольких ГБ кучи в вашей куче и с вашего компьютера.
Строка - это объект, содержащий массив символов, поэтому ваши строки как упомянуто многими выше, может быть больше, чем двойной объект например, поэтому вам потребуется больше памяти для куча.
Обратите внимание, что программы начинают плохо работать, когда вы приближаетесь к пределу вашего компьютера.
Если вы не хотите использовать базу данных, как было предложено выше, вы можете рассмотреть возможность кодирования и сжатия ваших ключей, чтобы сделать их в числа, которые вы все еще можете считать частотой. Вы можете выбрать кодировку на основе энтропии, основанную на частота слов в этом первом кодировании и перейти оттуда...
По причине неудачи я согласился бы с приведенными выше ответами.
DB - хороший выбор. Но даже коммерческий уровень БД, они также предложили бы "Разделение" данных на эффективные действия.
В зависимости от вашей среды я могу предложить использовать распределенные данные для нескольких узлов, которые подключаются через локальную сеть. Основываясь на значении ключа,
Node 01 имеет ключ, начинающийся с 'a' Node 02 имеет ключевое значение с "b"....
Итак, ваша программа внезапно изменилась на сетевое программирование.