Цикл через набор объектов

Question

У меня есть карта пар ключ-значение огромного размера, примерно 10 ^ 7, и мне нужно циклически просматривать ее 15 раз в секунду, чтобы обновить ее содержимое. Есть ли какой-либо класс или структура, которая предлагает хорошую сложность и уменьшаетвремя, необходимое для прохождения цикла?

В настоящее время я использую TreeMap , но сложность log n только для содержит, помещает, получает и удаляет.Цикл по элементам имеет сложность n

Знаете ли вы какую-либо структуру или у вас есть идея, которая может уменьшить сложность ниже n ?

Answer 1

Если вам придется выполнить произвольный цикл по всей коллекции, вы не получите лучше, чем n. Если вам нужно зациклить всю коллекцию, вы можете использовать простой ArrayList. но если вам нужен доступ к определенным данным в коллекции с помощью ключа, то с TreeMap все будет в порядке.

Answer 2

Вы не можете превзойти ограничение O (n) на любом последовательном (или конечно параллельном) компьютере, если ваша задача просто посмотреть на все значения O (n).

Если у вас есть конечно-параллельная машина и в зависимости от того, как именно вы обновляете элементы, вы можете добиться ускорения. Например, используя CUDA и GPU или OpenMP / MPI и кластерную / многоядерную рабочую станцию, вы можете вычислить A [i] = A [i] ^ 3 или что-то подобное с хорошим ускорением. Конечно, тогда возникает вопрос общения ... но это может быть что-то, на что можно посмотреть.