Доработка контейнера vector для работы с большими объемами данных

[@dordzhiev]

Было бы интересно посмотреть как вы это реализовали.

[@tampere]

Такое сейчас реализовано где-нибудь? Что делать на архитектурах, где страницы по 4MB?

[@GrossHo]

Желательно, чтобы ОС имела интерфейс в помощь миграции листов памяти. Иначе все преимущество на контекстных переключениях съестся.

[@Mineev]

А итераторы тоже реализовали?

[@Mineev]

И для альтернативных расположений данных в памяти можно использовать аллокаторы.

[@huek]

идиоты, про std::deque никогда не слышали

[@dosyas]

Ну deque тут не поможет. Обычно у STL-ного deque тоже переаллокация с копированием элементов происходит. Например в gcc используется реализация с вектором и циклической индексацией. Т.е. когда место в векторе закончится, то будет все то же самое.

[@huek]

у std::deque push_back имеет O(1) скорость выполнения, топикреатер просто нешарит в языке на котором пишет- вот и высирает вылосипеды, ну высирыает и высирает, это ещё полбеды- но когда свой высер на обозрение общественности выставляет- это уже плохо.

[@dosyas]

Да, немного неправильно выразился. Сами элементы не копируются, копируется таблица мэппинга индексов при переаллокации. Т.е. всплески могут быть все-равно и они будут O(n). Но константа, конечно, сильно меньше, чем в векторе.

[@qehgt]

Не будет.

«A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle. „

[@Spellman]

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

[@khizhaster]

Отчего же сразу идиоты, они просто еще не Senior и не читали Кнута и Мейерса, либо пролистали просто.
Кроме того, не сильно ясно какие у них задачи, может им только вектор и подходит. Посему не стоит так критично, каждый контейнер на свою задачу, к тому же если бы deque равнозначно заменял vector, он был бы не нужен, посему тут нужно просто полистать Мёртвого Страуса и Мейерса, выбрать контейнер. Если выбор не определился, то полистать более серьёзную литературу и выбрать правильный аллокатор.
Они по сути простенький хэш сделали своим «ветором векторов», может им бы банальное дерево подошло, кто знает, что у них там за потребности.

[@GraD_Kh]

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

[@Necrys]

Беда, инструментом пользуетесь, а как он работает не знаете. Скажите честно, сколько рабочих часов потратили на то, чтобы выявить ошибку и выяснить как работает банальный std::vector?

[@Andrew_Lvov]

Вы знаете как работает АБС в машине, к-рую водите? Или гидроусилитель?
Что удерживает мотоцикл от падения на скорости?
Как данные обрабатываются на видеокарте прежде, чем попасть на экран?
Я пользуюсь Хабром (что тоже инструмент), но не вникаю во внутренний механизм его работы (даже если б имел такую возможность) — потому, что не вижу в этом потребности.

У автора до некоторого момента не возникала потребность в знании реализации контейнера. Появилась — выяснил.

[@Xab]

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

[@Andrew_Lvov]

В большинстве случаей не правильный выбор контейнера не проявит себя на скорости выполнения никак.
Ну считываете вы параметры программы из ini файла. Ну пусть вы использовали vector/deque/list вместо map? Если в программе менее сотни конфигурационных параметров, каждый из к-рых считывается скажем раз в пару секунд — на современной машине вы даже с секундомером не увидите разницы, несмотря на линейную скорость поиска против логарифмической

[@Pushkoff]

так бы и сказали, что не сталкиваетесь с задачами которые требуют производительности…
на ГД.ру была тема где человек перешел от сета, к сортировке вектора и снизил время кадра с 40 до 6 мс, что согласитесь заметно, даже без секундомера…

[@Andrew_Lvov]

Почти никогда не пользовался буффером вектора напрямую.

[@artfabrique]

Интересно, а реализация Vector в AS3 это тупое зеркало? Плеер то на плюсах, наверно, написан. Мне бы большим подспорьем стало. Массивы хоть не такие большие (до 1000), но думается, если элемент вектора весит по 50кб, то оптимизация будет ощутима.

[@emendz]

Вообще-то vector изначально не оптимален для частого добавления элементов. И доролнительная проблема с часто растущими векторами, как и в предыдущей статье — фрагментация памяти. Был кусок size, стал size + K*size, потом оригинальную size освободили, но не факт что оптимально удастся ее использовать.

[@sgzmd]

Both vectors and deques provide thus a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors are very similar to a plain array that grows by reallocating all of its elements in a unique block when its capacity is exhausted, the elements of a deques can be divided in several chunks of storage, with the class keeping all this information and providing a uniform access to the elements. Therefore, deques are a little more complex internally, but this generally allows them to grow more efficiently than the vectors with their capacity managed automatically, specially in large sequences, because massive reallocations are avoided.

RTFM.

[@denim]

реализация вектора и логарифмическое выделение памяти соответсвует все академическим каннонам. именно так нас учили в универе пистать динамические массивы. вывод — общий случай не работает везде

[@AxisPod]

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

Если бы вы сначала описали, зачем вам понадобился именно vector. Было бы интереснее, да и может быть предложили бы другой вариант. А стандартный контейнер я переписывал только 1 раз, мне нужна была репликация данных на диск при изменении.

[@AxisPod]

Мне не важно сколько перераспределяет раз, все зависит от реализации, а их много и может отличаться. А list для этих целей подходит отлично.

[@AxisPod]

Ну элементы в векторе частенько менялись и вставлялись не только в конец.

[@tpolm]

Целая статья из проблемы, которая решается за пару минут, комментарии «используй list/deque», от людей, не знающих, что у list/deeque среднее время доступа O(N), а у вектора O(1)…

«бида-бида, грусть — пичаль»

авторы, почитайте про stlxxl

[@GraD_Kh]

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

[@GrossHo]

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

[@GrossHo]

Конкретно против этого высказывания спорить не буду. Но и вы спорите не со мной.

[@andrewsch]

Звучит как реализация sparce array (разреженный массив)

[@andrewsch]

да, точно :-) спасибо

[@dmbreaker]

«STL для самых маленьких» на Хабре :)

[@Next_Alex]

А им, знаете ли, тоже нужно учиться. И, честно говоря, не всегда хорошо учиться на своих ошибках.
Ясно что и нам нужно было учиться раньше и нужно было обращать внимание на «мелочи» ( специально взял в кавычки чтобы избежать очередного холливара о мелочах в программировании ), но ведь всегда есть достаточно веские причины вроде специфики проекта, особенностей реализации под конкретную платформу и просто человеческого фактора.
К слову, когда-то, много лет назад, мне приходилось писать нативную либу для работы с COM-портом в Java просто потому как таковая хоть и существовала, но была в настолько непотребном состоянии, что использовать ее не представлялось возможным. И там уже не стоял вопрос о знании языка, радиусе кривизны рук и длине костылей — нужно было просто быстро найти выход из сложившейся ситуации иначе финиш.
Собственно такая ситуация описана была и здесь. И, глядишь, кто-нибудь из этих «самых маленьких» благодаря умению читать и любви к хабру обойдет такие грабли стороной и скажет спасибо хабру или, чем черт не шутит, мне.

[@webhamster]

> «STL для самых маленьких» на Хабре :)

Поправочка:

«STL для самых маленьких» ^{из песочницы}.