Уффф... Спросите у чатгпт, я на память не воспроизведу. Вкратце – заменяем элемент (для удаления – на последний из кучи) и восстанавливаем порядок в куче операциями siftUp/siftDown, там не надо всю кучу перелопачивать.
Не понял. Короче, у вас решение за O(1) работает или за O(log N)? Для O(1) есть хитрость, просто хранить две кучи и обновлять их на каждом шаге – получите O(log N).
Да, это оно. Конечно, для leetcode задачка так себе, т.к. она больше на знание алгоритма (не думаю, что многие смогут придумать его сами). Интересно, уложится ли в тайминги литкода решение с логарифмической сложностью.
Не хэш-таблицы, гистограммы. Просто считать частичную сумму, пока не доберётесь до половины длины окна. Ну, естественно, можно оптимизировать, храня и обновляя некоторые из частичных сумм.
Имеет смысл только для очень больших размеров окна, и то не факт.
Из него не обязательно извлекать корень. Например, держите в узле количество его подэлементов. Тогда можете сразу определить, искомый элемент в корне, левом или правом поддереве, и рекурсивно повторить.
Зачем? Контейнер для хранения чисел внутри окна – чёрный ящик. Мы в него на каждом шаге кладём одно число, убираем одно число и извлекаем медиану.
Референсная реализация – отсортировать массив и взять из средней позиции. Легко доказать, что результат будет тот же.
Эксперимент был бы интересен для приближения гистограммы моментами и тому подобных приближённых методов (позволяющих считать за O(1) независимо от размера окна)
Как человек, 10 лет занимавшийся разработкой софта для анализа изображений, могу ответить: да, сложно.
Конечно, скользящее среднее – это база, если в вашей задаче можно им воспользоваться – ура, мы сэкономили кучу ресурсов. Но оно (как и дешёвые решения на его основе) подходит не всегда. Могут понадобиться оба фильтра – и медиана, и скользящее среднее (возможно, повторённое 2-3 раза, чтобы приблизить к гауссовскому фильтру).
Ещё, кстати, в копилку дешёвых методов – open и close фильтры. Вначале выполняем бегущий минимум (эрозия), потом бегущий максимум (дилатация). Ну или наоборот. Убирает светлые или тёмные пятна соответственно. Для изображений есть усовершенствование – open/close with reconstruction. Но тоже особо не используется отдельно.
Кстати, бегущий максимум/минимум, не зависящий от размера окна – сам по себе интересный алгоритм. Изобрели, если я правильно помню, только в 80-х. Попробуйте до него додуматься сами, не подглядывая – это правда интересно (делается без сложных структур данных).
Скользящее среднее – совсем другой фильтр. Лучше убирает гауссовский шум, хуже удаляет выбросы. Разница очень заметна при обработке изображений: медиана убирает одиночные точки/пятнышки на изображении, оставляя границы резкими, бегущее среднее – размывает границы, а точки полностью не удаляет.
Это не в том смысле, что медианный фильтр лучше – он просто решает другие задачи.
Именно что оставить возможность для оптимизации. Там порой не в наносекунды упирается, а выкидываются огромные куски ненужного кода. Причём код библиотек на C++ (где куча метапрограммирования на темплейтах) порой на эти оптимизации закладывается (простите, что перескочил от C к C++).
Не хотите этого безумия – меняйте язык. В более поздних языках гораздо, гораздо меньше UB. Типа пусть прога будет чуть медленнее, но программист не сойдёт с ума. Плюс многие моменты обошли за счёт более совершенной системы типов – и таки могут применять оптимизации.
Ну и даже в чистом C, насколько я помню, UB меньше, чем в C++ (но всё равно хватает).
Уффф... Спросите у чатгпт, я на память не воспроизведу. Вкратце – заменяем элемент (для удаления – на последний из кучи) и восстанавливаем порядок в куче операциями siftUp/siftDown, там не надо всю кучу перелопачивать.
Не понял. Короче, у вас решение за O(1) работает или за O(log N)? Для O(1) есть хитрость, просто хранить две кучи и обновлять их на каждом шаге – получите O(log N).
Удаление или замена элемента в куче – O(log N), можно не хранить удалённые элементы.
Ну так-то да. Реализация с деревом – просто база, от которой начинаешь думать, уже зная, что уложишься в O(log N).
Да, это оно. Конечно, для leetcode задачка так себе, т.к. она больше на знание алгоритма (не думаю, что многие смогут придумать его сами). Интересно, уложится ли в тайминги литкода решение с логарифмической сложностью.
Не хэш-таблицы, гистограммы. Просто считать частичную сумму, пока не доберётесь до половины длины окна. Ну, естественно, можно оптимизировать, храня и обновляя некоторые из частичных сумм.
Имеет смысл только для очень больших размеров окна, и то не факт.
Из него не обязательно извлекать корень. Например, держите в узле количество его подэлементов. Тогда можете сразу определить, искомый элемент в корне, левом или правом поддереве, и рекурсивно повторить.
Зачем? Контейнер для хранения чисел внутри окна – чёрный ящик. Мы в него на каждом шаге кладём одно число, убираем одно число и извлекаем медиану.
Референсная реализация – отсортировать массив и взять из средней позиции. Легко доказать, что результат будет тот же.
Эксперимент был бы интересен для приближения гистограммы моментами и тому подобных приближённых методов (позволяющих считать за O(1) независимо от размера окна)
Или вы имели в виду эксперимент по скорости?
Как человек, 10 лет занимавшийся разработкой софта для анализа изображений, могу ответить: да, сложно.
Конечно, скользящее среднее – это база, если в вашей задаче можно им воспользоваться – ура, мы сэкономили кучу ресурсов. Но оно (как и дешёвые решения на его основе) подходит не всегда. Могут понадобиться оба фильтра – и медиана, и скользящее среднее (возможно, повторённое 2-3 раза, чтобы приблизить к гауссовскому фильтру).
Ещё, кстати, в копилку дешёвых методов – open и close фильтры. Вначале выполняем бегущий минимум (эрозия), потом бегущий максимум (дилатация). Ну или наоборот. Убирает светлые или тёмные пятна соответственно. Для изображений есть усовершенствование – open/close with reconstruction. Но тоже особо не используется отдельно.
Кстати, бегущий максимум/минимум, не зависящий от размера окна – сам по себе интересный алгоритм. Изобрели, если я правильно помню, только в 80-х. Попробуйте до него додуматься сами, не подглядывая – это правда интересно (делается без сложных структур данных).
С чего бы? Сбалансированное дерево позволяет получить элемент с заданным номером за O(log N).
С погрешностью – это если на гистограммах делать или приближать гистограмму моментами.
Скользящее среднее – совсем другой фильтр. Лучше убирает гауссовский шум, хуже удаляет выбросы. Разница очень заметна при обработке изображений: медиана убирает одиночные точки/пятнышки на изображении, оставляя границы резкими, бегущее среднее – размывает границы, а точки полностью не удаляет.
Это не в том смысле, что медианный фильтр лучше – он просто решает другие задачи.
В сбалансированное дерево тогда уж, чтоб вставка/удаление дорогими не были.
Ну, у камуса вообще задача специфическая – обеспечить скольжение в одну сторон.
Я думал, это из анекдота про многодетного отца :-)
Кажется, вы не прочитали пост. У Apple всё ещё остаётся тумблер, позволяющий сделать установку приложения из сторонних сторов невозможной.
Клеим на локтевой сгиб.
Так-то понятно, что обычно не подвергается: пользы с этого никакой, а повредить можно. Но раз уж резинку сделали – можно об этом подумать.
Хм... Резинка могла бы и энергию деформации в электричество преобразовывать.
Много лет прошло, уже давно не "переносимый ассемблер". Вот и...
Именно что оставить возможность для оптимизации. Там порой не в наносекунды упирается, а выкидываются огромные куски ненужного кода. Причём код библиотек на C++ (где куча метапрограммирования на темплейтах) порой на эти оптимизации закладывается (простите, что перескочил от C к C++).
Не хотите этого безумия – меняйте язык. В более поздних языках гораздо, гораздо меньше UB. Типа пусть прога будет чуть медленнее, но программист не сойдёт с ума. Плюс многие моменты обошли за счёт более совершенной системы типов – и таки могут применять оптимизации.
Ну и даже в чистом C, насколько я помню, UB меньше, чем в C++ (но всё равно хватает).
А на крестиках и на це ваш выбор – писать без UB.
1 парируется магазином: сдал и ждёшь возврата денег в течение месяца или сколько там допустимо по закону.