Pull to refresh
43
0
Николай Мальковский @malkovsky

Математик

Send message

"Ваш бигмак на вид просто ужасен! Как я буду выглядеть с ним в инстаграме?! А вот там в Гастролакшариресте такой же бигмак, но с блестящей булочкой и фирменной печатью за х10 стоимости, вот это я понимаю!"

"Я бы не стал покупать у вас бигмак, потому что мне не нравится как он выглядит, но если бы у него блестела булочка, а сверху поставили бы красивую печать, то готов заплатить х4 стоимости да еще и друзей приведу"

Там не перебор, а проход от одной из вершин к корню

Правда, "классические" алгоритмы для решения этой задачи работают лишь с парой узлов (раздватричетыре)

Скорее всего из-за следующего тождества
LCA(a1, a2, ..., an) = LCA(a1, LCA(a2, a3, ..., an))
В отдельных случаях можно сделать сделать LCA для n узлов быстрее, чем n раз сделать LCA двух узлов, но это уже редкость (хотя я на практике сталкивался с такой необходимостью)

а мы, используя всю мощь PostgreSQL,

Вот вам тоже самое только на питоне
from collections import Counter
from typing import List, Tuple

class LCAfinder:
    def __init__(self, arcs: List[Tuple[int, int]]):
        self.parents = dict()
        for arc in arcs:
            self.parents[arc[0]] = arc[1]
        
    def query(self, nodes: List[int]):
        num_nodes = Counter()
        for node in nodes:
            while node is not None:
                num_nodes[node] += 1
                node = self.parents[node]
        node = nodes[0]
        while node is not None:
            if num_nodes[node] == len(nodes):
                return node
            node = self.parents[node]

lca_finder = LCAfinder([(1, None)
  , (2, 1)
  , (3, 1)
  , (4, 2)
  , (5, 2)
  , (6, 5)
  , (7, 5)])

print(lca_finder.query([4, 6, 7]))

Поставлю плюс статье, потому что узнал, что SQL может не только тормознутый JOIN, но и по дереву пройтись. Но вообще на хабре в алгоритмическом треде хотелось бы более серьезного изучения материала перед написанием статьи.

Задача поиска любой порядковой статистики хорошо известна и в оффлайн варианте решается за линейное время. Есть относительно простой известный алгоритм, который по сути заключается в том, что в быстрой сортировке при рекурсивном вызове одна из частей не сортируется, потому что не содержит нужный элемент. Вики утверждает, что есть алгоритм, который гарантирует линейное время.

В С++ к слову нахождение порядковой статистики за линейное время есть в стандарте

Полагаю, что постановка задачи все-таки следующая: требуется реализовать структуру данных, которая поддерживает два запроса

  • Добавить элемент в множество
  • Найти текущую медиану

Тут уже быстрая сортировка не даст нужного эффекта. Стоит отметить, что log(n) для обоих операций можно добиться обычным бинарным деревом поиска без особых ухищрений c кучами. В любом случае говорить о том, что быстрее log(n) не получить довольно наивно, хоть я и не знаю, существует ли кучи, которые умеют одновременно удалять и добавлять за O(1). В целом кажется, что есть возможности исхитриться и делать меньше удалений.
Написал код, который реализует алгоритм Форда-Фалкерсона и генерирует по шагам Ваш пример, можно посмотреть тут
github.com/Malkovsky/interactive-visualization/blob/master/examples/ford-fulkerson.ipynb
Если хочется посмотреть и потыкать, но не хочется мучаться с установкой, можно онлайн в биндере (в репе есть ссылка), но возможно придется подождать сборку докер-образа

У меня что-то такое получилось

Метод, который упомянут в статье — «взять переменную, выразить из одного из уравнений и подставить в другие». Метод Гаусса — приведение к треугольному виду.

UPD. Технически это наверно эквивалентно, но я первый раз вижу, чтобы это подавалось с такой стороны
Важность алгоритма Вемпалы и Пенга совсем не в практической применимости, а в доказательстве того, что сложность решения систем уравнений не ограничена сложностью умножения матриц

С чего такой вывод? В статье улучшение только частного случая (в абстракте более точно указана привязка количества ненулевых элементов к числу обусловленности).
Но ни новый алгоритм, ни другие математические достижения последнего полувека никак не повлияли на практически применимые способы решения систем уравнений: Google и все остальные так и продолжат пользоваться простым, быстрым и неточным итеративным способом.

Мое сугубо субъективное мнение: вы написали статью по теме, в которой не понимаете почти ничего. «Простой, быстрый и неточный итеративный способ» изучен в математике не меньше, чем алгоритмы умножения матриц. Да даже хотя бы в аннотации к статье, которую вы пересказываете, заявлено, что используется блочный метод Крылова, который, не поверите, основывается на итеративном методе. Полагать, что гугл никак не улучшил у себя метод простой итерации было бы довольно наивно.
Все мы учили в школе алгоритм исключения неизвестных по одной
Это между прочим именной метод
У Вас же картинки отсюда взяты, не сравнивались с похожими пакетами?

Я в своё время использовал hyperopt (кажется TPE), из коробки вполне работал, интересно узнать лучше ли у вас получилось.
Вроде бы Вы как раз говорите о том, что зависимость от n есть.
К тому же, в вещественных числах вычисление логарифма не зависит от аргумента

Если Вы говорите об операциях скажем в 64-битном double или любом другом конечном типе хоть с плавающей, хоть с фиксированной точкой, то я согласен — вычисление логарифма не зависит от аргумента. Проблема в том, что в этих вычислениях будет погрешность, которая ограничена снизу в силу конечности представления. И этой точности не будет достаточно для вычисления произвольного числа Фибоначчи, так как последовательность Фибоначчи не ограничена, а следовательно не ограничено и количество значащих цифр в представлении чисел Фибоначчи.
Сотрите, у меня было два основных тезиса
1) Вычисление степени матрицы можно свести к формулам наподобие того, что вы выписали
Диагонализация матрицы из статьи


умножая матрицу в степени на вектор (1, 1) получается последовательность Фибоначчи, умножая на (a, b) получается вариация, о которой Вы писали.
2) Некорректно считать, что такое возведение в степень — это O(1). Чтобы вычислить a^n по формуле exp(log(a) * n) нужно обеспечить достаточную точность при работе с вещественными числами, эта точность зависит от размера результата, точнее сказать не могу — не разбирался.
Выводится через производящие функции, но для подсчета конкретного числа Фибоначчи с её помощью нужно вычислять два возведения в степень
Видимо вы имеете в виду Формулу Бине, которая также опирается на возведение в степень, и если эту операцию мы считаем O(1), то и представленный алгоритм тоже O(1), но вообще это некорректно.
Это хорошие алгоритмы, но это же не динамическое программирование.
Вы сравнивали не для m максимумов, а для 10
Ну вот же у вас в 300 раз различаются замеры
Заголовок спойлера

Интересный момент, вполне возможно, что там имелось в виду (last-first) + (middle-first)log(middle-first), так как видимо предполагается, что элементы от [first, middle) должны быть отсортированы. В соседнем же nth_element уже сложность линейная (с стандартной execution policy).

Про сам алгоритм можно прочитать например здесь
Из статьи Поляк Б. Т. История математического программирования в СССР: анализ феномена

Одноко реальные попытки применить этот метод на практике провалились. Много историй об этом можно найти в… Вот только одна из них: используя работы Канторовича по оптимальному раскрою кусков заданной формы из прямоугольного листа, инженеры и экономисты фабрики, производившей стальные изделия, смогли значительно увеличить выпуск продукции. Однако они столкнулись с неожиданными неприятными последствиями. Во-первых, как результат, план на следующий год увеличился (для системы социалистического планирования было обычно требовать некоторого прироста производства продукции автоматически каждый год), но теперь уже у фабрики больше не было резервов, чтобы выполнить новый увеличенный план. Во-вторых, у каждого предприятия был план сбора металлолома, очевидно, что в результате применения оптимальной стратегии раскроя, количество отходов стали уменьшилось, и этот план выполнить не удалось. Руководство фабрики получило партийный выговор и, как следствие, отказалось от дальнейшего сотрудничества с математиками.
Но тут я использую термин не из матанализа с таким же названием. В моем случае касательная к полигону — это прямая, пересекающая его ровно в одной точке, или проходящая через сторону.

Для этого в матане тоже есть термин)
Опорная гиперплоскость

Information

Rating
Does not participate
Location
Санкт-Петербург, Санкт-Петербург и область, Россия
Date of birth
Registered
Activity