Ищете космические эффективные алгоритмы и структуры данных

Question

Предпочтительно на Java. Меня интересуют реализации структур данных, таких как Sets and Maps, и алгоритмы, такие как сортировка, которые эффективны с точки зрения памяти, не обязательно быстрые. Я мог бы жить с извлечением O (n^2) и хранить, если количество памяти и количество распределений были низкими. Что-нибудь там?

Answer 1

O (n^2) кажется действительно чрезмерным. Что именно вы ожидаете от своей структуры данных? Простое использование вектора даст вам O (n) наихудший случай для хранения и извлечения, а также для O (n) пространства. - Последнее не может быть действительно уменьшено (запрет на сжатие структуры данных, но для этого вам нужно предоставить много более подробную информацию о вашем домене данных), так почему бы просто не использовать вектор?

Answer 2

Для чрезвычайно компактных структур по сравнению с стандартными стандартами java можно работать на уровне бит. Разумеется, это сильно зависит от ваших данных, код, на мой взгляд, не может быть общим. Я не знаю ничего, что могло бы сделать это в целом. Вы могли бы разработать его (возможно, используя класс BitSet).

---

Что-то в Java, который сверхкомпактные это перечисление классов: EnumSet и EnumMaps. Они чрезвычайно компактны и чрезвычайно быстры. Идея:

• Определение наличия или нет конкретного перечисления, например, в виде набора является булевой информация, поэтому она требует 1 бит. Поэтому для EnumSet требуется только один длинный (для перечислений с менее чем 64 экземплярами).
• В EnumMap (строка только для примера), не требуется хранить ключ (enum), его можно сделать неявным, вызывая ordinal() на перечислении, которое поставляет индекс. Следовательно, память может быть String [], а ключи не сохраняются.