— Could NOT find INOTIFY (missing: INOTIFY_INCLUDE_DIR INOTIFY_LIBRARY_DIR) — Could NOT find Sphinx (missing: SPHINX_EXECUTABLE) — Could NOT find PdfLatex (missing: PDFLATEX_EXECUTABLE) как исправить?

оно же тебе черным по белому написал - нет исполняемых файлов. Смотри пути к bin папке либ

да понял, ненашел таких файлов

он ищеть inotify.h

есть команда locate inotify.h

вот она покажет каких путей у тебя не хватает. Если такой файл вообще есть в системе

на windowsе ?

или

?

нет, это для линукса

у меня win

В смаке, как я думаю

/stat@combot

combot.org/chat/-1001031904034

Объясните мне кто-нибудь почему у меня есть vector<int> и list<int> и если я вычисляю сумму всех элементов, то операция на list'е оказывается быстрее. Почему так? Я всегда думал что вектор будет быстрее из-за того что там всё в одном блоке памяти лежит

Объясните мне кто-нибудь почему у меня есть vector<int> и list<int> и если я вычисляю сумму всех элементов, то операция на list'е оказывается быстрее. Почему так? Я всегда думал что вектор будет быстрее из-за того что там всё в одном блоке памяти лежит

Лист небольшой, создай массив и связный список на 100к элементов и проверь

Я на 10 000 000 создавал, ща код примера выложу где-нибудь

Так. Интересно. С -O3 другие результаты

о, сегодня ж очередная встреча коммитета

Объясните мне кто-нибудь почему у меня есть vector<int> и list<int> и если я вычисляю сумму всех элементов, то операция на list'е оказывается быстрее. Почему так? Я всегда думал что вектор будет быстрее из-за того что там всё в одном блоке памяти лежит

мне кажется это зависит от того как ты достаёш элементы из коллекций.

о, сегодня ж очередная встреча коммитета

Да. на нее уже вылетели прям с конфы тогда

Так. Интересно. С -O3 другие результаты

Код-то будет? :)

Да я уже разобрался. С флагами оптимизаций сложения вектора быстрее. Причём через std::accumulate быстрее чем через просто цикл

Код-то будет? :)

Хорошо, ща выложу )

Код-то будет? :)

https://gist.github.com/shelomentsevd/9b5764bacd2698056097d7c683dbf2c0

Да я уже разобрался. С флагами оптимизаций сложения вектора быстрее. Причём через std::accumulate быстрее чем через просто цикл

accumulate тот же for

не может он быстрее или у тебя for криво написан

кароче, нужен код :)

И в дебаге лист все равно медленне должен быть

http://melpon.org/wandbox/permlink/I8MYeXPdo8tLvPAb

мне кажется это зависит от того как ты достаёш элементы из коллекций.

Скорость доступа в листе - динамическая, больше список - дольше доступ. В векторе - статическая

без всяких оптимизаций видно что лист все равно медленнее

Попробуй свой контейнер написать

Скорость доступа в листе - динамическая, больше список - дольше доступ. В векторе - статическая

wat

Ну вектор быстрей по доступу, это логиншно жеж.

Первый без -O3 второй с O3

wat

А, произвольный доступ - конечно.

В первом случае list быстрее. Чудеса

https://gist.github.com/shelomentsevd/9b5764bacd2698056097d7c683dbf2c0

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

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

а как лучше?

Он сам по себе медленный

Юзай деку вместо листа)

а как лучше?

accumulate?

accumulate?

А без accumulate?

А без accumulate?

Поищи, их много

http://melpon.org/wandbox/permlink/I8MYeXPdo8tLvPAb

242445 у deque и 696983 у list

Юзай деку вместо листа)

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

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

Но тут ваще непростой вопрос.)

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

Вот такой ответ почему-то не прокатил

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

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

Вот такой ответ почему-то не прокатил

Патамущ там не так просто.

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

Sum is: 25000426 List: 222145 microseconds. Sum is: 25000426 Vector: 39549 microseconds. Sum is: 25000426 List cycle: 205900 microseconds. Sum is: 25000426 Vector cycle: 171095 microseconds. если ком уто интересно vs2015

без всяких флагов оптимизаций

Sum is: 25000426 List: 222145 microseconds. Sum is: 25000426 Vector: 39549 microseconds. Sum is: 25000426 List cycle: 205900 microseconds. Sum is: 25000426 Vector cycle: 171095 microseconds. если ком уто интересно vs2015

Блин, какая-то фигня у меня получается на компьютере

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

Вот это, думаю, немного просветит ситуацию https://courses.engr.illinois.edu/ece390/books/artofasm/CH03/CH03-2.html

ERROR: S client not available

Вот такой ответ почему-то не прокатил

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

Вот что я забыл, это по скорости изменения коллекции (добавление/удаление) быстрей...

list, заполненный в цикле добавлением в конец, тоже будет расположен в памяти относительно последовательно

Вот это, думаю, немного просветит ситуацию https://courses.engr.illinois.edu/ece390/books/artofasm/CH03/CH03-2.html

До кучи ещё вот Дреппера могу предложить почитать, но это если тема реально интересует https://www.akkadia.org/drepper/cpumemory.pdf

list, заполненный в цикле добавлением в конец, тоже будет расположен в памяти относительно последовательно

Всё так.

В общем надо про память читать. Я правильно понял?

И про проц)

Воще, кэш же!

Я это себе туго представляю, но получается что вектор какую-то свою часть хранит прямо в кэше, а список всё хранит в памяти?

Туда ж целыми кусочками копируются данные из памяти)

Я это себе туго представляю, но получается что вектор какую-то свою часть хранит прямо в кэше, а список всё хранит в памяти?

В кэше никто ничего не хранит кроме процессора

В кэше никто ничего не хранит кроме процессора

Но процессор не знает, что у него есть кэш(минутка ЭВМ)

Но процессор не знает, что у него есть кэш(минутка ЭВМ)

Ну для того чтобы объяснить почему вектор быстрее этой абстракции вполне достаточно

Кэш это тоже по сути память же? Может ли быть такое, что list случайно весь попадет в кэш и тогда операция по нему будет быстрее?

лист очень маловероятно, вектор да

В общем. И вектор, и список лежат в памяти. Вектор — последовательно, а лист — не всегда, у каждой вершинки есть указатель на следующую и он может указывать на другой участок памяти Просто когда процессор хочет посчитать, например, ту же сумму чисел в кеш отправляется целый кешлайн, например, 64 байта. Он берет первую чиселку, кладет в аккумулятор. Идет за второй, а она такая — оп, тоже есть в кешлайне, за ней не надо идти в оперативную память по медленной шине. Таким образом в кешлайне лежит, например, сразу восемь чиселок, которые надо добавить к аккумулятору. Если лист лежит в памяти последовательно, то процесс, по идее, должен быть таким же. А если элементы как-то неоднородно в памяти лежат, за ними приходится ходить в память (опять-таки, шина в оперативную память очень медленная и читать оттуда очень дорого по сравнению с чтением из кэша)

В общем. И вектор, и список лежат в памяти. Вектор — последовательно, а лист — не всегда, у каждой вершинки есть указатель на следующую и он может указывать на другой участок памяти Просто когда процессор хочет посчитать, например, ту же сумму чисел в кеш отправляется целый кешлайн, например, 64 байта. Он берет первую чиселку, кладет в аккумулятор. Идет за второй, а она такая — оп, тоже есть в кешлайне, за ней не надо идти в оперативную память по медленной шине. Таким образом в кешлайне лежит, например, сразу восемь чиселок, которые надо добавить к аккумулятору. Если лист лежит в памяти последовательно, то процесс, по идее, должен быть таким же. А если элементы как-то неоднородно в памяти лежат, за ними приходится ходить в память (опять-таки, шина в оперативную память очень медленная и читать оттуда очень дорого по сравнению с чтением из кэша)

Господи, чем я занимаюсь, лишь бы не работать...

Учишь людей. И это хорошо. Омниссия одобряет!

В общем. И вектор, и список лежат в памяти. Вектор — последовательно, а лист — не всегда, у каждой вершинки есть указатель на следующую и он может указывать на другой участок памяти Просто когда процессор хочет посчитать, например, ту же сумму чисел в кеш отправляется целый кешлайн, например, 64 байта. Он берет первую чиселку, кладет в аккумулятор. Идет за второй, а она такая — оп, тоже есть в кешлайне, за ней не надо идти в оперативную память по медленной шине. Таким образом в кешлайне лежит, например, сразу восемь чиселок, которые надо добавить к аккумулятору. Если лист лежит в памяти последовательно, то процесс, по идее, должен быть таким же. А если элементы как-то неоднородно в памяти лежат, за ними приходится ходить в память (опять-таки, шина в оперативную память очень медленная и читать оттуда очень дорого по сравнению с чтением из кэша)

в листе еще есть оверхед на адрес следующего элемента

Да, поэтому кол-во чиселок к кэше будет меньше.

А, ну да Тем более, в случае с std::list это doubly linked list, поэтому там два указателя

В общем. И вектор, и список лежат в памяти. Вектор — последовательно, а лист — не всегда, у каждой вершинки есть указатель на следующую и он может указывать на другой участок памяти Просто когда процессор хочет посчитать, например, ту же сумму чисел в кеш отправляется целый кешлайн, например, 64 байта. Он берет первую чиселку, кладет в аккумулятор. Идет за второй, а она такая — оп, тоже есть в кешлайне, за ней не надо идти в оперативную память по медленной шине. Таким образом в кешлайне лежит, например, сразу восемь чиселок, которые надо добавить к аккумулятору. Если лист лежит в памяти последовательно, то процесс, по идее, должен быть таким же. А если элементы как-то неоднородно в памяти лежат, за ними приходится ходить в память (опять-таки, шина в оперативную память очень медленная и читать оттуда очень дорого по сравнению с чтением из кэша)

? я все понял, спасибо

В общем. И вектор, и список лежат в памяти. Вектор — последовательно, а лист — не всегда, у каждой вершинки есть указатель на следующую и он может указывать на другой участок памяти Просто когда процессор хочет посчитать, например, ту же сумму чисел в кеш отправляется целый кешлайн, например, 64 байта. Он берет первую чиселку, кладет в аккумулятор. Идет за второй, а она такая — оп, тоже есть в кешлайне, за ней не надо идти в оперативную память по медленной шине. Таким образом в кешлайне лежит, например, сразу восемь чиселок, которые надо добавить к аккумулятору. Если лист лежит в памяти последовательно, то процесс, по идее, должен быть таким же. А если элементы как-то неоднородно в памяти лежат, за ними приходится ходить в память (опять-таки, шина в оперативную память очень медленная и читать оттуда очень дорого по сравнению с чтением из кэша)

#fyi #list #vector #memory

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

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

Народ, не могли бы вы объяснить, что значит эта запись на Си?

полный контекст

Спасибо за скрины вместо пасты