Здравствуйте, c-smile, Вы писали:
CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу[/url].
Поэтому Кнута и ко надо читать с осторожностью — хоть парни и толковые, но инфа несколько устарела, если не учитывать устройство современного процессора (всякие кеши, предсказание переходов), то можно легко напороться на то, что алгоритм с худшей асимптоматикой внезапно уделывает алгоритм с хорошей. Ну и вообще стоит прикидывать стоимость операций — внезапно может оказаться, что при вставке на небольшом массиве со сдвигом, чтобы сохранить упорядоченность и бинарный поиск, уделывают деревья только так.
Если честно, я бы присмотрелся к Вашему тесту более внимательно.
1. Например, настораживает передача строки по значению.
FormatterType t2e(std::string s) { ... }
2. В контейнерах, std::map / std::unordered_map вы храните объекты std::string,
в то время когда в функция if_t2e сравнение идет с использованием обертки slice.
3. Дальше, маленькие объемы + еще std::string тот случай, когда нужно быть особенно внимательным,
поэтому еще нужно посмотреть как компилятор работает со строками ( какие там оптимизации ),
вполне возможно что разные компиляторы дадут разный результат.
4. Различные реализации std::hash / std::equal_to / std::less для std::string могут дать разные результат.
5. Можно попробовать хранить const char* вместо std::string, возможно тоже покажет другой результат.
В полтора раза (3.44 против 2.13) это "как бык овцу"?
"Ну извините..." ((с) Вовочка)
И заметим, всего-то при 9 записях линейный поиск уже хуже мапы. А что дальше?
CS> А над O(log N) — вообще сплошное надругательство.
Аж на пару десятков процентов.
Нет, тут понятно, что std::map обычно медленнее std::unordered_map (если не слишком дорого вычислять хэш), но Ваш пример как раз _против_ того, чтобы тут был выбран линейный поиск по умолчанию.
Потому что какая-то мапа тут по природе вещей и хорошо масштабируется, а замена на линейный поиск будет типичной преждевременной оптимизацией со всеми своими последствиями. Если это место станет узким и будет гарантия неувеличения количества ключевых строк — тогда можно сократить до линейного поиска. Если хотя бы одно условие не выполняется — закат солнца вручную отменяется.
А если тут нужен действительно быстрый поиск — то как это делать — смотреть, например, в Kamailio:
#define _acce_ 0x65636361 /* "acce" */#define _allo_ 0x6f6c6c61 /* "allo" */#define _auth_ 0x68747561 /* "auth" */#define _oriz_ 0x7a69726f /* "oriz" */#define _atio_ 0x6f697461 /* "atio" */#define _call_ 0x6c6c6163 /* "call" */#define __id2_ 0x2064692d /* "-id " */#define __id1_ 0x3a64692d /* "-id:" */
[...]
#define FIRST_QUATERNIONS \
case _via1_: via1_CASE; \
case _from_: from_CASE; \
case _to12_: to12_CASE; \
case _cseq_: cseq_CASE; \
case _call_: call_CASE; \
case _cont_: cont_CASE; \
case _rout_: rout_CASE; \
case _max__: max_CASE; \
ну и так далее — строка нарезается стандартными порциями по 4 байта, переводится к нижнему регистру (SIP заголовки — case-insensitive) и затем задача компилятора — выбрать правильный вариант разложить case (обычно он строит что-то вроде дерева). Да, это очень жёсткая целевая оптимизация. Но там она оправдана.
CS>Не ходите дети в Африку гулять используйте std::map не по назначению.
Вы не показали, на каком количестве значений std::map эффективнее линейного поиска. Это уже некрасиво.
И VS-only code тоже сейчас как-то "не очень".
Здравствуйте, c-smile, Вы писали:
CS>Не ходите дети в Африку гулять используйте std::map не по назначению.
Игра в бирюльки по сравнению с оптимизацией критического по времени кода через интринсики, форсинлайн, гоуту и т.д..
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Так ведь никто и не обещал, что O(1) ВСЕГДА будет быстрее O(log N), а O(log N) ВСЕГДА быстрее O(N). Потому, что все эти оценки задают лишь асимптотику зависимости времени выполнения от размера входной последовательности, но не являются точной зависимостью. Они позволяют лишь говорить о том, что существует такой размер входной последовательности, свыше которого O(1) начинает выигрывать у O(log N), а O(log N) у O(N). А вот каким будет этот размер, зависит уже от...
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, MTD, Вы писали:
MTD>Здравствуйте, c-smile, Вы писали:
CS>>Приводится случай когда O(N) lookup кроет O(1) как бык овцу[/url].
MTD>Поэтому Кнута и ко надо читать с осторожностью — хоть парни и толковые, но инфа несколько устарела, если не учитывать устройство современного процессора (всякие кеши, предсказание переходов), то можно легко напороться на то, что алгоритм с худшей асимптоматикой внезапно уделывает алгоритм с хорошей.
Асимптотика описывает поведение при стремлении переменной к чему-то. В применении к сложностям алгоритмов рассматривается характер поведения при увеличении переменной, или стремлении к бесконечности. Кроме того, O(f(n)) — это верхняя оценка по определению, которая лишь указывает что существует константа и такое n0, что рост сложности алгоритма при n >= n0 будет соответствовать некоторой модели с точностью до этих констант. То есть, асимптотика не предназначена для описывания нижних оценок на малых n.
Причем Кнут — не понятно. Он не утверждает обратного.
Пару лет назад столкнулись с похожей историей. Посмотрели, как ведут себя разные структуры данных для хранения подписок агентов в зависимости от количества этих самых подписок. Оказалось, что если подписок всего один-два десятка, то хранение подписок в std::vector и простой линейный перебор по нему работает эффективнее всего. Если количество подписок находится в районе от пары десятков до пары сотен, то эффективнее работает std::map. А вот от 200+ подписок -- самым эффективным оказывается std::unordered_map.
Здравствуйте, samius, Вы писали:
S>То есть, асимптотика не предназначена для описывания нижних оценок на малых n.
Речь не только про малые n.
S>Причем Кнут — не понятно.
При том, что Кнут не учитывал, как алгоритмы выполняются на современном железе, такая теория в вакууме. Знать надо, но каждый раз надо думать, а слепо верить в О.
S>Он не утверждает обратного.
Для оценки скорости алгоритмов предлагается использовать его асиптотику — это не всегда верно. Например, у бинарного дерева и упорядоченного массива асимптотика поиска одинакова — логарифм. Значит ли это, что они одинаково эффективны? Нет, ведь дерево может быть размазано по памяти из-за этого возникнут постоянные промахи в кеш и упорядоченный массив окажется в разы эффективней. Рассматривается это у Кнута? Нет, вот о том и речь.
подвигла мя на написание статьи на тему.
ты, к сожалению, не понял, что та дискуссия совсем не производительность, а про качество кода
тебе даже форматтер кода намекнул об этом
CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.
бенчмарки хороши тем, что можно любое решение засунуть в топ, а неудобные цифры просто не публиковать
CS>Не ходите дети в Африку гулять используйте std::map не по назначению.
сам-то понял, что сказал? (с)
у меня для тебя плохие новости: назначение мапы быть ассоциативным контейнером, то есть хранить ключи и значения и искать по ключам
ты хоть выводы может внятно сформулировать? вот сортировка пузырьком тоже в топ иногда выходит, но выводы из этого надо ещё уметь сделать
Здравствуйте, MTD, Вы писали:
S>>Причем Кнут — не понятно.
MTD>При том, что Кнут не учитывал, как алгоритмы выполняются на современном железе, такая теория в вакууме. Знать надо, но каждый раз надо думать, а слепо верить в О.
Я бы сказал "каждый раз надо измерять", а не "думать". "Думать" оно надо, но не это ключевое.
А "неучёт на современном железе" это специфика не только Кнута. Я навскидку сейчас посмотрел Кормена, Сиену, Седжвика — нигде не упоминается — по крайней мере нет ни в оглавлении, ни в предметном указателе. Поэтому следует полагать, что им в пару обязательно читать "Computer achitecture: a quantitative approach" или аналог.
Ещё Вы почему-то распространяете паразитную логическую связь "алгоритмы, сложность -> Кнут". Кнут — фундамент и историческая база, но сейчас его использовать в качестве абсолюта уже поздновато.
S>>Он не утверждает обратного.
MTD>Для оценки скорости алгоритмов предлагается использовать его асиптотику — это не всегда верно. Например, у бинарного дерева и упорядоченного массива асимптотика поиска одинакова — логарифм. Значит ли это, что они одинаково эффективны? Нет, ведь дерево может быть размазано по памяти из-за этого возникнут постоянные промахи в кеш и упорядоченный массив окажется в разы эффективней. Рассматривается это у Кнута? Нет, вот о том и речь.
Реальный мир надо всегда учитывать. Где-то алгоритм в 100 раз быстрее на RAM, но в 2 раза прожорливее по объёму памяти затормозится из-за трэшинга свопа. Где-то очень эффективная обычно сортировка станет вдруг медленнее пузырька из-за того, что сравнение в 1000 раз дороже обмена.
Вы читая Кнута почему-то смотрите только на выводы, а не на проведённый им анализ. А ведь то, чему он учит — это именно анализировать от основ. И при всём при этом не знаете никого, кроме Кнута... просто пугаете этим.
Здравствуйте, netch80, Вы писали:
N>Вы читая Кнута почему-то смотрите только на выводы, а не на проведённый им анализ. А ведь то, чему он учит — это именно анализировать от основ. И при всём при этом не знаете никого, кроме Кнута...
Телепатам привет!
N>просто пугаете этим.
Шапочка из фольги спасет от голосов в голове и вернет душевное здоровье.
Здравствуйте, MTD, Вы писали:
MTD>Здравствуйте, samius, Вы писали:
S>>То есть, асимптотика не предназначена для описывания нижних оценок на малых n.
MTD>Речь не только про малые n.
Но таки про нижние оценки?
S>>Причем Кнут — не понятно.
MTD>При том, что Кнут не учитывал, как алгоритмы выполняются на современном железе, такая теория в вакууме. Знать надо, но каждый раз надо думать, а слепо верить в О.
Так и на современном железе стоимость выполнения шага алгоритма неотрицательна. Не понимаю, что изменилось в этом плане со времени выхода книги. Тем более, что Кнут не предлагал слепо верить в О. Не знаю, из какой именно фразы вы сделали такой вывод.
S>>Он не утверждает обратного.
MTD>Для оценки скорости алгоритмов предлагается использовать его асиптотику — это не всегда верно.
Это не так. Асимптотику предлагается использовать для прогноза роста стоимости алгоритма при увеличении n. При том, что M и x0 неизвестны, как об этом и указал Кнут.
MTD>Например, у бинарного дерева и упорядоченного массива асимптотика поиска одинакова — логарифм. Значит ли это, что они одинаково эффективны? Нет, ведь дерево может быть размазано по памяти из-за этого возникнут постоянные промахи в кеш и упорядоченный массив окажется в разы эффективней. Рассматривается это у Кнута? Нет, вот о том и речь.
Речь тут ровно о том, что вы сделали неверную оценку и прогноз. Неверно выбрали M и x0 при оценке скорости работы алгоритмов на дереве в условиях постоянных промахов. Нет никаких оснований утверждать на одинаковую эффективность алгоритмов с одной асимптотикой, не зная констант. Именно об этом Кнут и писал.
Ну, это не новость давно уже. "Умелки" процессора, размер кэшей, характер данных, их расклад в памяти и прочие вроде бы мелочи способны смешать с грязью самые теоретически-лучшие алгоритмы.
Здравствуйте, MTD, Вы писали:
MTD>Здравствуйте, c-smile, Вы писали:
CS>>Приводится случай когда O(N) lookup кроет O(1) как бык овцу[/url].
MTD>Поэтому Кнута и ко надо читать <...> внезапно может оказаться, что при вставке на небольшом массиве со сдвигом, чтобы сохранить упорядоченность и бинарный поиск, уделывают деревья только так.
1) Дык потому структуры вроде B-tree и придумали...
2) У того Кнута, которого когда-то читал я, было прямо написано, что какой бы распрекрасный рекурсивный алгоритм с очень хорошей асимптотикой вы не придумали, обычно начиная с некоторого размера и меньше, надо переключаться на что-то быстрое на маленьких данных
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, so5team, Вы писали:
S>Пару лет назад столкнулись с похожей историей. Посмотрели, как ведут себя разные структуры данных для хранения подписок агентов в зависимости от количества этих самых подписок. Оказалось, что если подписок всего один-два десятка, то хранение подписок в std::vector и простой линейный перебор по нему работает эффективнее всего. Если количество подписок находится в районе от пары десятков до пары сотен, то эффективнее работает std::map. А вот от 200+ подписок -- самым эффективным оказывается std::unordered_map.
Можно было сделать B-tree на 10-20 подписок на узел, -- совместило бы достоинства разных подходов...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
