Раз уж вы тут за философию пишите, открою секрет - почему. Глупые деньги. Индустрия находится на закате стандартного 30 летнего технологического цикла и максимума хайпа. Люди закапывают деньги в песок, чаще всего не свои.
Нет смысла воевать с ветреными мельницами. Если хотите доводить проекты до конца, найдите место где это ценят(возможно придется постараться).
Компилятор не может порождать эффективный код для SIMD(на x86_64 это SSE/AVX), который выходит за пределы довольно простых паттернов векторизации. Поэтому его пишут на intrinsic которые практически однозначно отображаются в ассемблерные команды (за компилятором остается только распределение регистров) И как-то с "этой бедой" где реально нужна скорость (кодеки/растеризация/криптография/нейросетки на CPU) справляются, а те кто не справляются ищут себе более подходящее занятие.
Опен соурс редко существует в вакууме. Те кто в него комитит и завязал на него свои продукты/разработки, рассчитывали на определенные правила игры, когда на это подписывались. А именно наличие определенной OSS лицензии. Поэтому вполне логично, что если кто-то решил поменять правила игры, будут те кто с ним не согласится и все таки захочет играть по старым правилам и сделает форк. Так что как по мне, так тут все и в рамках права, этики, да и логики нормально.
Помню историю SCO против Linux там вот реально все было за гранью добра и зла.
Если нормально писать код и думать, что он в принципе будет собираться плюсовым компилятором - все будет хорошо. То что есть какое-то количество edge case, которые не будут работать - да это так. И что? Какое это отношение, вообще имеет к практической разработки?
Вопрос ни в том, что произвольно взятый код на C будет компилироваться плюсовым компилятором. А в тех усилиях, которые надо приложить, чтобы он начал компилироваться. И эти усилия на самом деле минимальны, с точки зрения общих затрат на разработку. Думаю в приведенном примере с redis, это все чинится максимум за человеко-неделю разработчика.
Собственно мало, кто знает/помнит, но основной sailing point плюсов в конце 80-х начале 90-х был - "вы можете не выбрасывать свою сишную кодо базу, а начать постепенно переносить ее на плюсы".
Какая доля людей, по-вашему, на самом деле использует эту базу даже в машинке?
Использует это не очень правильный термин. Можно слать промпты в LLM и считать, что занимаешься машинным обучением. Можно ли понимать без этой базы(к слову довольно тривиальной, топология там точно не нужна), что происходит под капотом современных моделей и подходов машинного обучения - крайне сомнительно.
Конечно, можно начинать разбираться в машинном обучении без базы, постепенно изучая, то что не понимаешь. В результате изучив ровно тоже самое, но при этом потратив еще больше времени, чем при систематическом обучении.
Возможно, вы имели в виду «потраченная». Потому что можно в эту молодость, собсна, общаться с людьми и всё такое, что там в молодость делают, а потом уже поздно, а можно поглаживать многообразия до четырёх утра.
Да, ладно как будто студенты эти многообразия до утра, каждый день гладят. Чаще всего это ближе к сессии, приходило. А так ВУЗ это место сосредоточения не самых глупых людей (по крайней мере относительно), наделенных какой-то целью. (хотя бы закончить ВУЗ)
Можно общаться с людьми, из соседнего подъезда, или сразу грузчиком в Пятерочку или "менеджером" пойти, тоже будет много интересного общения. Если ты из условно "средне статистической/простой семьи", то и веток развития будет на самом деле, совсем немного.
Хорошо бы разделить собственно фундаментальные знания, и ВУЗ как средство их получения.
Фундаментальный плюс фундаментальных знаний, что они устоялись и не меняются каждые полгода-год, как новомодный фрэймворк. Если вы выучили алгоритмы и структуры данных, реляционные СУБД, принципы работы операционных систем, основы работы процессора, принципы написания чистого кода, проектирования и ООП. То эти знания останутся с вами навсегда, какой бы новомодный фрэмворк или язык программирования вам не пришлось бы использовать на практике.
Что касается математики, то да, можно согласиться что ее применимость в практическом программировании довольно не велика. Особенно если заниматься в основном перекладыванием джэйсонов. Но стоит шагнуть немного в сторону и оказывается, ни все так просто. То же машинное обучение, выше уровня обезьянки запускающей код с гитхаба, практически невозможно адекватно понять без математической базы: теор. вер, линейной алгебры, дифференциальное исчисление, элементарного понимания, что такое градиент и т.д.
И тут мы подходим к основному пункту. Хорошо когда ты молодой и влет изучаешь очередной фрэймворк. После 35 это становится уже ни так просто. И оказывается, что фундаментальные знания это то на чем можно ехать долгое время, даже если ты в айти уже двадцать лет.
И в качестве завершения. Фундаментальные знания != ВУЗ, их вполне можно получить самому. Достаточно вкалывать часов по 6 в день в течении года, за это время можно освоить практически всю полезную программу. Но только ВУЗ это не только про получение знаний, это молодость, студенчество, знакомства, даже то же самое "научить учится" для тех кто этого не умел. Ни все так просто, как кажется на первый взгляд.
С потоками в opensource вообще проблематично, я к сожалению хороших пакетов не знаю. Раньше была библиотека от Гольдберга, но кажется, что он лет 20 назад на неё забил.
Такова экономическая реальность за пределами "успшеного успеха ютуба". Рынки эффективны, это означает что если вы зарабатываете значимо больше ключевой ставки(а иначе проще деньги на депозит положить), то у вас неизбежно появятся конкуренты. И если рынок достаточно большой, придут большие профессиональные деньги, и сделают дешевле, и с разумным качеством. Конкурировать частнику с индустриальными способом производства обычно крайне тяжело. (история про ферму против молоко завода)
В конечном итоге, если хотите заняться бизнесом, надо ответить на базовые вопросы. Составить хотя бы отдаленно реалистичный бизнес план. Продумать какие могут быть административные, технологические и другие барьеры для входа конкурентов на рынок. Или возможно рынок достаточно небольшой и нишевой, за счет чего не интересен большим деньгам (привет когтеточки). И даже если решите заняться своим делом, не стоит вкладывать больше чем 1/2-1/3 от накоплений, и тем более лезть в кредиты. Иначе проще в сразу в казино идти, там хотя бы шансы будут больше.
Не надо пожалуйста издеваться над здравым смыслом. Определение графа знаете? Набор вершин и дуг, в котором дуги являются парами связных вершин, плюсом веса для дуг в нашем случаи. Никакого порядка там в принципе не предусмотрено. Не говоря уже о различных представлениях в виде матриц смежности.
3. Замените половину весов на отрицательные и посмотрите, что там посчитается.
"Нужно писать узлы графа в порядке их отдаленности от источника. Т.е. сперва описываем первых соседей источника. После того, как описали их, приступаем к следующим соседям соседей."
Таким образом вы решаете не известную задачу, а какую-то другую. Соответственно, чтобы получить честные оценки асимптотики, нужно добавить этот этап препроцессинга
Сложность Дейкстры при нормальной реализации, это "Dijkstra's algorithm with Fibonacci heap O ( E + V log V )", или "Dijkstra's algorithm with binary heap O ( ( E + V ) log V)" https://en.wikipedia.org/wiki/Shortest_path_problem (то есть фактически близко к линейному)
Ваш алгоритм не работоспособен для негативных и положительных весов в общем случаи, то есть не является аналогом Bellman–Ford.
Извиняюсь, конечно. Но о какой разницы может идти речь в рамках поставленной задачи? У вас N бросков, k из которых орлы, и очевидно N - k решки.
Соответственно если вы знаете распределение одного, другое получается тривиально. И вычитание константы или из нее, это просто смещение мат. ожидания распределения, получаемое тривиально, без изменения формы распределения.
Речь немного о другом. У нас есть симметричная монетка, которую мы подкидываем N раз, и получаем количество орлов k, за один эксперимент. Если мы проведем серию экспериментов, то получим некоторое распределение, количества выпавших орлов. У этого распределения очевидно будет некоторый центр и разброс вокруг него. Именно этот разброс мы и можем оценить, но для этого надо знать, что это будет за распределение. В наш век можно просто намонтекарлить эти монетки, если не верить во всю эту "науку", либо посчитать аналитически.
Здесь два варианта, как было выше отмечено выше, выпадение k орлов при N бросках, для честной симметричной монетки даст биномиальное распределение. Которое при таком количестве подбрасываний сойдется практически в точности к нормальному со средним N×0.5, и дисперсией N×0.25. Или если перейти к средне квадратичному отклонению/сигме, sqrt(N×0.25). Что даст нам для N=10^10, для среднего 0.5×10^10, и сигму - 50 000. Дальше вспоминаем широко известное правило трех сигм, то есть что 99.73% плотности нормального распределения лежит в диапазоне среднее +/- 3×сигма. Соответственно вероятность выброса за этот диапазон 0.27%. Для 6 сигм вероятность выброса 0.0000002%. В общем, к чему это все, мы вполне можем оценить распределение и его размах, при условии, что нуль гипотеза о честной симметричной монетке верна и имея конкретное значение k , посчитать то самое p-value.
Альтернативный, более простой путь к выводу, это представить эксперимент как сумму случайных бернулевских переменных {0,1} и сразу применить к ним ЦПТ(центральная предельная теорема), что даст ровно такой же результат в виде нормального распределения с параметрами тривиально получаемыми из среднего и дисперсии бернулевского распределения.
И вы мне ещё будете советовать читать основы мат. логики и теории множеств... Вам не показалось, что я их достаточно хорошо знаю, если вижу потенциальную проблему в определении графа?
Там нет проблем, есть ваше не понимание основ предмета, которому уже сотня лет стукнет. Типичный пример Даннинга - Крюгера: мало что понимаю в вопросе, но свое мнение выскажу.
"Алгоритм там не сложный" это вообще о чем? Это NP задача(задача коммивояжера), там единственный не сложный алгоритм - это полный перебор, все остальное там сложное или очень сложное. (может быть за исключением совсем наивных "жадных" алгоритмов)
Про статью "решения задачи коммивояжера" вы явно пошутили, там просто про один из наиболее эффективных подходов к точному решению - монография страниц на 500. И без мат подготовки, вы просто не поймете, что там написано.
Про "аппроксимирующие" алгоритмы и методы локальной оптимизации, применительно к этой задаче, еще можно одну книгу написать.
Даже не знаю что и сказать, почитайте основы мат. логики и теории множеств, там все описано. Функция это подмножество декартового произведения, как вы его выберете? Ну можно предикат определить, или просто перечислить все элементы если множество конечное.
И в случаи графа дуги это именно конечное множество упорядоченных(или нет, если граф не направленный) пар вершин, это множество конечное, и его можно просто перечислить. Все просто.
И автор комментария правильно написал, что представления графов множества, и чаще всего матрица смежности далеко не самое эффективное.
Производственные процессы и технологии тоже меняются, то на что раньше надо было больше материала и работы, теперь надо меньше и при это может быть надежнее.
Хотелось бы конечно увидеть какую-то реальную статистику, а не просто апелляция к расхожему мнения "раньше трава была зеленее" и "все производители закладывают устаревание, лишь бы дотягивало до конца гарантии".
Да, вроде про нее статья. Конечно я не имею не малейшего представления как это работает на самом деле, но массовая слежка через "тайную" подмену сертификата мало реалистична.
Раз уж вы тут за философию пишите, открою секрет - почему. Глупые деньги. Индустрия находится на закате стандартного 30 летнего технологического цикла и максимума хайпа. Люди закапывают деньги в песок, чаще всего не свои.
Нет смысла воевать с ветреными мельницами. Если хотите доводить проекты до конца, найдите место где это ценят(возможно придется постараться).
Компилятор не может порождать эффективный код для SIMD(на x86_64 это SSE/AVX), который выходит за пределы довольно простых паттернов векторизации. Поэтому его пишут на intrinsic которые практически однозначно отображаются в ассемблерные команды (за компилятором остается только распределение регистров) И как-то с "этой бедой" где реально нужна скорость (кодеки/растеризация/криптография/нейросетки на CPU) справляются, а те кто не справляются ищут себе более подходящее занятие.
Опен соурс редко существует в вакууме. Те кто в него комитит и завязал на него свои продукты/разработки, рассчитывали на определенные правила игры, когда на это подписывались. А именно наличие определенной OSS лицензии. Поэтому вполне логично, что если кто-то решил поменять правила игры, будут те кто с ним не согласится и все таки захочет играть по старым правилам и сделает форк. Так что как по мне, так тут все и в рамках права, этики, да и логики нормально.
Помню историю SCO против Linux там вот реально все было за гранью добра и зла.
Если нормально писать код и думать, что он в принципе будет собираться плюсовым компилятором - все будет хорошо. То что есть какое-то количество edge case, которые не будут работать - да это так. И что? Какое это отношение, вообще имеет к практической разработки?
Вопрос ни в том, что произвольно взятый код на C будет компилироваться плюсовым компилятором. А в тех усилиях, которые надо приложить, чтобы он начал компилироваться. И эти усилия на самом деле минимальны, с точки зрения общих затрат на разработку. Думаю в приведенном примере с redis, это все чинится максимум за человеко-неделю разработчика.
Собственно мало, кто знает/помнит, но основной sailing point плюсов в конце 80-х начале 90-х был - "вы можете не выбрасывать свою сишную кодо базу, а начать постепенно переносить ее на плюсы".
Использует это не очень правильный термин. Можно слать промпты в LLM и считать, что занимаешься машинным обучением. Можно ли понимать без этой базы(к слову довольно тривиальной, топология там точно не нужна), что происходит под капотом современных моделей и подходов машинного обучения - крайне сомнительно.
Конечно, можно начинать разбираться в машинном обучении без базы, постепенно изучая, то что не понимаешь. В результате изучив ровно тоже самое, но при этом потратив еще больше времени, чем при систематическом обучении.
Да, ладно как будто студенты эти многообразия до утра, каждый день гладят. Чаще всего это ближе к сессии, приходило. А так ВУЗ это место сосредоточения не самых глупых людей (по крайней мере относительно), наделенных какой-то целью. (хотя бы закончить ВУЗ)
Можно общаться с людьми, из соседнего подъезда, или сразу грузчиком в Пятерочку или "менеджером" пойти, тоже будет много интересного общения. Если ты из условно "средне статистической/простой семьи", то и веток развития будет на самом деле, совсем немного.
Хорошо бы разделить собственно фундаментальные знания, и ВУЗ как средство их получения.
Фундаментальный плюс фундаментальных знаний, что они устоялись и не меняются каждые полгода-год, как новомодный фрэймворк. Если вы выучили алгоритмы и структуры данных, реляционные СУБД, принципы работы операционных систем, основы работы процессора, принципы написания чистого кода, проектирования и ООП. То эти знания останутся с вами навсегда, какой бы новомодный фрэмворк или язык программирования вам не пришлось бы использовать на практике.
Что касается математики, то да, можно согласиться что ее применимость в практическом программировании довольно не велика. Особенно если заниматься в основном перекладыванием джэйсонов. Но стоит шагнуть немного в сторону и оказывается, ни все так просто. То же машинное обучение, выше уровня обезьянки запускающей код с гитхаба, практически невозможно адекватно понять без математической базы: теор. вер, линейной алгебры, дифференциальное исчисление, элементарного понимания, что такое градиент и т.д.
И тут мы подходим к основному пункту. Хорошо когда ты молодой и влет изучаешь очередной фрэймворк. После 35 это становится уже ни так просто. И оказывается, что фундаментальные знания это то на чем можно ехать долгое время, даже если ты в айти уже двадцать лет.
И в качестве завершения. Фундаментальные знания != ВУЗ, их вполне можно получить самому. Достаточно вкалывать часов по 6 в день в течении года, за это время можно освоить практически всю полезную программу. Но только ВУЗ это не только про получение знаний, это молодость, студенчество, знакомства, даже то же самое "научить учится" для тех кто этого не умел. Ни все так просто, как кажется на первый взгляд.
Могу посоветовать LEMON, https://lemon.cs.elte.hu/pub/doc/1.3.1/modules.html . Там много хороших, накочегаренных алгоритмов для графов и оптимизации на них, в том числе комбинаторной.
Такова экономическая реальность за пределами "успшеного успеха ютуба". Рынки эффективны, это означает что если вы зарабатываете значимо больше ключевой ставки(а иначе проще деньги на депозит положить), то у вас неизбежно появятся конкуренты. И если рынок достаточно большой, придут большие профессиональные деньги, и сделают дешевле, и с разумным качеством. Конкурировать частнику с индустриальными способом производства обычно крайне тяжело. (история про ферму против молоко завода)
В конечном итоге, если хотите заняться бизнесом, надо ответить на базовые вопросы. Составить хотя бы отдаленно реалистичный бизнес план. Продумать какие могут быть административные, технологические и другие барьеры для входа конкурентов на рынок. Или возможно рынок достаточно небольшой и нишевой, за счет чего не интересен большим деньгам (привет когтеточки). И даже если решите заняться своим делом, не стоит вкладывать больше чем 1/2-1/3 от накоплений, и тем более лезть в кредиты. Иначе проще в сразу в казино идти, там хотя бы шансы будут больше.
Не надо пожалуйста издеваться над здравым смыслом. Определение графа знаете? Набор вершин и дуг, в котором дуги являются парами связных вершин, плюсом веса для дуг в нашем случаи. Никакого порядка там в принципе не предусмотрено. Не говоря уже о различных представлениях в виде матриц смежности.
3. Замените половину весов на отрицательные и посмотрите, что там посчитается.
У вас в статье собственно три основные проблемы:
"Нужно писать узлы графа в порядке их отдаленности от источника. Т.е.
сперва описываем первых соседей источника. После того, как описали их,
приступаем к следующим соседям соседей."
Таким образом вы решаете не известную задачу, а какую-то другую. Соответственно, чтобы получить честные оценки асимптотики, нужно добавить этот этап препроцессинга
Сложность Дейкстры при нормальной реализации, это "Dijkstra's algorithm with Fibonacci heap O ( E + V log V )", или "Dijkstra's algorithm with binary heap O ( ( E + V ) log V)" https://en.wikipedia.org/wiki/Shortest_path_problem (то есть фактически близко к линейному)
Ваш алгоритм не работоспособен для негативных и положительных весов в общем случаи, то есть не является аналогом Bellman–Ford.
Извиняюсь, конечно. Но о какой разницы может идти речь в рамках поставленной задачи? У вас N бросков, k из которых орлы, и очевидно N - k решки.
Соответственно если вы знаете распределение одного, другое получается тривиально. И вычитание константы или из нее, это просто смещение мат. ожидания распределения, получаемое тривиально, без изменения формы распределения.
Речь немного о другом. У нас есть симметричная монетка, которую мы подкидываем N раз, и получаем количество орлов k, за один эксперимент. Если мы проведем серию экспериментов, то получим некоторое распределение, количества выпавших орлов. У этого распределения очевидно будет некоторый центр и разброс вокруг него. Именно этот разброс мы и можем оценить, но для этого надо знать, что это будет за распределение. В наш век можно просто намонтекарлить эти монетки, если не верить во всю эту "науку", либо посчитать аналитически.
Здесь два варианта, как было выше отмечено выше, выпадение k орлов при N бросках, для честной симметричной монетки даст биномиальное распределение. Которое при таком количестве подбрасываний сойдется практически в точности к нормальному со средним N×0.5, и дисперсией N×0.25. Или если перейти к средне квадратичному отклонению/сигме, sqrt(N×0.25). Что даст нам для N=10^10, для среднего 0.5×10^10, и сигму - 50 000. Дальше вспоминаем широко известное правило трех сигм, то есть что 99.73% плотности нормального распределения лежит в диапазоне среднее +/- 3×сигма. Соответственно вероятность выброса за этот диапазон 0.27%. Для 6 сигм вероятность выброса 0.0000002%. В общем, к чему это все, мы вполне можем оценить распределение и его размах, при условии, что нуль гипотеза о честной симметричной монетке верна и имея конкретное значение k , посчитать то самое p-value.
Альтернативный, более простой путь к выводу, это представить эксперимент как сумму случайных бернулевских переменных {0,1} и сразу применить к ним ЦПТ(центральная предельная теорема), что даст ровно такой же результат в виде нормального распределения с параметрами тривиально получаемыми из среднего и дисперсии бернулевского распределения.
Вообще то они станок сделали, потому что им уже есть много чего производить, а технологии производства перекрыли заклятые друзья.
https://en.wikipedia.org/wiki/Predicate_(mathematical_logic)
Там нет проблем, есть ваше не понимание основ предмета, которому уже сотня лет стукнет. Типичный пример Даннинга - Крюгера: мало что понимаю в вопросе, но свое мнение выскажу.
"Алгоритм там не сложный" это вообще о чем? Это NP задача(задача коммивояжера), там единственный не сложный алгоритм - это полный перебор, все остальное там сложное или очень сложное. (может быть за исключением совсем наивных "жадных" алгоритмов)
Про статью "решения задачи коммивояжера" вы явно пошутили, там просто про один из наиболее эффективных подходов к точному решению - монография страниц на 500. И без мат подготовки, вы просто не поймете, что там написано.
Про "аппроксимирующие" алгоритмы и методы локальной оптимизации, применительно к этой задаче, еще можно одну книгу написать.
Даже не знаю что и сказать, почитайте основы мат. логики и теории множеств, там все описано. Функция это подмножество декартового произведения, как вы его выберете? Ну можно предикат определить, или просто перечислить все элементы если множество конечное.
И в случаи графа дуги это именно конечное множество упорядоченных(или нет, если граф не направленный) пар вершин, это множество конечное, и его можно просто перечислить. Все просто.
И автор комментария правильно написал, что представления графов множества, и чаще всего матрица смежности далеко не самое эффективное.
Производственные процессы и технологии тоже меняются, то на что раньше надо было больше материала и работы, теперь надо меньше и при это может быть надежнее.
Хотелось бы конечно увидеть какую-то реальную статистику, а не просто апелляция к расхожему мнения "раньше трава была зеленее" и "все производители закладывают устаревание, лишь бы дотягивало до конца гарантии".
Да, вроде про нее статья. Конечно я не имею не малейшего представления как это работает на самом деле, но массовая слежка через "тайную" подмену сертификата мало реалистична.