Что быстрее списки или вектор ?

Всем привет.
Делаю приложение и очень важна скорость обработки данных, а нужно хранить динамические массивы.
В каком формате будет поэлементный перебор происходить быстрее? В частности нужно хранить комплексные числа.

0

про скорость не знаю а мне больше вектор по душе, хотя и списки тоже хороши,

0

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

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

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

Добавлено через 6 минут
А ещё есть деревья (т.е. когда из одного элемента доступно сразу несколько следующих ), по "характеристикам" - промежуточное положение между списком и хэш-таблицей .

1

TRam_, ведя разговор о списках, необходимо помнить, что его быстрая вставка и удалени - это лишь теория. Постоянное дерганье узлов списка выльется в постоянные кеш-промахи и отнимет кучу процессорного времени. Запомни, vector - хорошо дружит с кешем, т.к. он непрерывен. Что касается копирований и т.д., то во-первых, есть перемещение, во-вторых, вставка в конец вектора, скорее всего, обгонит список в разы, а в-третьих, каждая вставка в список требует аллоцировать память, у вектора же запас.

Что касается выбора контейнера, то отталкиваться нужно совсем не от теоретической его скорости. Сначала необходимо решить какие контейнеры на вообще подойдут. Например, нам нужен контейнер, итераторы на элементы которого не будут инвалидироваться. Тогда вектор нам сразу не подойдет, однако, если вставка только в конец и нам известно максимальное число элементов, которое нам потребуется, то, нам подойдет и вектор, но с предварительным резервированием (но всё же ассерт лучше добавить, для проверки).
А точную скорость, которую нам даст вектор или список нужно проверять на конкретном наборе данных и оборудовании. Все остальные замеры будут не верными, возможно, даже противоположными. Так что берите и тестируйте.

3

Сообщение от MasterOfAlteran Что касается выбора контейнера, то отталкиваться нужно совсем не от теоретической его скорости. Сначала необходимо решить какие контейнеры на вообще подойдут. Например, нам нужен контейнер, итераторы на элементы которого не будут инвалидироваться. Тогда вектор нам сразу не подойдет, однако, если вставка только в конец и нам известно максимальное число элементов, которое нам потребуется, то, нам подойдет и вектор, но с предварительным резервированием (но всё же ассерт лучше добавить, для проверки).

Планируется хранить в памяти N -ое кол-во наборов (как бы двумерный массив) комплексных чисел. Из функционала полный перебор всех элементов, вставка в конец, размер не известен. И да, скорее всего надо будет иметь обращение к соседним элементам, так что доступ по индексу хотелось бы осуществлять. Поэтому выбор в сторону вектора. Надеюсь хватит скорости )) Если что придется параллелить.

0

Сообщение от Leffken Надеюсь хватит скорости

у флеша попросите тогда будет моментально выполняться а так много факторов могут повлиять на скорость

0

Сообщение от Leffken В каком формате будет поэлементный перебор происходить быстрее?

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

0

MrGluck,
А можно подробнее? Не могу понять, в чем разница. На мой взгляд скорость будет одинаковой т.к в итоге в обоих случаях все сводится к адрес-> данные

0

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

1

Сообщение от Undisputed На мой взгляд скорость будет одинаковой т.к в итоге в обоих случаях все сводится к адрес-> данные

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

1

Если планируется хранения большого количества элементов, то стоит учитывать что при использовании std::list будут дополнительные расходы памяти, в размере двух указателей на соседние элементы для каждого элемента списка.

Undisputed,
Если вам необходимо хранить динамический массив (из вашего описания, только для добавления), то я бы вам посоветовал посмотреть ещё в сторону std::deque т.к. он в специфику своей реализации позволит избежать перераспределений памяти в долгосрочной перспективе. Память в std::deque выделяется постранично, и в случае нехватки памяти в странице, будет выделена новая и связана как тот же двусвязный список.

Но, опять же, пока ещё никто не отменял std::vector::reserve().

Чтобы окончательно определиться с контейнером, необходимо больше информации о задаче.
Ещё есть одно хорошее правило: "Если вы не знаете какой контейнер выбрать, выбирайте std::vector"

0

Сообщение от Celly Если планируется хранения большого количества элементов, то стоит учитывать что при использовании std::list будут дополнительные расходы памяти, в размере двух указателей на соседние элементы для каждого элемента списка.

А при использовании вектора не будет? Его push_back должен работать за амортизированное константное время. Но при push_back может случиться реаллокация данных которая, понятное дело, работает за линейное время (на перекидывание данных с места на место). Чтобы скрестить первое со вторым, надо минимизировать число реаллокаций. А значит хапать память с этак 100% запасом.

1

Сообщение от Renji А при использовании вектора не будет? Его push_back должен работать за амортизированное константное время. Но при push_back может случиться реаллокация данных которая, понятное дело, работает за линейное время (на перекидывание данных с места на место). Чтобы скрестить первое со вторым, надо минимизировать число реаллокаций. А значит хапать память с этак 100% запасом.

Не будет. Здесь речь идёт о дополнительной памяти которую будут занимать служебные данные контейнера. У std::vector служебных данных несколько байт. У std::list - по 2 указателя на каждый элемент, т.е. при использовании списка на каждый элемент будет ещё приходится 8 байт (на 32 битной системе) служебных данных. Renji, дальше вашу мысль не понял.

0

Сообщение от Renji Но при push_back может случиться реаллокация

При удалении элементов тоже не лучше. Всё переписывается уже в выделенной области иначе без переиндексации (тех же указателей) чтобы получить прямой доступ с семантикой последовательного размещения не получится. То есть затраты. Зато список на стенку пи не умеет бинари сёрчить по человечески. То есть, даже в сортированном списке нужно в среднем N/2 шагов. А в векторе двоичный логарифм. То есть, искать тем проще чем больше объём. Вектору хорошо, если его заполняют однажды и потом только читают. Или, по крайней мере, не часто заставляют релоцировать.

0

Сообщение от Celly Renji, дальше вашу мысль не понял.

0

Renji, В вашем примере происходит выделение памяти, которая в последсвии будет использоваться для хранения элементов. В случае std::list идёт речь о памяти которая будет использоваться для служебных данных самой структуры std::list. Это размер двух указателей для каждого элемента списка. Допустим, в данной задаче, размер комплексного числа 8 байт (4 байта действительная часть и 4 мнимая). Тогда, на каждый элемент списка размером 8 байт придётся ещё 8 байт служебных данных (по 4 байта на указатели на соседние элементы).

0

Сообщение от Celly Не будет.

Будет-будет. Список не релоцируется вообще. А вектор, - да релоцируется. Конечно, если сравнивать неизменяемые контейнеры равного объёма данных, то вектор меньше. Это правда. Но в реальной жизни, неизменяемость это то, что делает применение списка бессмысленным и сравнение тоже теряет смысл. Иначе, если только есть такая возможность, то список удобнее. Память сегодня не самое узкое место.
К тому же есть хеш-массивы которые используют плохие качества и массивов и списков.
Вот одна ужасная фантазия на тему:
https://www.cyberforum.ru/blog... g4772.html

0

Сообщение от Celly Renji, В вашем примере происходит выделение памяти, которая в последсвии будет использоваться для хранения элементов.

Кто вам сказал что эта память будет использоваться?
Итог - "и 6 из 16 позиций висят мертвым грузом".

0

IGPIGP, Перечитайте мои посты. Вы пытаетесь присвоить мне суждение о том что память вектора не перераспределяется.
Я говорил о том что в случае std::vector дополнительный расход памяти на служебные данных контейнера минимален. В случае std::list - в размере двух указателей на каждый элемент.

Добавлено через 4 минуты
Renji, В момент вывода на экран - да, не используются. Но вы можете так же уверенно заявить что в процессе жизни программы они не будут использоваться?

0

Сообщение от Celly Renji, В момент вывода на экран - да, не используются. Но вы можете так же уверенно заявить что в процессе жизни программы они не будут использоваться?

Не я, а теория вероятности может заявить, что в среднем половина этого резерва будет пустовать. Но, разумеется, это в среднем. Так то у вас есть отличный от нуля шанс что вектор всегда будет полностью использовать занятую "про запас" память. Просто этот шанс стремится к нулю.

0