stdvector — постоянный доступ к произвольному элементу в списке (C ++)
В настоящее время я работаю над реализацией алгоритма, который я хотел бы показать, что он может работать в постоянном времени, даже с очень большим количеством элементов.
К сожалению, мне нужна структура данных, где хранить элементы. Когда количество элементов очень велико, но не слишком много для моего алгоритма, и std :: vector, и std :: valarray не обращаются к произвольному элементу в постоянном времени как вы можете видеть на этом графике.
Есть ли лучшая структура данных для хранения значений? Есть ли какие-либо методы, которые я могу реализовать, чтобы достичь постоянного доступа?
Решение
Для высоких значений n очень вероятно, что:
Вы столкнулись с проблемой кеширования. В какой-то момент каждый доступ к памяти пропускает кеш, вызывая более длительную загрузку памяти.
Вы столкнулись с проблемой кеширования с подкачкой памяти. Современная компьютерная память организована в древовидную структуру. Каждый доступ к памяти проходит через это дерево, делая каждый доступ к памяти O(log n) где n адресная область памяти. Обычно вы этого не замечаете из-за высокой арности этого дерева и хорошего кеширования. Однако для очень высокого n и произвольный доступ к памяти это может стать проблемой.
Мой друг, например, доказывал, что алгоритм сортировки O(n log n) временная сложность из-за случайного доступа к памяти. Алгоритм быстрой сортировки — для сравнения — имеет очень хороший последовательный доступ к памяти, а затраты на подкачку намного ниже.
Суть в том, что вы, скорее всего, столкнетесь с накладными расходами на доступ к памяти архитектуры / ОС — то, что вы не сможете преодолеть, если не будете использовать действительно экстремальный подход (например, реализацию собственной ОС).
Другие решения
Других решений пока нет …