"Ваш бигмак на вид просто ужасен! Как я буду выглядеть с ним в инстаграме?! А вот там в Гастролакшариресте такой же бигмак, но с блестящей булочкой и фирменной печатью за х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 и все остальные так и продолжат пользоваться простым, быстрым и неточным итеративным способом.
Мое сугубо субъективное мнение: вы написали статью по теме, в которой не понимаете почти ничего. «Простой, быстрый и неточный итеративный способ» изучен в математике не меньше, чем алгоритмы умножения матриц. Да даже хотя бы в аннотации к статье, которую вы пересказываете, заявлено, что используется блочный метод Крылова, который, не поверите, основывается на итеративном методе. Полагать, что гугл никак не улучшил у себя метод простой итерации было бы довольно наивно.
Все мы учили в школе алгоритм исключения неизвестных по одной
К тому же, в вещественных числах вычисление логарифма не зависит от аргумента
Если Вы говорите об операциях скажем в 64-битном double или любом другом конечном типе хоть с плавающей, хоть с фиксированной точкой, то я согласен — вычисление логарифма не зависит от аргумента. Проблема в том, что в этих вычислениях будет погрешность, которая ограничена снизу в силу конечности представления. И этой точности не будет достаточно для вычисления произвольного числа Фибоначчи, так как последовательность Фибоначчи не ограничена, а следовательно не ограничено и количество значащих цифр в представлении чисел Фибоначчи.
Сотрите, у меня было два основных тезиса
1) Вычисление степени матрицы можно свести к формулам наподобие того, что вы выписали
Диагонализация матрицы из статьи
умножая матрицу в степени на вектор (1, 1) получается последовательность Фибоначчи, умножая на (a, b) получается вариация, о которой Вы писали.
2) Некорректно считать, что такое возведение в степень — это O(1). Чтобы вычислить a^n по формуле exp(log(a) * n) нужно обеспечить достаточную точность при работе с вещественными числами, эта точность зависит от размера результата, точнее сказать не могу — не разбирался.
Видимо вы имеете в виду Формулу Бине, которая также опирается на возведение в степень, и если эту операцию мы считаем O(1), то и представленный алгоритм тоже O(1), но вообще это некорректно.
Интересный момент, вполне возможно, что там имелось в виду (last-first) + (middle-first)log(middle-first), так как видимо предполагается, что элементы от [first, middle) должны быть отсортированы. В соседнем же nth_element уже сложность линейная (с стандартной execution policy).
Одноко реальные попытки применить этот метод на практике провалились. Много историй об этом можно найти в… Вот только одна из них: используя работы Канторовича по оптимальному раскрою кусков заданной формы из прямоугольного листа, инженеры и экономисты фабрики, производившей стальные изделия, смогли значительно увеличить выпуск продукции. Однако они столкнулись с неожиданными неприятными последствиями. Во-первых, как результат, план на следующий год увеличился (для системы социалистического планирования было обычно требовать некоторого прироста производства продукции автоматически каждый год), но теперь уже у фабрики больше не было резервов, чтобы выполнить новый увеличенный план. Во-вторых, у каждого предприятия был план сбора металлолома, очевидно, что в результате применения оптимальной стратегии раскроя, количество отходов стали уменьшилось, и этот план выполнить не удалось. Руководство фабрики получило партийный выговор и, как следствие, отказалось от дальнейшего сотрудничества с математиками.
Но тут я использую термин не из матанализа с таким же названием. В моем случае касательная к полигону — это прямая, пересекающая его ровно в одной точке, или проходящая через сторону.
"Ваш бигмак на вид просто ужасен! Как я буду выглядеть с ним в инстаграме?! А вот там в Гастролакшариресте такой же бигмак, но с блестящей булочкой и фирменной печатью за х10 стоимости, вот это я понимаю!"
"Я бы не стал покупать у вас бигмак, потому что мне не нравится как он выглядит, но если бы у него блестела булочка, а сверху поставили бы красивую печать, то готов заплатить х4 стоимости да еще и друзей приведу"
Там не перебор, а проход от одной из вершин к корню
Скорее всего из-за следующего тождества
LCA(a1, a2, ..., an) = LCA(a1, LCA(a2, a3, ..., an))
В отдельных случаях можно сделать сделать LCA для n узлов быстрее, чем n раз сделать LCA двух узлов, но это уже редкость (хотя я на практике сталкивался с такой необходимостью)
Вот вам тоже самое только на питоне
Поставлю плюс статье, потому что узнал, что SQL может не только тормознутый JOIN, но и по дереву пройтись. Но вообще на хабре в алгоритмическом треде хотелось бы более серьезного изучения материала перед написанием статьи.
В С++ к слову нахождение порядковой статистики за линейное время есть в стандарте
Полагаю, что постановка задачи все-таки следующая: требуется реализовать структуру данных, которая поддерживает два запроса
Тут уже быстрая сортировка не даст нужного эффекта. Стоит отметить, что log(n) для обоих операций можно добиться обычным бинарным деревом поиска без особых ухищрений c кучами. В любом случае говорить о том, что быстрее log(n) не получить довольно наивно, хоть я и не знаю, существует ли кучи, которые умеют одновременно удалять и добавлять за O(1). В целом кажется, что есть возможности исхитриться и делать меньше удалений.
github.com/Malkovsky/interactive-visualization/blob/master/examples/ford-fulkerson.ipynb
Если хочется посмотреть и потыкать, но не хочется мучаться с установкой, можно онлайн в биндере (в репе есть ссылка), но возможно придется подождать сборку докер-образа
UPD. Технически это наверно эквивалентно, но я первый раз вижу, чтобы это подавалось с такой стороны
С чего такой вывод? В статье улучшение только частного случая (в абстракте более точно указана привязка количества ненулевых элементов к числу обусловленности).
Мое сугубо субъективное мнение: вы написали статью по теме, в которой не понимаете почти ничего. «Простой, быстрый и неточный итеративный способ» изучен в математике не меньше, чем алгоритмы умножения матриц. Да даже хотя бы в аннотации к статье, которую вы пересказываете, заявлено, что используется блочный метод Крылова, который, не поверите, основывается на итеративном методе. Полагать, что гугл никак не улучшил у себя метод простой итерации было бы довольно наивно.
Это между прочим именной метод
Я в своё время использовал hyperopt (кажется TPE), из коробки вполне работал, интересно узнать лучше ли у вас получилось.
Если Вы говорите об операциях скажем в 64-битном double или любом другом конечном типе хоть с плавающей, хоть с фиксированной точкой, то я согласен — вычисление логарифма не зависит от аргумента. Проблема в том, что в этих вычислениях будет погрешность, которая ограничена снизу в силу конечности представления. И этой точности не будет достаточно для вычисления произвольного числа Фибоначчи, так как последовательность Фибоначчи не ограничена, а следовательно не ограничено и количество значащих цифр в представлении чисел Фибоначчи.
1) Вычисление степени матрицы можно свести к формулам наподобие того, что вы выписали
умножая матрицу в степени на вектор (1, 1) получается последовательность Фибоначчи, умножая на (a, b) получается вариация, о которой Вы писали.
2) Некорректно считать, что такое возведение в степень — это O(1). Чтобы вычислить a^n по формуле exp(log(a) * n) нужно обеспечить достаточную точность при работе с вещественными числами, эта точность зависит от размера результата, точнее сказать не могу — не разбирался.
Про сам алгоритм можно прочитать например здесь
Одноко реальные попытки применить этот метод на практике провалились. Много историй об этом можно найти в… Вот только одна из них: используя работы Канторовича по оптимальному раскрою кусков заданной формы из прямоугольного листа, инженеры и экономисты фабрики, производившей стальные изделия, смогли значительно увеличить выпуск продукции. Однако они столкнулись с неожиданными неприятными последствиями. Во-первых, как результат, план на следующий год увеличился (для системы социалистического планирования было обычно требовать некоторого прироста производства продукции автоматически каждый год), но теперь уже у фабрики больше не было резервов, чтобы выполнить новый увеличенный план. Во-вторых, у каждого предприятия был план сбора металлолома, очевидно, что в результате применения оптимальной стратегии раскроя, количество отходов стали уменьшилось, и этот план выполнить не удалось. Руководство фабрики получило партийный выговор и, как следствие, отказалось от дальнейшего сотрудничества с математиками.
Для этого в матане тоже есть термин)
Опорная гиперплоскость