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

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

0

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

Где хотябы одно подтверждение ваших слов? Вы лично проводили такое исследование?

0

Сообщение от Celly Где хотябы одно подтверждение ваших слов? Вы лично проводили такое исследование?

В учебнике по теории вероятности. Вместимость вектора - 2^N. Из них 2^(N-1) было хапнуто про запас. Реально использовано от 2^(N-1) до 2^N элементов. Значит, в среднем - (2^(N-1)+2^N)/2. Что и означает что половина хапнутого про запас простаивает. Можете, впрочем, провести численный эксперимент.

2

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

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

0

Renji, Хороший теоретический пример. В данной задаче std::list всё равно будет использовать больше памяти.

Добавлено через 5 минут

Сообщение от IGPIGP При использовании reserve она не перераспределяется

Вот вам так и хочется присвоить мне свои домыслы.

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

Где здесь шла речь о том что reserve перераспределяет память? Здесь речь идёт о том что reserve позволят избежать лишних перераспределений.

0

Сообщение от Celly Вот вам так и хочется присвоить мне свои домыслы.

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

Сообщение от Celly Где здесь шла речь о том что reserve перераспределяет память? Здесь речь идёт о том что reserve позволят избежать лишних перераспределений.

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

0

https://baptiste-wicht.com/pos... deque.html

Conclusion To conclude, we can get some facts about each data structure: std::list is very very slow to iterate through the collection due to its very poor spatial locality. std::vector and std::deque perform always faster than std::list with very small data std::list handles very well large elements std::deque performs better than a std::vector for inserting at random positions (especially at the front, which is constant time) std::deque and std::vector do not support very well data types with high cost of copy/assignment This draw simple conclusions on usage of each data structure: Number crunching: use std::vector or std::deque Linear search: use std::vector or std::deque Random Insert/Remove: ...Small data size: use std::vector ...Large element size: use std::list (unless if intended principally for searching) Non-trivial data type: use std::list unless you need the container especially for searching. But for multiple modifications of the container, it will be very slow. Push to front: use std::deque or std::list

1

Croessmah, интересные и вполне ожидаемые результаты. С ростом размера объекта список становится луче везде где превалирует вставка либо обмен. Конечно легче просвопить указатели чем переписать большие объекты.
Но тут игнорируется самое большое преимущество вектора. В сортированном векторе возможен бинарный поиск и в ряде задач список пролетает как фанера. Или я не прав?

0

Только в случае последовательного перебора в несортированных данных список хоть как-то приближаться к вектору, за исключением описанного тут - Что быстрее списки или вектор ? . А если нужно данные сортировать, то никакой список тут не подойдёт.

0

Сообщение от TRam_ А если нужно данные сортировать, то никакой список тут не подойдёт.

Он же и показывает, что для объектов очень большого размера, список как минимум не хуже. А вот по сортированным данным искать в списке тяжелее. Главная причина - последовательный доступ, в отличие от вектора/массива. Последовательное размещение массива - его главный козырь. Именно оно позволяет прямой доступ посредством адресной арифметики. И это позволяет очень быстро искать в сортированном массиве. Именно за сохранения этого преимущества вектор и борется путём перераспределения. Иначе можно было бы создавать кучу сцепленных массивов, например.
Ну то есть, они зеркальные близнецы. У одного последовательное размещение и произвольный доступ, а у другого произвольное размещение и последовательный доступ.

0

Сообщение от IGPIGP В сортированном векторе возможен бинарный поиск

Причем он быстрее, чем поиск в set/map.
В boost даже есть соответствующие контейнеры - flat_set/flat_map.

1

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

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

в векторе данные идут друг за дружкой:
1,2,3,4

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

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

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


итого:
при последовательном переборе элементов,
лист с треском проигрывает вектору в эффективности.

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

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

лист же выгодно использовать,
только если нужно часто вставлять/удалять
на больших объемах данных.

2

Воу-воу-воу, ребята! Что тут происходит?)
Память меня вроде пока не интересует, пусть ест сколько надо, главное время! Задачка для обработки кадров с веб-камеры.

0

Сообщение от hoggy лист же свои данные раскидывает по всей памяти.

Это самый большой ужас для любого контейнера. Но во многих задачах это не так. Вот простой пример. Есть поток данных. Сортируем и сохраняем на ходу. Почему менеджер памяти должен выделять откуда попало? Конечно, при сильной фрагментации может быть всё, но тогда и вектору придётся искать кусище за счёт свопинга на винчестер. А это уже не мимо кеша. Это реально очень долго.
В целом, сравнивать вектор и список вне контекста задачи - холивар.

Добавлено через 2 минуты

Сообщение от Leffken Задачка для обработки кадров с веб-камеры.

Что значит обработки?
Может глобальный массив это оно?

0

Сообщение от hoggy первое же обращение к этой страничке, и 32кб (на самом деле на разных камнях по разному)

Не пугайте людей на пустом месте, данные подгружаются кеш-рядами по 32/64 байта. Причем, кеша того мегабайты. Во времена старого-доброго Доса оперативки столько не было, сколько сейчас кеш делают и ничего, 640 килобайт как известно хватало всем.

Сообщение от hoggy даже более того: тесты показывают, что при относительно малом количестве элементов, вектор эффективнее даже в условиях, когда нужно часто вставлять/удалять элементы.

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

2

Сообщение от IGPIGP Что значит обработки? Может глобальный массив это оно?

Ну каждый кадр надо обработать попиксельно.

0

Leffken, возьми вектор. А точнее вектор с данными + вектор указателей на начала каждой из строк. Или можно вектор векторов (но в него данные чуть сложнее вставлять/забирать). Потому что разрешение на камере в процессе приёма не меняется (или меняется при переключении режимов, т.е. оочень редко), лишние пиксели при обработке добавлять не нужно .

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

0

Сообщение от Leffken Ну каждый кадр надо обработать попиксельно.

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

0