Здравствуйте, 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 подписок на узел, -- совместило бы достоинства разных подходов...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Engler, Вы писали:
E>Здравствуйте, c-smile, Вы писали:
E>Если честно, я бы присмотрелся к Вашему тесту более внимательно.
E>1. Например, настораживает передача строки по значению. E>
E>FormatterType t2e(std::string s) { ... }
E>
Не важно. Ибо эта сигнатура используется во всех сравниваемых функциях.
E>2. В контейнерах, std::map / std::unordered_map вы храните объекты std::string, E>в то время когда в функция if_t2e сравнение идет с использованием обертки slice.
А это причем?
E>3. Дальше, маленькие объемы + еще std::string тот случай, когда нужно быть особенно внимательным, E>поэтому еще нужно посмотреть как компилятор работает со строками ( какие там оптимизации ), E>вполне возможно что разные компиляторы дадут разный результат.
E>4. Различные реализации std::hash / std::equal_to / std::less для std::string могут дать разные результат. E>5. Можно попробовать хранить const char* вместо std::string, возможно тоже покажет другой результат.
Я про это и говорю. Надо смотреть на реальную ситуацию, а не тупо брать std::map для поиска в наборе.
Здравствуйте, MTD, Вы писали:
MTD>Здравствуйте, c-smile, Вы писали:
CS>>Я про это тоже написал. Это примерно то что генерирует perfect hash (gperf).
MTD>Ну генерирует он сильно другое (насколько я помню), кроме того, при чем в контексте обсуждения он (это же генератор хеш-функции)?
gperf генерирует функцию в которой strcmp используется ровно один раз (т.е. полный проход строки). В качестве дискриминатора используется длина строки и один или несколько значений characters. Примерно тот же FSA что и ты написал как я понял.
Здравствуйте, rg45, Вы писали:
R>Здравствуйте, c-smile, Вы писали:
CS>>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.
R>Так ведь никто и не обещал, что O(1) ВСЕГДА будет быстрее O(log N), а O(log N) ВСЕГДА быстрее O(N). Потому, что все эти оценки задают лишь асимптотику зависимости времени выполнения от размера входной последовательности, но не являются точной зависимостью. Они позволяют лишь говорить о том, что существует такой размер входной последовательности, свыше которого O(1) начинает выигрывать у O(log N), а O(log N) у O(N). А вот каким будет этот размер, зависит уже от...
Ну собственно об этом и речь. Это все про эту вот цитату:
Практик: "Если он вызывается не один раз, то очевидно что std::map будет эффективнее, т.к. инициализация дерева будет происходить только один раз. И это кстати не теория — я использую на практике именно такой подход (только со string_view, а не string в качестве ключа для map)."
подвигла мя на написание статьи на тему. U>ты, к сожалению, не понял, что та дискуссия совсем не производительность, а про качество кода U>тебе даже форматтер кода намекнул об этом
Что есть такое "качество кода" в обсуждаемом контексте?
Здравствуйте, netch80, Вы писали:
N>Здравствуйте, c-smile, Вы писали:
CS>>Приводится случай когда O(N) lookup кроет O(1) как бык овцу.
N>В полтора раза (3.44 против 2.13) это "как бык овцу"? N>"Ну извините..." ((с) Вовочка) N>И заметим, всего-то при 9 записях линейный поиск уже хуже мапы. А что дальше?
CS>> А над O(log N) — вообще сплошное надругательство.
N>Аж на пару десятков процентов.
Ну дык, тут копеечка, там копеечка...
N>А если тут нужен действительно быстрый поиск — то как это делать — смотреть, например, в Kamailio:
N>
N>ну и так далее — строка нарезается стандартными порциями по 4 байта, переводится к нижнему регистру (SIP заголовки — case-insensitive) и затем задача компилятора — выбрать правильный вариант разложить case (обычно он строит что-то вроде дерева). Да, это очень жёсткая целевая оптимизация. Но там она оправдана.
Да вот тоже не факт на самом деле ...
1) endianness 2) перевод в нижний регистр это O(n) и 3) switch на разреженных case values это всё тот же linear lookup.
Немного лучше, но тем не менее нужно смотреть на конкретное распределение tokens probability. Про которые компилятор не знает ничего и может сгенерировать плохой lookup.
Здравствуйте, rg45, Вы писали:
R>Здравствуйте, c-smile, Вы писали:
CS>>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.
R>Так ведь никто и не обещал, что O(1) ВСЕГДА будет быстрее O(log N), а O(log N) ВСЕГДА быстрее O(N). Потому, что все эти оценки задают лишь асимптотику зависимости времени выполнения от размера входной последовательности, но не являются точной зависимостью. Они позволяют лишь говорить о том, что существует такой размер входной последовательности, свыше которого O(1) начинает выигрывать у O(log N), а O(log N) у O(N). А вот каким будет этот размер, зависит уже от...
В этих формулах еще есть константа, про которую забывают, которая и есть все эти хэши, кэши, предсказания ветвлений, прифечинг и прочее. При большом n ее влияние не значительно, поэтому в формулах ее и отбрасывают, а при малых n она как раз может оказать решающее влияние на скорость.
Здравствуйте, c-smile, Вы писали:
N>>Аж на пару десятков процентов. CS>Ну дык, тут копеечка, там копеечка...
Ну если уверены, что эта копеечка на что-то повлияет — ok, делать так. Оставив под, условно говоря, `#if 0` простой вариант.
N>>ну и так далее — строка нарезается стандартными порциями по 4 байта, переводится к нижнему регистру (SIP заголовки — case-insensitive) и затем задача компилятора — выбрать правильный вариант разложить case (обычно он строит что-то вроде дерева). Да, это очень жёсткая целевая оптимизация. Но там она оправдана.
CS>Да вот тоже не факт на самом деле ... CS>1) endianness
Решено основным случаем (для BE разворачивают порядок).
CS> 2) перевод в нижний регистр это O(n)
Он делается через or с 0x20202020 (или чуть меньшей маской, где не буква).
CS> и 3) switch на разреженных case values это всё тот же linear lookup.
Компиляторы часто строят switch как дерево ifʼов.
CS>Немного лучше, но тем не менее нужно смотреть на конкретное распределение tokens probability. Про которые компилятор не знает ничего и может сгенерировать плохой lookup.
Оно для этой задачи, грубо говоря, равномерно — вероятность встретить поле заголовка слабо зависит от букв начала его имени.
(Хуже то, что на нём любые branch prediction лажаются.)
Здравствуйте, c-smile, Вы писали:
CS>Не ходите дети в Африку гулять используйте std::map не по назначению.
А если бы ты в своем линейном поиске свел проверку к memcmp(), он победил бы во всех случаях.
При использовании perfect hash в реальной жизни было бы не лишне сделать в конце проверку, что мы нашли именно то, что искали. На заданном наборе он, конечно, не дает коллизий, но кто сказал, что его с гарантией накормят одной из валидных строк?
а можешь такой вариант проверить? идея в том чтобы положить все данные в массив и последовательно, так чтобы хорошо работал кэш, сравнивать куски памяти с помощью memcmp.
Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, c-smile, Вы писали:
CS>>Не ходите дети в Африку гулять используйте std::map не по назначению.
Pzz>А если бы ты в своем линейном поиске свел проверку к memcmp(), он победил бы во всех случаях.
А как это помогает?
Pzz>При использовании perfect hash в реальной жизни было бы не лишне сделать в конце проверку, что мы нашли именно то, что искали. На заданном наборе он, конечно, не дает коллизий, но кто сказал, что его с гарантией накормят одной из валидных строк?
Здравствуйте, c-smile, Вы писали:
Pzz>>А если бы ты в своем линейном поиске свел проверку к memcmp(), он победил бы во всех случаях.
CS>А как это помогает?
Быстрее работает, чем сравнивать строки в цикле побайтово.
Здравствуйте, Engler, Вы писали: E>Здравствуйте, c-smile, Вы писали: E>Если честно, я бы присмотрелся к Вашему тесту более внимательно.
Посмотрел немного более внимательно.
Мне все-таки кажется, что сравнение в тесте не совсем корректное.
Функция,
FormatterType if_t2e(std::string name)
Сам код в этой функции дает определенные подсказки компилятору.
Судя по всему очень хорошо инлайнится, + возможно еще есть магия опцимизации ( я там не во всем разбирался ).
И это, не совсем честный линейный поиск. Вместо этого, по хорошему надо делать поиск в std::vector.
Тогда получится, что вы сравниваете похожие вещи.
А вот кстати, поведение std::unordered_map::find меня удивило.
Она вызывает lower_bound, которая в свою очередь уже
1) строит хеш [вызывается кастомный функтор], что в общем-то естесвенно
2) вызывает опреатор == ( для поиска элеметна в листе , на который указывает bucket )
3) вызывает опреатор == еще раз ( пока не понял зачем ).
В итоге мы имеем хорошо оптимизированную функцию if_t2e,
против непонятно какой реализации unordered_map.
Здравствуйте, MTD, Вы писали:
MTD> Для оценки скорости алгоритмов предлагается использовать его асиптотику — это не всегда верно. Например, у бинарного дерева и упорядоченного массива асимптотика поиска
Какая-то фигня.
Бинарное дерево можно реализовать in-place в массиве. А упорядоченный массив может быть массивом указателей с кеш-промахами. И внезапно дерево заработает быстрее упорядоченного массива.
Просто надо учитывать конкретные реализации структур данных — чем именно занимается процессор, а не оперировать абстрактными типами. Тогда не придётся "слепо верить", а просто тупо считать.
По сабжу: мне кажется самым эффективным и универсальным будет std::vector<std::pair<char[MAX_KEY_SIZE], FormatterType>> отсортированный по pair.first и искать в нём используя binary_search (кстати, там имхо реализована оптимизация для малых размеров).
Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, c-smile, Вы писали:
Pzz>>>А если бы ты в своем линейном поиске свел проверку к memcmp(), он победил бы во всех случаях.
CS>>А как это помогает?
Pzz>Быстрее работает, чем сравнивать строки в цикле побайтово.
Нет, не быстрее:
Это вот 2.82 секунды
bool operator == ( const slice& r ) const
{
if( length != r.length )
return false;
for( unsigned int i = 0; i < length; ++i )
if( start[i] != r.start[i] )
return false;
return true;
}
Здравствуйте, MTD, Вы писали:
MTD>Речь не только про малые n.
Ух ты. Хотелось бы посмотреть, как линейный поиск обойдет лучшие асимптотически алгоритмы при n хотя б в миллион. А лучше в миллиард.
MTD>Для оценки скорости алгоритмов предлагается использовать его асиптотику — это не всегда верно. Например, у бинарного дерева и упорядоченного массива асимптотика поиска одинакова — логарифм. Значит ли это, что они одинаково эффективны? Нет, ведь дерево может быть размазано по памяти из-за этого возникнут постоянные промахи в кеш и упорядоченный массив окажется в разы эффективней. Рассматривается это у Кнута? Нет, вот о том и речь.
Кеш промахи и все такое имеют значение только для малых n. Но даже без учетов архитектуры современных процессоров, алгоритмы в лоб чаще проще и в результате за 1 проход выполняется меньшее количество команд. Соответственно да, для малых n простой алгоритм может быть быстрее и даже скорее всего будет. Но с ростом n всегда получится дерьмо. Учетом архитектуры процессора и тому подобного на больших n ты максимум поднимешь производительность в 10 раз. Ладно, даже в 100. Ладно, даже в тысячу, хоть это и маловероятно. Вот только смена асимптотики — это ускорение может быть в миллионы и миллиарды раз. Главное чтоб памяти хватило чтоб это n вместить.
Читать написанное мной не пробовал? Попробуй, потом покажи пальцем, где я там линейный поиск называл панацеей.
E>Кеш промахи и все такое имеют значение только для малых n.
Да что ты говоришь. Вот у тебя есть 100 терабайт данных — это малое n? Теперь представь, что у тебя есть оперативная память (кеш) и дисковый массив. Тебе все еще не очевидно, что количество промахов надо минимизировать?
E>Вот только смена асимптотики — это ускорение может быть в миллионы и миллиарды раз.
Да, так обычно получается, если не прочитать, но начать отвечать.
·>Бинарное дерево можно реализовать in-place в массиве. А упорядоченный массив может быть массивом указателей с кеш-промахами. И внезапно дерево заработает быстрее упорядоченного массива.
Молодец. Любопытно, что побудило тебя написать это?
·>Просто надо учитывать конкретные реализации структур данных — чем именно занимается процессор, а не оперировать абстрактными типами.
Я никак не пойму, ты с чем споришь? Я где-то отрицал, что надо учитывать конкретные реализации структур данных?
·>По сабжу: мне кажется самым эффективным и универсальным будет std::vector<std::pair<char[MAX_KEY_SIZE], FormatterType>> отсортированный по pair.first и искать в нём используя binary_search (кстати, там имхо реализована оптимизация для малых размеров).
Универсальное решение всегда проигрывает в каком-то случае частному. Я думаю, до какого-то n (не знаю какого — надо бенчмаркать) ничего быстрее автомата не будет, потом возможно начнет рулить бинарный поиск, а затем хеш-таблица, дальше уже начнутся всякие фильтры Блума вместе со всякими экзотическими структурами.
Здравствуйте, MTD, Вы писали:
MTD>·>Какая-то фигня. MTD>Да, так обычно получается, если не прочитать, но начать отвечать.
Я наверное просто к словам придираюсь. " асимптотика поиска одинакова — логарифм" — это верно для абстактной структуры "дерево", "массив". А имплементация даёт изменение асимтотики — индирекция, промах в кеш это по сути дополнительный lookup для процессора, который начинает использовать ассоциативный контейнер страниц памяти для их подгрузки в свой кеш. Т.е. на уровне языка программирования вроде как одно и то же, но если смотреть все слои всего вычислительного устройства — то уже фигня получается. То же и с предсказанием ветвления — это ведь тоже по сути алгоритм со своей сложностью — не всегда его влияние можно отбрасывать.
Т.е. проблема не в асимтотике, а в том как её считают — не учитывают "незначительные" детали.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, MTD, Вы писали:
MTD>Шапочка из фольги спасет от голосов в голове и вернет душевное здоровье.
Шапочка из фольги на самом деле отражает внутренние голоса обратно в голову. Из-за чего процесс зацикливается и из него нету выхода. Перегрев одним словом наступит.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, c-smile, Вы писали: CS>Здравствуйте, Engler, Вы писали: E>>Здравствуйте, Engler, Вы писали: E>>В итоге мы имеем хорошо оптимизированную функцию if_t2e, CS>Что там оптимизировано-то?
Например gcc, вначале сравнивает строки одинаковой длинны (4 байта), потом более длинной, и.т.д
Это если я правильно понял, конечно.
( update: причем компилятор разварачивает сравнение вот таким вот образом
if (str[0] != 't') goto ...
if (str[1] != 'e') goto ...
if (str[2] != 'x') goto ...
if (str[3] != 't') goto ...
И так для всех строк
) CS>Банальный же if-elif-elif-else... т.е. последовательный (линейный) перебор.
Банальность, это ключ
Я немного добавил тестов, что бы точнее понять, что присходит.
Я добавил 2 вектора [вооще 4, с разным порядком строк, отсортированным по длине, и оригинальным]
std::vector<pair< string, FormatterType> > и
std::vector<pair< aux::chars, FormatterType> > и
Еще в клоне if_t2e немного нагадил компилятору с помощью volatile, потому что могу
и что бы он не харкодил значения, а "честно" читал их как в случае c std::vector
Вот теперь, попытка интерпретации результатов.
Что мы имеем.
"Банальный поиск" выигрывает у поиска по std::string в std::vector и у slice в std::vector.
"Банальный поиск" в результате превращается в оптимизированный вариант сравнения с констатами.
Оптимизированный, потому что строки выклаюыватся по длине в определенным образом.
Сравнение с константами, потому что компилятор может их подставить.
Давай-те попробуем усложнить задачу, и попробовать запретить подстановку строк с помощью volatile ( пришлось дописать конструктор с volatile ).
И увидим, что if_t2e_disable_opt уже выросла в почти 2 раза ( и равно обычному линейном поиску в std::vector для slice ),
что подталкивает не мысль, что обращение к памяти ( или кешу, тут уже не знаю ) ухудшает работу.
Но все равно поиск по строкам занимает больше времени.
Если взглянуть на реализацию сравнения std::string и slice мы увидим, что:
slice делает меньше телодвижений ( сравнивается только длина и значения )
std::string делает больше работы ( во всяком случае под дебагом в VS ):
1. Есть сравнение длинны строки ( из за SSO оптимизации ) это раз.
2. Сравнение реализовано через int compare, т.е результат может быть "равно" , "больше", "меньше",
а это требует, как минимум еще одного сравнения длинны. И только потом уже мы можем перейти непосредсвенно к сравнению строк.
Похоже, что на 10,000,000 итерации эти несколько "лишних" сравнений и ухудшают результат.
Это кстати ответ, на вопрос в вашем другом посте ( в чем разница, между хранением std::string и slice: короткий ответ в реализации operator==)
А вот ручное выкладывание строк по порядку, результато не дало.
сообщение той темки. Непонятно зачем ты завёл новую. Разве что хотелось ещё поговорить об этом, но нечего было ответить на то сообщение? )))
Можно вопрос, std::string_view , как раз использует лексикографический порядок, http://en.cppreference.com/w/cpp/string/basic_string_view/operator_cmp. Или я что-то упускаю? Каким способом можно еще сравнить строки, если не лексикографическим порядком (всмысле, как сделать операцию < еще легче)?
сообщение той темки. Непонятно зачем ты завёл новую. Разве что хотелось ещё поговорить об этом, но нечего было ответить на то сообщение? ))) E>Можно вопрос, std::string_view , как раз использует лексикографический порядок, http://en.cppreference.com/w/cpp/string/basic_string_view/operator_cmp. Или я что-то упускаю?
И у std::string и у std::string_view оператор сравнения является лексикографическим, о чём я собственно и написал в сообщение по ссылке выше. Однако std::map совершенно не обязан его использовать — это всего лишь значение по умолчанию для 3-го параметра шаблона map, который в случае принципиальности быстродействия естественно устанавливается свой.
E>Каким способом можно еще сравнить строки, если не лексикографическим порядком (всмысле, как сделать операцию < еще легче)?
Да как угодно, лишь бы работал быстро и позволял реализовывать некую сортировку. Например по ссылке выше есть рабочий пример подобного оператора, с которым std::map работает быстрее линейного поиска даже на маленьких перечислениях.