Постоянный доступ к произвольному элементу в списке (C++)

Question

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

К сожалению, мне нужна структура данных, где хранить элементы. Когда количество элементов очень большое, но не слишком высокое для моего алгоритма, и std::vector, и std::valarray не обращаются к произвольному элементу в постоянном времени, как вы можете видеть на этом графике.

Есть ли лучшая структура данных для хранения значений? Есть ли какие-либо методы, которые я могу реализовать, чтобы достичь постоянного доступа?

Answer 1

Для высоких значений n очень вероятно, что:

Вы столкнулись с проблемой кеширования. В какой-то момент каждый доступ к памяти пропускает кеш, вызывая более длительную загрузку памяти.

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

Мой друг, например, доказывал, что алгоритм сортировки O(n log n) временная сложность из-за случайного доступа к памяти. Алгоритм быстрой сортировки - для сравнения - имеет очень хороший последовательный доступ к памяти, а затраты на подкачку намного ниже.

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