Вы можете упрямиться и продолжать настаивать на том, что все вокруг неправильно делают, а надо делать так как вы предложили. Или можете попытаться понять почему другие люди пишут, что у них полная фрустрация от происходящего. Я подписываюсь под каждым пунктом в первом комментарии этого треда. Могу добавить, что мне пришлось лезть в интернет за тем, чтобы найти значение слова "логографический" при том, что я знаю разницу между графемами, морфемами и сенонами. За себя скажу, что если Вы пойдёте по первому пути, то я буду считать, что вы просто сделали язык под себя, и перестану им интересоваться совсем.
P. S. Почему бы Вам не попробовать это дело в азиатской среде продвинуть?
Вы точно понимаете о чем пишете? В C# любое изменение размера массива приводит к выделению памяти для нового, копированию данных из старого и удаления старого (не сразу конечно, а как там сборщик мусора решит).
Именно по этому почти во всех популярных языках есть динамический массив, реализующий одну и ту же идею: есть две величины capacity и length. Последняя -- это реальное количество элементов, первая -- это текущий размер массива, где элементы хранятся. Выделение памяти происходит только если мы пытаемся добавить элмент при length=capacity, в этом случае capacity увеличивается в два раза. Соответственно с таким подходом количество аллокаций при добавлении N элементов -- это log(N), количетсов перемещений <= 2N. Конкретно в List<T> эта логика реализована вот тут, аллокации вот тут.
Как уже было сказано, в C++ это std::vector, в Java ArrayList, в Python это стандартный список. Идея является стандартом индустрии и поэтому почти ни у кого не возникает опасений о том, что добавление в массив -- это постоянные переалокации.
Очень интересная оригинальная статья. Жаль, что ни этот перевод, ни её оригинал не отражают её сущности. Попробую взять на себя роль пояснительной бригады.
Есть алгоритм Дейкстры. Он ищет кратчайшие пути от одной вершины до всех остальных в графе с неотрицательными рёбрами. В процессе работы он переберает каждую вершину и каждое ребро ровно один раз. Теоретически он мог бы работать за O(n+m) -- лучшую асимптотическую оценку не получить ибо это размер входных данных, тем не менее ни одна реализация алгоритмы Дейкстры её не достигает.
Попутно с нахождением кратчайших путей алгоритм Дейкстры также косвенно упорядочивает все вершины по отдалению от исходной вершины. Если предположить, что веса рёбер можно только складывать и сравнивать, то нижняя оценка Дейкстры ухудшается до O(nlogn+m), так как задача упорядочивания вершин в топологии "звезда" эквивалентна сортировке, которую при использовании только сравнений нельзя решить быстрее nlogn. Оценка O(nlogn+m) для Дейкстры достигается при использовании кучи Фибоначчи в качестве очереди с приоритетом.
Оценка O(nlogn) неулучшаема для звезды, но очевидным образом, если граф -- один единственный путь, то там легко получить упорядочивание за линейный проход. Вот здесь кроется тонкость в понимании оптимальности оригинальной статьи (universal optimality). Если обозначить за OPT(G) минимальное число сравнений задачи упорядочивания вершин по отдалению от заданной для фиксированной топологии G (минимум берётся по всем возможным весам ребер в этой топологии), то Дейкстра со специальной кучей работает за время O(OPT(G)+n+m), т.е. например для линейного графа он сделает линейное число O(n) сравнений, а не O(nlogn).
Специальная куча -- это "Fibonacci-like priority queue with the working set property". Её отличие от обычной кучи Фибоначчи в том, что удаление минимума делается не за logn, где n -- количество элементов в куче на момент удаления, а log W(x), где x -- удаляемый минимум, а W(x) -- количество элементов, которые попали в очередь после х и еще находятся в ней на момент удаления. Построение такой кучи -- значительная часть статьи и скорее всего она относится к галактическим алгоритмам
Основной теоретический вклад Нэша как раз в том, что он развил более ранюю теорию Неймана-Моргенштерна игр 2х игроков с нулевой суммой на случай игр с ненулевой суммой и произвольным числом игроков. О каком большинстве вы говорите?
Если ресурс делим на произвольные доли, то это задача линейного программирования и, соответственно, решается симплекс методом. Если же ресурс делится только на какие-то куски, то это задача целочисленного линейного программирования, где хорошего универсального решателя нет, по крайней мере сиплекс-метод таким не является.
Эквивалентом описанной в статье задачи с произвольным делением было бы что-то такое: "Есть несколько порошков с разной удельной стоимостью, нужно отмерить ровно M минимальным возможным объемом". Такая задача решается симплекс-методом, но при этом решается и простым жадным алгоритмом "берем порошок с наибольшей удельной стоимостью пока не закончился, если еще не отмерили -- переходим к следующему порошку"
Это как? Если Вы взялись сравнивать два O(nlogn), то уж точно не с такой аргументацией. Быстрая сортировка в среднем делает nln(n) сравнений (обычно в анализе приводят 2n(ln), как например тут, но там алгоритм разделения предполагает n сравнений на n элементов в то время как обычно используется алгоритм с n/2 сравнений. С пирамидальной сортировкой сложнее, потому что худший случай -- это когда во всех операциях новый/удаляемый элемент проходит полностью путь от корня до листа и наоборот, но даже тут есть нюанс, заключающийся в том, что размер кучи равномерно изменяется от 1 к n и обратно, что ведет к n(log_2(n)-2), в среднем случае как будто получается nlog_2(n) (не проверял) и разница соответственно уже на в два раза, а ln(2). Короче я это к тому, что стоит вкидывать не совсем верные утверждения без должного подкрепления где это можно детально посмотреть.
Промышленные методы сортировки - это сплав быстрой, вставок и пирамиды
Ну что за недосказанность! Это описание сортировки introsort, используемой например в качестве std::sort в gcc c неочевидной реализацией перехода на вставки для массивов длины 16. Стоит отметить, что все три используемых вспомогательных сортировок (быстрая, пирамидальная, вставками) -- inplace для массивов.
Так вроде бы KMP != построение префикс-функции для "pattern$text". KMP -- это префикс-функция для pattern и проход без доп. памяти по text, так что два последовательных цикла как раз каноничны, а конструкция "pattern$text" используется исключительно в образовательных целях
Если зафиксировать X0, то n-ый член последовательности
можно выразить как полином степени 2^n-1 по D, причем из свойств метода Ньютона получаем, что на отрезке [1.0, 2.0] его максимальное отклонение от 1/x очень маленькое. Можем ли мы найти какой-то другой полином, который можно было бы быстрее посчитать, и его отклонение было бы не хуже? Вот со вторым свойством как раз всплывают многочлены Чебышева, и основанный на нем метод Ремеза (про них не так давно была на хабре статья про вычисление синуса) -- такие методы позволяют найти многочлен фиксированной степени с наименьшим отклонением от целевой функции на отрезке. Как этот многочлен потом эффективно вычислять -- отдельный вопрос, вроде как в статье об этом отдельный параграф.
@botyaslonim это уже за гранью постиронии использовать на КДПВ генерала Лебедя при том, что он выступал не за "жесткое управление", да и хорошо его ощутил на себе
Тут нужно сделать важную оговорку, что все указанные оценки справедливы только если вы, например, делаете вычисления по модулю. Проблема в том, что длина Fn растет линейно от n из-за чего итеративный алгоритм работает на самом деле за O(n^2), а быстрый за O(nlogn) (из мастер-теоремы). Ну и соответственно если вы работаете по модулю часла длины k, то получаются оценки O(nk)/O(klogn).
Есть еще формула Бине
которая сводит вычисления чисел Фибоначчи к возведению в степень, которое можно делать за log, но из-за работы с float она не такая полезная даже для спортивного интереса, в отличии от
Также работает дейкстра с потенциалами: если в каждой вершине записать какое-то число и считать длину пути как длина всех ребер + потенциал конца - потенциал начала. На этом основан алгоритм Джонсона, который работает в графах с отрицательными ребрами, но без отрицательных циклов. Так же A* является дейкстрой со сложной функцией расстояния.
Да, про это упомянуто в статье.
Этот алгоритм работает с любой функцией расстояния, если только она удовлетворяет некоторым свойствам:
Вообще изначально я хотел добавить в статью SSSP на полукольцах, Алгоритм Витерби, beam search, альфа-бета отсечение как смежные задачи, но когда в выходной день в 5 утра дебажил ALT понял, что надо завязывать. В заглавной картинке например остался Мерияр Мори -- он обобщил scanning method и Дейкстру для весов из полукольца (кольцо без обратного по сложению). Например обычная SSSP -- это SSSP в тропическом полукольце (вдоль пути разные веса складываем, к путям разным путям с одинаковыми концами применяем минимум), для вероятностного кольца (вдоль пути умножаем, веса разных путей с одинаковыми концами складываем) SSSP -- это поиск стационарного распределения в марковской цепи, ваш пример -- мин-макс полукольцо.
И поэтому же не работает Дейкстра с орицательными ребрами, ведь нарушается третье условие.
Тут кстати стоит отметить, что реализация Дейкстры через scanning method -- это довольно простая модификация, которая делает его применимым к отрицательным рёбрам, правда уже без какой-либо оценки по сложности.
Если для вас действительно имеет значение использование рекурсии, то видимо вы работаете c системами реального времени или чем-то аналогичным по уровню требований. В такой ситуации для фундаментальных алгоритмов я бы просто не рекомендовал использовать python ибо он предназначен не для оптимизации рантайма, а для оптимизации времени разработки. Если бы я писал примеры к OSM на С++, это бы заняло примерно бесконечное время (если не привлекать питон хотя бы для обвязки), но при этом если бы стояла задача ускорить алгоритмы, то первым бы делом я их переписал на С++.
Касательно исходного вопроса: чаще всего обход в глубину можно заменить обходом в ширину, но при необходимости можно и переписать как здесь
Питон хороший язык, но не высокопроизводительный. А от библиотеки, которая заявляет, что у них
an interface to existing numerical algorithms and code written in C, C++, and FORTRAN;
я бы ожидал высокой производительности, а получаю, что все методы начиная с двунаправленного Дейкстры, которые я написал для демонстрации работают быстрее библиотечных.
А как же неравенство треугольника?
Не совсем понял вопроса. Кратчайшие расстояния от одной вершины до всех остальных удовлетворяют неравенству треугольника
Вы можете упрямиться и продолжать настаивать на том, что все вокруг неправильно делают, а надо делать так как вы предложили. Или можете попытаться понять почему другие люди пишут, что у них полная фрустрация от происходящего. Я подписываюсь под каждым пунктом в первом комментарии этого треда. Могу добавить, что мне пришлось лезть в интернет за тем, чтобы найти значение слова "логографический" при том, что я знаю разницу между графемами, морфемами и сенонами. За себя скажу, что если Вы пойдёте по первому пути, то я буду считать, что вы просто сделали язык под себя, и перестану им интересоваться совсем.
P. S. Почему бы Вам не попробовать это дело в азиатской среде продвинуть?
Именно по этому почти во всех популярных языках есть динамический массив, реализующий одну и ту же идею: есть две величины
capacityиlength. Последняя -- это реальное количество элементов, первая -- это текущий размер массива, где элементы хранятся. Выделение памяти происходит только если мы пытаемся добавить элмент приlength=capacity, в этом случаеcapacityувеличивается в два раза. Соответственно с таким подходом количество аллокаций при добавлении N элементов -- это log(N), количетсов перемещений <= 2N. Конкретно в List<T> эта логика реализована вот тут, аллокации вот тут.Как уже было сказано, в C++ это std::vector, в Java ArrayList, в Python это стандартный список. Идея является стандартом индустрии и поэтому почти ни у кого не возникает опасений о том, что добавление в массив -- это постоянные переалокации.
Очень интересная оригинальная статья. Жаль, что ни этот перевод, ни её оригинал не отражают её сущности. Попробую взять на себя роль пояснительной бригады.
Есть алгоритм Дейкстры. Он ищет кратчайшие пути от одной вершины до всех остальных в графе с неотрицательными рёбрами. В процессе работы он переберает каждую вершину и каждое ребро ровно один раз. Теоретически он мог бы работать за O(n+m) -- лучшую асимптотическую оценку не получить ибо это размер входных данных, тем не менее ни одна реализация алгоритмы Дейкстры её не достигает.
Попутно с нахождением кратчайших путей алгоритм Дейкстры также косвенно упорядочивает все вершины по отдалению от исходной вершины. Если предположить, что веса рёбер можно только складывать и сравнивать, то нижняя оценка Дейкстры ухудшается до O(nlogn+m), так как задача упорядочивания вершин в топологии "звезда" эквивалентна сортировке, которую при использовании только сравнений нельзя решить быстрее nlogn. Оценка O(nlogn+m) для Дейкстры достигается при использовании кучи Фибоначчи в качестве очереди с приоритетом.
Оценка O(nlogn) неулучшаема для звезды, но очевидным образом, если граф -- один единственный путь, то там легко получить упорядочивание за линейный проход. Вот здесь кроется тонкость в понимании оптимальности оригинальной статьи (universal optimality). Если обозначить за OPT(G) минимальное число сравнений задачи упорядочивания вершин по отдалению от заданной для фиксированной топологии G (минимум берётся по всем возможным весам ребер в этой топологии), то Дейкстра со специальной кучей работает за время O(OPT(G)+n+m), т.е. например для линейного графа он сделает линейное число O(n) сравнений, а не O(nlogn).
Специальная куча -- это "Fibonacci-like priority queue with the working set property". Её отличие от обычной кучи Фибоначчи в том, что удаление минимума делается не за logn, где n -- количество элементов в куче на момент удаления, а log W(x), где x -- удаляемый минимум, а W(x) -- количество элементов, которые попали в очередь после х и еще находятся в ней на момент удаления. Построение такой кучи -- значительная часть статьи и скорее всего она относится к галактическим алгоритмам
Основной теоретический вклад Нэша как раз в том, что он развил более ранюю теорию Неймана-Моргенштерна игр 2х игроков с нулевой суммой на случай игр с ненулевой суммой и произвольным числом игроков. О каком большинстве вы говорите?
Если ресурс делим на произвольные доли, то это задача линейного программирования и, соответственно, решается симплекс методом. Если же ресурс делится только на какие-то куски, то это задача целочисленного линейного программирования, где хорошего универсального решателя нет, по крайней мере сиплекс-метод таким не является.
Эквивалентом описанной в статье задачи с произвольным делением было бы что-то такое: "Есть несколько порошков с разной удельной стоимостью, нужно отмерить ровно M минимальным возможным объемом". Такая задача решается симплекс-методом, но при этом решается и простым жадным алгоритмом "берем порошок с наибольшей удельной стоимостью пока не закончился, если еще не отмерили -- переходим к следующему порошку"
А познакомите с Мирей Матьё? 🙏
Это как? Если Вы взялись сравнивать два O(nlogn), то уж точно не с такой аргументацией. Быстрая сортировка в среднем делает nln(n) сравнений (обычно в анализе приводят 2n(ln), как например тут, но там алгоритм разделения предполагает n сравнений на n элементов в то время как обычно используется алгоритм с n/2 сравнений. С пирамидальной сортировкой сложнее, потому что худший случай -- это когда во всех операциях новый/удаляемый элемент проходит полностью путь от корня до листа и наоборот, но даже тут есть нюанс, заключающийся в том, что размер кучи равномерно изменяется от 1 к n и обратно, что ведет к n(log_2(n)-2), в среднем случае как будто получается nlog_2(n) (не проверял) и разница соответственно уже на в два раза, а ln(2). Короче я это к тому, что стоит вкидывать не совсем верные утверждения без должного подкрепления где это можно детально посмотреть.
Ну что за недосказанность! Это описание сортировки introsort, используемой например в качестве std::sort в gcc c неочевидной реализацией перехода на вставки для массивов длины 16. Стоит отметить, что все три используемых вспомогательных сортировок (быстрая, пирамидальная, вставками) -- inplace для массивов.
Если вы считаете, что 1 час преподавания = 1 час нагрузки, то вот краткий список вещей, которые Вы видимо не делаете/не учитываете
Подготовка и проверка домашних/контрольных работ/упражнений на практику
Подготовка к лекции накануне
Периодическое обновление материала
В местах где я работал обычно предполагалось, что 1 час преподавания = 2 часа нагрузки
Ага, а еще вот это
Так вроде бы KMP != построение префикс-функции для "pattern$text". KMP -- это префикс-функция для pattern и проход без доп. памяти по text, так что два последовательных цикла как раз каноничны, а конструкция "pattern$text" используется исключительно в образовательных целях
Если зафиксировать X0, то n-ый член последовательности
можно выразить как полином степени 2^n-1 по D, причем из свойств метода Ньютона получаем, что на отрезке [1.0, 2.0] его максимальное отклонение от 1/x очень маленькое. Можем ли мы найти какой-то другой полином, который можно было бы быстрее посчитать, и его отклонение было бы не хуже? Вот со вторым свойством как раз всплывают многочлены Чебышева, и основанный на нем метод Ремеза (про них не так давно была на хабре статья про вычисление синуса) -- такие методы позволяют найти многочлен фиксированной степени с наименьшим отклонением от целевой функции на отрезке. Как этот многочлен потом эффективно вычислять -- отдельный вопрос, вроде как в статье об этом отдельный параграф.
Главное помнить, что быстрый обратный корень выдает аппроксимацию, а не точное значение.
@botyaslonim это уже за гранью постиронии использовать на КДПВ генерала Лебедя при том, что он выступал не за "жесткое управление", да и хорошо его ощутил на себе
Range aggregation queries (SELECT average(weight) WHERE age BETWEEN 30 AND 40)
https://petsymposium.org/popets/2022/popets-2022-0128.pdf
Top-k completion (вы что-то написали в текстовом поле, а вам дают 10 продолжений)
https://dl.acm.org/doi/pdf/10.1145/2488388.2488440
Least common ancestor problem и её применения (анализ иерархии классов, зависимостей модулей)
Сбор статистики на в потоке данных
https://www.sciencedirect.com/science/article/pii/S0169023X10000753
Succint словари
https://en.wikipedia.org/wiki/Succinct_data_structure#Succinct_indexable_dictionaries
Тут нужно сделать важную оговорку, что все указанные оценки справедливы только если вы, например, делаете вычисления по модулю. Проблема в том, что длина Fn растет линейно от n из-за чего итеративный алгоритм работает на самом деле за O(n^2), а быстрый за O(nlogn) (из мастер-теоремы). Ну и соответственно если вы работаете по модулю часла длины k, то получаются оценки O(nk)/O(klogn).
Есть еще формула Бине
которая сводит вычисления чисел Фибоначчи к возведению в степень, которое можно делать за log, но из-за работы с float она не такая полезная даже для спортивного интереса, в отличии от
Да, про это упомянуто в статье.
Вообще изначально я хотел добавить в статью SSSP на полукольцах, Алгоритм Витерби, beam search, альфа-бета отсечение как смежные задачи, но когда в выходной день в 5 утра дебажил ALT понял, что надо завязывать. В заглавной картинке например остался Мерияр Мори -- он обобщил scanning method и Дейкстру для весов из полукольца (кольцо без обратного по сложению). Например обычная SSSP -- это SSSP в тропическом полукольце (вдоль пути разные веса складываем, к путям разным путям с одинаковыми концами применяем минимум), для вероятностного кольца (вдоль пути умножаем, веса разных путей с одинаковыми концами складываем) SSSP -- это поиск стационарного распределения в марковской цепи, ваш пример -- мин-макс полукольцо.
Тут кстати стоит отметить, что реализация Дейкстры через scanning method -- это довольно простая модификация, которая делает его применимым к отрицательным рёбрам, правда уже без какой-либо оценки по сложности.
Если для вас действительно имеет значение использование рекурсии, то видимо вы работаете c системами реального времени или чем-то аналогичным по уровню требований. В такой ситуации для фундаментальных алгоритмов я бы просто не рекомендовал использовать python ибо он предназначен не для оптимизации рантайма, а для оптимизации времени разработки. Если бы я писал примеры к OSM на С++, это бы заняло примерно бесконечное время (если не привлекать питон хотя бы для обвязки), но при этом если бы стояла задача ускорить алгоритмы, то первым бы делом я их переписал на С++.
Касательно исходного вопроса: чаще всего обход в глубину можно заменить обходом в ширину, но при необходимости можно и переписать как здесь
к сожалению нет, быть может есть какая-нибудь точка входа? В чем задача заключается?
Питон хороший язык, но не высокопроизводительный. А от библиотеки, которая заявляет, что у них
an interface to existing numerical algorithms and code written in C, C++, and FORTRAN;
я бы ожидал высокой производительности, а получаю, что все методы начиная с двунаправленного Дейкстры, которые я написал для демонстрации работают быстрее библиотечных.
Не совсем понял вопроса. Кратчайшие расстояния от одной вершины до всех остальных удовлетворяют неравенству треугольника
Вот еще, если не считать того, что библиотека на питоне, то в общем то вполне добротная подборка потоковых алгоритмов. Правда там только классические.
https://github.com/networkx/networkx/tree/main/networkx/algorithms/flow