Java Производительность: Карта против Списка

Question

Я построение дерева пагинации в JSF1.2 и RichFaces 3.3.2, потому что есть много узлов дерева (что-то вроде 80K), и это медленно ..

Так , в качестве первой попытки я создаю HashMap со страницей и списком узлов страницы.

Но, производительность, не достаточно хорошо ...

Так мне было интересно, если что-то быстрее, чем HashMap, может быть список списков или что-то.

У кого-то есть опыт? Что я могу сделать?

Заранее спасибо.

---

EDIT.

Большая проблема заключается в том, что я должен проверять разрешения пользователей в дочерних элементах дерева. Я знал, что это большая проблема: эта проверка медленна, потому что я должен заходить в узлы, у меня нет хорошего способа узнать, имеет ли пользователь разрешение на узле 10-го уровня без повторения всех них. Плюс к этому, те же три использовали в других местах ... Основная причина, почему я делал эту разбивку на страницы, заключается в том, что клиентская сторона будет намного медленнее из-за структуры, созданной richfaces, много tr и td's, браузер просто сходит с ума от этого. Итак, к сожалению, я должен загружать все узлы и разбивать на страницы только на стороне клиента, и мне нужно знать, что из них быстрее итерации ...

Извините, мой плохой английский.

Answer 1

Хэш-карта - это самая быстрая структура данных, если вы хотите получить все узлы для страницы. Список узлов может быть выбран в постоянное время (O (1)), тогда как со списками время равно O (n) (n = количество страниц, быстрее по отсортированным спискам, но никогда не приближается к O (1))

Что такое операции над вашей структурой данных: слишком медленно. Это то, что вам нужно проанализировать, прежде чем начинать оптимизацию.

Answer 2

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

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

Answer 3

Я бы решил это с помощью метода javascript/ajax calls, который извлекает дочерние элементы.

Answer 4

Структура данных, используемая всегда зависит от того, как вам нужно хранить данные и как вам нужно получить к ней доступ. HashMap<K, V> должен иметь постоянную временную сложность при доступе к значению при условии ключа. Когда вы вызываете get(key), вычисляется hashCode() для key и используется для извлечения соответствующего значения. Если у вас нет разных ключей, имеющих один и тот же хэш-код (в этом случае вы, возможно, делали что-то неправильно, поскольку, хотя это необязательно, разные объекты должны иметь разные хэш-коды, по крайней мере в большинстве случаев), это обычно быстро ,

Поиск элемента в обычном списке требует сканирования списка, который (почти) всегда будет медленнее, чем вычисление хэш-кода.

Если вам нужно связать значения с ключами, то путь Map. И HashMap должен быть достаточно быстрым.

Я не знаю слишком много о JSF, но я думаю - если структура данных и шаблон доступа - это тот, который предназначен для Map - проблема не в самой HashMap.