- 1
- 2
- 3
- 4
>Сложность получается лучше O(1).
>Не надо бросаться грудью на амбразуру, посиди — подумай.
>Как оказалось, самый быстрый алгоритм — это линейный поиск и никакие map/bitset не нужны.-
Куча / Говнокод #21836
−15
Будни мамкиного питимизатора
https://habrahabr.ru/post/317588/Запостил:
3.14159265,
14 Декабря 2016
Follow us!
А там Цари переобулись на C++.
При достаточно большом x задача решается без единой инструкции!
При фиксированном m c ростом n количество итераций будет уменьшаться, т.к. вероятность встретить 0 тоже уменьшается.
Ваша формула наверняка считает число попыток до первой "удачи", не включая саму "удачу". У нас же
> выбрать элемент по случайному индексу
Нам же нужно вернуть этот элемент, а не просто нагреть процессор, так ведь? Следовательно, "удачу" тоже считать надо, а для этого хотя бы одно движение сделать нужно.
* Это простое доказательство оставим для читателя
** Гиперреальную
правильнее работает == подтверждает мою точку зрения?
1+ из формулы можно успешно выпилить, да.
Чистые O(10/n) = O(1/n)!
>Как оказалось, самый быстрый алгоритм — это линейный поиск
Не надо бросаться грудью на амбразуру, посиди — подумай.
>он опережает все аналоги.
Он работает не во времени, но в пространстве!
Экстраполяция: со временем Царь будет использовать языки всё выше и выше уровнем.
В какой-то момент он откроет, что перфоманс программы написанной в pointfree стиле является самым царским, интринсики сменятся на GHC rewrite rules.
Наконец он откроет для себя Wolfram Mathematica и функцию D.
Кстати, надо будет поглядеть на код из Arrival, может, там чего весёлое найдётся
Хм, врядли, там сын Вольфрама над кодом работал
>интринсики сменятся на GHC rewrite rules.
Но всё-равно будет продолжать жрать кактус, пытаться "заставить инлайниться ассемблерный код".
>Как оказалось, самая лучшая структура данных -- это массив, а никакие деревья не нужны
>Как оказалось, самое лучшее место для хранения данных это файл, разделенный запятыми, а никакие Oracle и MS-SQL не нужны
>Как оказалось, самый лучший issue tracker это желтые листочки на мониторе, а никакие jira/youtrack не нужны
>Как оказалось, самый лучший программист это я, а вы все не нужны
>Значит придётся смотреть комбинаторику, но мне это не сильно помогло, так как достаточного объёма знаний по этой теме я не имею, пришлось выписывать примерно такой же пример на бумажку и подумать.
>Идём самым простым путём: берём boost::multiprecision::uint128 — вот его нам хватит надолго! Это из-за того, что я пользуюсь MS CL, а он просто не поддерживает uint128, как все остальные компиляторы.
>Тут уже задача начинала надоедать, так как быстрее уже не получалось и я занялся C# версией. Всё перенёс туда. Нашёл уже готовый, написанный другим человеком UInt128 — примерно такой же простой, как и мой для C++.
>А вот самописный map проигрывает по всем статьям Dictionary. Видимо проверки границ массивов дают о себе знать, ибо увеличение памяти ничего не даёт.
>Дальше уже пошла совсем ерунда, даже была попытка оптимизировать сложение интринсиками, но чисто C++ версия оказалась самой быстрой. У меня почему-то не получилось заставить инлайниться ассемблерный код.
В последнее время в прессе муссируются структуры данных. Абстрактные типы данных, структуры, указатели, списки и строки стали популярны в определенных кругах. Вирт, сосунок, написал даже целую книгу ("Алгоритмы + Структуры данных = Программы", Prentice Hall, 1976 [русский перевод - изд. "Мир", 198?]), в которой утверждает, что можно написать программу на базе структур данных, не используя другие способы. Как все настоящие программисты знают, единственной полезной структурой данных является массив. Строки, списки, структуры и наборы - это все разновидности массивов и их можно рассматривать как массивы без усложнения вашего языка приграммирования. Хуже всего с этими хитрыми типами данных то, что вы должны их описывать, а настоящие языки программирования, как мы все знаем, обладают возможностью неявного задания типа, основанного на первой букве 6-символьного имени переменной.
Но это же ограничивает количество переменных целого типа, используемых в программе!
Серьёзно, я видел проект на фортране, где список переменных инклюдили в каждую функцию из отдельного файла.
У меня в паскале были переменные i1, i2 .. iN, и я их переюзал.
Не потому что мне было жалко места в стеке, а потому что определять переменную можно было только вверху, и мне было лениво туда скролиться каждый раз.
Соответственно, вход в контекст запилит новый список переменных, hold займёт свободную переменную из пула или создаст новую, release - освободит.
Вроде это универсальная фигня, хватит для всех популярных языков. Дальше для разных языков - только в объявлении разница будет.
Для объявления указателей на функции и массивов в C/C++ можно использовать typedef, затем ~hold f:my_fun_t сработает как надо.
Ох, может и правы были жабоёбы, когда не завезли в свой ЯП препроцессора.
Может быть и с C# он зря.
Одно дело DEBUG передать, но за "#if (SEARCHMAP)" _посреди_ метода надо убивать