Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, Sharov, Вы писали:

S>>Почему также нельзя сделать для O(log(n))?
CC>А где ты видел алгоритмы с log n и линейным доступом к данным?

М-да, справедливо. Но тогда по разнице доступы к L1 и RAM (вроде в 100 раз ?), соотв. если у нас будет
в 100(1000,10000 и т.д.) раз больше элементов, то мы точно сможем сказать, что log(n) быстрее.
А так да за счет spatila locality можно в отыграть разницу между n и log(n) до определенного предела.
Вот когда эта разница будет слишком велика, больше разницы между L1 и RAM, вот тогда можно быть точно уверенным.

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

Здравствуйте, Sharov, Вы писали:

S>>>А есть реальные примеры с объяснением почему?
CC>>Например потому что cache locality обеспечивает существенный прирост алгоритмов с линейным доступом.

S>А как это влияет на O(log(n)) vs O(n)? Типа при O(n) locality будет лучше? Почему также нельзя сделать для O(log(n))?

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

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

Здравствуйте, Тёмчик, Вы писали:

Тё>Бинарный поиск в отсортированном массиве- на помоечку? Будем искать перебором, забивая кэш процессора мусором?

Здравствуйте, Sharov, Вы писали:

S>если у нас будет в 100(1000,10000 и т.д.) раз больше элементов, то мы точно сможем сказать, что log(n) быстрее.
Точно можно сказать только померяв. Тем практика от теории и отличается, что на практике есть туча "движущихся частей" которые на первый взгляд не видны пока не посмотришь профайлером и не станешь разбираться что за фигня происходит.

S>В любом случае, если про это спрашивают на общих основаниях, то явно имеется в виду понимание сложности,
С этим никто не спорит. Речь была про то, что мало просто знать теорию, надо ещё иметь понимание нюансов, отсутствующих в этой теории + практику применения, чтобы всё это эффективно применять. Кроме того в сложных алгоритмах стоимость шага (та самая С) нифига не константа, а состоит из супа других подалгоритмов, так что сравнение реальной производительности "на бумаге" получается ещё веселее.

Здравствуйте, Тёмчик, Вы писали:

Тё>Такие приходили собеседоваться, включая и онлайн из России. Судя по тому, как у некоторых участников раскалён коллектор на bigO, как они пытаются доказать, что bigO не на первом месте по важности, делаю выводы.

Ну т.е. ты опять споришь сам с собой.

Здравствуйте, fmiracle, Вы писали:

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

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

Здравствуйте, CreatorCray, Вы писали:

S>>если у нас будет в 100(1000,10000 и т.д.) раз больше элементов, то мы точно сможем сказать, что log(n) быстрее.
CC>Точно можно сказать только померяв. Тем практика от теории и отличается, что на практике есть туча "движущихся частей" которые на первый взгляд не видны пока не посмотришь профайлером и не станешь разбираться что за фигня происходит.

Мне кажется теоретическую границу можно вывести каким-нибудь отношением "доступ RAM/L1", т.е.
пусть k="доступ RAM/L1", тогда если log n > k, то типа можно и нужно использовать log(n). Как-то так.

Здравствуйте, Sharov, Вы писали:

S>Мне кажется теоретическую границу можно вывести каким-нибудь отношением "доступ RAM/L1", т.е.
S>пусть k="доступ RAM/L1", тогда если log n > k, то типа можно и нужно использовать log(n). Как-то так.

Там ж не только для разных алгоритмов но и для разных типов обрабатываемых данных будут разные соотношения выходить.
Подобные ускорения за счёт locality лучше всего применяются когда юнит данных маленький, меньше чем cache line

Здравствуйте, CreatorCray, Вы писали:

CC>С этим никто не спорит. Речь была про то, что мало просто знать теорию, надо ещё иметь понимание нюансов, отсутствующих в этой теории + практику применения,
Эти "нюансы" вследствие упрощения модели. Сначала теория, потом нюансы. Но ты же только сейчас признал, что одной теории мало, а до того по твоим сообщениям складывалось ощущение, что ты против этой самой теории. Как состим или хайлендер, — у них пригорает пои упоминании про алгоритмы на собеседовании.

Здравствуйте, so5team, Вы писали:

S>>>Люди просто за меня довели твою мысль до логического завершения.
Тё>>Я не говорил этот бред про "коллекторов коллекторов".

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

Тё>>Это на твоей и твоих подхалимов совести.

S>Ну ладно мне, другим-то ты зачем хамишь?
Посмотри на твои посты. Там же оскорбления на уровне базарных продавцов. И ты после этого называешь "хамишь" за оценку поведения твоих подпевал?

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

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

S>Это не дизайн, это даже всерьез обсуждать невозможно.

Ну так аргументируй, конструктивно. Ведь проблему исключений в деструкторе этот дизайн решает, Ч.Т.Д.

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

S>Ко мне вопросов не было.
К тебе вопрос- конструктивно аргументируй критику предложенного дизайна.

Тё>>Глотать все исключения- это ненормально и никогда не было нормальным. Ни В C++, ни в Java.

S>Главное верить.
Мне тут коллега предлагает

[9/4, 10:12] : Catch all это путь к стрессу, согласен
[9/4, 10:13] : На пипку садить можно за кэтч ол

Тё>>Наблюдал минимум на 2 митапах плюсных в 2016-17гг. Что характерно, на митапах кложурных все с линуксом.

S>Понятно, голоса.
Ага, голоса. На 100 участников из самых крутых плюсных контор.

Здравствуйте, Тёмчик, Вы писали:

Тё>Но ты же только сейчас признал, что одной теории мало
C самого начала говорил.

Тё> а до того по твоим сообщениям складывалось ощущение
Как обычно у тебя угадайка работает просто отвратительно.

Здравствуйте, Тёмчик, Вы писали:

S>>Прочитай то, что тебе пишут. Не утверждалось что ты такое предлагал. Говорилось, что это логическое завершение твоей мысли.
Тё>Необязательно. Я уже указал, почему вызывать деструктор у непустого коллектора- натягивание совы на глобус.

Нет, не указал. Вызов деструктора -- неотъемлемая часть жизни объекта в C++, соответственно, деструктор должен корректно отработать при всех корректных инвариантах объекта. В том числе и когда список не пуст. Это же корректный инвариант.

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

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

S>>Ну ладно мне, другим-то ты зачем хамишь?
Тё>Посмотри на твои посты. Там же оскорбления на уровне базарных продавцов. И ты после этого называешь "хамишь" за оценку поведения твоих подпевал?

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

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

Навесить на этих людей ярлык "твои подпевала" -- это ты, Тёмчик, со зла.

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

S>>Это не дизайн, это даже всерьез обсуждать невозможно.

Тё>Ну так аргументируй, конструктивно.

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

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

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

Тё>Ведь проблему исключений в деструкторе этот дизайн решает, Ч.Т.Д.

Решение проблемы -- это не тогда когда более серьезные проблемы возникают в других местах.

S>>Главное верить.
Тё>Мне тут коллега предлагает
Тё>

Тё>[9/4, 10:12] : Catch all это путь к стрессу, согласен
Тё>[9/4, 10:13] : На пипку садить можно за кэтч ол

Так если ты этого коллегу собеседовал и он попал на работу по твоей рекомендации, то и не удивительно. Тем более, что тут явно нет обсуждения контекста, в котором catch all применяется. И если твой коллега не представляет себе контекст, в котором catch all использовали, то столь категоричные утверждения многое говорит о его квалификации.

S>>Понятно, голоса.
Тё>Ага, голоса. На 100 участников из самых крутых плюсных контор.

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

Здравствуйте, Тёмчик, Вы писали:

N>>Ты серьезно?! Сравнить местечковые мииапы с ежегодной международной конференцией, где выступают люди первой величины в профессии?
Тё>Местечковые конференции в HFT-й конторе

Тема, извини, но HFT в Сиднее уже само по себе звучит смешно

Здравствуйте, AndrewJD, Вы писали:

У>>Это тот Флойд, которого летом в штатах копы придушили?
AJD>Ты хотел сказать, который скопытился от передоза?

Типа того, да

Здравствуйте, Nuzhny, Вы писали:

Тё>>Мало ли что докладчики докладывают (часто откровенную хрень), это не ставит докладчика на уровень Александреску.

N>Это рецензируемые конференции как минимум. Это даже круче, чем работа в хорошей конторе чаще всего, потому что там неизвестно чем человек занимался, а тут полная публичность, обсуждение, рецензии со стороны. Более объективный критерий.

Мне эти конференции напоминают "Голубой огонёк"... во всех смыслах.

Здравствуйте, so5team, Вы писали:

Тё>>Мне тут коллега предлагает
Тё>>

Тё>>[9/4, 10:12] : Catch all это путь к стрессу, согласен
Тё>>[9/4, 10:13] : На пипку садить можно за кэтч ол

S> если твой коллега не представляет себе контекст, в котором catch all использовали,
Ого, уже на коллегу оскорбления.
Когда случился зашквар, то контекст этого нерелевантен по отношению к факту случившегося.


S>>>Понятно, голоса.
Тё>>Ага, голоса. На 100 участников из самых крутых плюсных контор.

S>Я сейчас общаюсь не с теми участниками, а с тобой. И мне приходится расшифровать выплески потоков сознания от голосов из твоей головы. Так что претензия не к участникам каких-то митапов, а к твоим рассказам об этих самых митапах. Бессмысленным и бессвязным.
Туши коллектор.

Здравствуйте, landerhigh, Вы писали:

L>Тема, извини, но HFT в Сиднее уже само по себе звучит смешно
IMC и Optiver — всё ещё смешно?
На фоне околожелезячного шнайдер, возможно, смех истеричен при сравнении зп.