Мне нужно хранить большой словарь слов естественного языка - до 120 000, в зависимости от языка. Они должны храниться в памяти, поскольку профилирование показало, что алгоритм, который использует массив, является узким местом в системе. (Это, по сути, алгоритм проверки орфографии/автокоррекции, хотя детали не имеют значения.) На устройствах Android с памятью 16 МБ накладные расходы памяти, связанные с Java String
s, вызывают у нас нехватку места. Обратите внимание, что каждый String
имеет 38 byte overhead associated with it,, который дает до 5 МБ служебных данных.Компактные альтернативы Java ArrayList <String>
На первый взгляд, один из вариантов заключается в замене char[]
на String
. (Или даже byte[]
, так как UTF-8 в этом случае более компактен.) Но опять-таки проблема с памятью является проблемой: each Java array has a 32 byte overhead.
Одна из альтернатив ArrayList<String>
и т. Д. Заключается в создании класса с таким же интерфейсом, который внутренне объединяет все строки в одну гигантскую строку, например. представленный как один byte[]
, а затем сохраняет смещения в эту огромную строку. Каждое смещение занимает 4 байта, что дает гораздо более эффективное пространство.
Мои вопросы: а) есть ли какие-либо другие решения проблемы с такими же низкими накладными расходами * и b) любое решение, доступное готово? Поиск в библиотеках коллекций Guava, trove и PCJ ничего не дает.
* Я знаю, что накладные расходы могут быть ниже 4 байтов, но есть уменьшающиеся доходы.
NB. Support for Compressed Strings being Dropped in HotSpot JVM? предполагает, что опция JVM -XX:+UseCompressedStrings
здесь не поможет.
Массив может иметь только записи 2^31-1 = 2.1g, может быть слишком мал для вас? – maraca
Нет ... слово обычно занимает ~ 10 байт, поэтому вся структура будет входить в ~ 1 МБ. (~ 1.5MB с накладными расходами.) – Mohan
Вам действительно нужно хранить все строки в памяти? Возможно, вы можете сохранить некоторый индекс и эффективно загрузить необходимую часть из файла? Какова ваша первоначальная задача? Как вы используете эти строки? –