Мне нужно быстро найти объект, используя как можно меньше памяти. Какой контейнер данных я должен использовать?
Моей программе нужно вставить более миллиона записей в контейнер данных. Я пробовал hashmap и treemap. И то и другое даст мне исключение пространства кучи, хотя я позволю JVM использовать оперативную память 2 ГБ.
Моя программа часто получает конкретные данные из контейнера, которые, я думаю, если это займет O(logn) время, будут приемлемы для меня. Так какой контейнер я должен использовать? Или мне нужно реализовать один? Как?
Больше подробностей: ключ является String, как глобальный идентификатор, например, "00011123459", что-то вроде этого. Тогда ключ отобразится в список списка, т.е. List<List<String>>, Моя программа считала строку из файла, затем изменила строку на список, затем получила глобальный идентификатор из списка, затем поместила список в соответствующий список списка. Файл содержит более миллиона строк, поэтому я считаю, что основная причина в том, что я создаю слишком много списков. Тем не менее, я не могу добавить больше памяти на машину.
4 ответа
Предполагая, что подавляющее большинство использования памяти связано с самими данными записи, может случиться так, что выбор контейнера не решит вашу проблему (в качестве теста попытайтесь загрузить все ваши данные в массив; если вы закончили памяти, вам понадобится другое решение). Мало того, но если вы урезаете его настолько близко к емкости, у вас все равно будут проблемы, если в будущем вы столкнетесь с большим количеством записей.
Помимо добавления дополнительной оперативной памяти, есть много других подходов, которые вы можете использовать, но общая идея заключается в том, чтобы хранить больше на диске и меньше в памяти. Вот несколько возможных альтернатив:
- Храните свои записи в надлежащей базе данных (многие варианты здесь, SQLite может быть наиболее удобным для вас - много вариантов для доступа, начиная от прямой
java.sql.*в спящий режим). - Используйте что-то вроде MapDB, как отметил Андрей Чащев.
- Если ваша программа часто обращается к небольшому подмножеству данных или последовательно обращается к одним и тем же данным, рассмотрите возможность оставлять записи на диске, находить их при необходимости и кэшировать их при обнаружении (поиск только на диске, если интересующая запись не находится в кэше).
- Вместо того, чтобы хранить целые записи на карте, возможно, храните некоторую информацию, которая поможет вам быстрее находить их на диске и лениво загружать записи по мере необходимости (например, сохранять смещение файла данных записи на карте, затем при поиске загружать фактические данные записи из файл, реализовать кеширование при желании).
Лично я бы выбрал первый вариант (обязательно создайте индекс по ключам, которые вы обычно используете для поиска записей), поскольку его очень просто настроить и использовать, а SQLite (например) автономен и требует нет сервера. Ценой дополнительной сложности разработки вы все еще можете кэшировать данные, если обнаружите, что ваши требования к производительности не выполняются или что-то вроде Hibernate сделает это за вас.
HashMap занимает меньше памяти, чем TreeMap и является O(1).
Если ваши ключи цифры, вы можете сэкономить память с TLongObjectHashMap от Trove4j.
Другой вариант - временно сохранить ваши данные на диске с помощью MapDB.
Вы также можете применить кеширование с CacheBuilder в Гуаве: что происходит, когда коллекция в Java увеличивается до предела?
Если у вас есть больше поддержки инфраструктуры, попробуйте увеличить объем памяти до 4 или 5 ГБ и использовать любую из этих карт
Использовать древовидную карту - если вы хотите, чтобы ваши объекты были отсортированы. Поскольку объекты сортируются, требуется дополнительное время для сортировки всей карты после вставки нового объекта.
Используйте Hash map - для быстрого добавления / поиска, поскольку объекты не сортируются.
Из Javadoc.
This implementation provides guaranteed log(n) time cost for
the containsKey, get, put and remove operations.
Так что используйте TreeMap и дайте Java больше памяти.