смутно помню, что в каких-то деревьях номер элемента описывал положение элемента в дереве и там битовыми операциями включая разворот можно было быстро находить наименьшего общего предка элементов
Скорее всего речь идет о представлении дерева виде правильной скобочной последовательности -- одна из основ succint структур данных. Детально не подскажу, но там точно битовых трюков используется. Конкретно реверс битов я нашел немного в другой штуке -- wavelet tree
Бенчмарки сделаны с помощью google benchmark, в статье приведен его консольный вывод, вот он же на гитхабе
Бенчмарки где написано All 32-bit uint -- это прогон метода для всех 2^32 значений uint32_t. Одна итерация означает, что бенчмарк запускался один раз, 45.5 секунд -- время его выполнения. Есть несколько бенчмарков где прогоняется только 32 значения -- числа с одним единичным битом, они очень маленькие и google benchmark сам решает прогонять его несколько раз, число итераций он выбирает сам в этом случае.
Должны быть, но едва ли там требуется написать что-то из того, что я в статье описал. Сам я первый раз познакомился с подобными штуками на олимпиадном программировании, но как ни странно эти методы там не особо применимы.
Есть такой типичный сценарий когда нужен LSB: есть стандартное решение задачи о коммивояжёре динамическим программированием на подмножествах. Суть в том, чтобы посчитать функцию "Какая длина минимального пути, проходящего по множеству вершин S и заканчивающегося в T?". Чтобы её вычислить нужно перебрать предпоследнюю вершины из S и взят минимум по путям S\{T}. Перебирать можно все биты и там все просто, а можно методом, который я писал в статье x = x & (x - 1), это в среднем уменьшает в 2 раза количество итераций. Проблема остается в том, что мы выделяем число, у которого ровно один бит, но не знаем какой, а он нужен для вычислений, вот здесь и нужен LSB. Проблема в целом в том, что с использованием LSB в таком сценарии итоговый выигрышь по производительности не очень велик (максимум в 2 раза) -- это значительно для продакшена, но в рамках олимпиадной задачи обычно незначительно.
А зачем он тогда такой нужен, если наивный алгоритм O(n)?
Я имел в виду ровно то, что в обычной ситуации такой алгоритм был бы неэффективен, но в случае когда доступны эффективные векторные инструкции он оказывается лучше.
Не вижу где автор говорит такие вещи как "все вокруг неправильно делают, а надо делать так как он предложил"
В сообщении, на которое я отвечал, буквально написано
У меня не получается объяснить, что операторы в Я не надо гуглить - их надо читать
Я признаю, что мог неаккуратно подобрать, но хоть убейте я не понимаю где Вы в моём сообщении нашли шапкозакидательство с моей стороны. Могу отдельно обратить внимание на то, что вот это
P. S. Почему бы Вам не попробовать это дело в азиатской среде продвинуть?
Не подъеб и не предложение свалить в туман. Это интуитивное предположение, что азиатам, привыкшем к логографическому письму и которым в частности не привыкать делать клавиатуры с иероглифами "Я" может подойти гороздо лучше, чем в рускоязычном или англоязычном сегменте.
Что вы сделали для того чтобы следующий экспериментатор захотел с вами поделиться на хабре своим безумным проектом? Закидали камнями всех предыдущих?
Пишу технические статьи осознавая, что я пишу их не для себя или своих коллег, продираюсь через адские проблемы c версткой формул с хабровским wysiwyg, получается не всегда.
Что блять за комунити такое где все всё знают про все языки и паттерны, а элементарных вещей по комунити билдинг не понимают.
Вы говорите о том, что плохо закидывать камнями авторов, а через пару предложений закидываете камнями комментатора.
Вы можете упрямиться и продолжать настаивать на том, что все вокруг неправильно делают, а надо делать так как вы предложили. Или можете попытаться понять почему другие люди пишут, что у них полная фрустрация от происходящего. Я подписываюсь под каждым пунктом в первом комментарии этого треда. Могу добавить, что мне пришлось лезть в интернет за тем, чтобы найти значение слова "логографический" при том, что я знаю разницу между графемами, морфемами и сенонами. За себя скажу, что если Вы пойдёте по первому пути, то я буду считать, что вы просто сделали язык под себя, и перестану им интересоваться совсем.
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" используется исключительно в образовательных целях
Погодите, а как такое произошло? Код прогоняется вот таким циклом
https://github.com/Malkovsky/bit_tricks/blob/main/src/benchmarks.cpp#L19C1-L23C8
метод benchmark::DoNotOptimize не запрещает внутренние оптимизации, но как будто в метод не константы передаются. Непонятно
Скорее всего речь идет о представлении дерева виде правильной скобочной последовательности -- одна из основ succint структур данных. Детально не подскажу, но там точно битовых трюков используется. Конкретно реверс битов я нашел немного в другой штуке -- wavelet tree
https://github.com/simongog/sdsl-lite/blob/master/include/sdsl/wt_pc.hpp#L844
Обновил.
Минус я случайно поставил пока тыкал тачпад. Не знаю как убрать
Бенчмарки сделаны с помощью google benchmark, в статье приведен его консольный вывод, вот он же на гитхабе
Бенчмарки где написано All 32-bit uint -- это прогон метода для всех 2^32 значений uint32_t. Одна итерация означает, что бенчмарк запускался один раз, 45.5 секунд -- время его выполнения. Есть несколько бенчмарков где прогоняется только 32 значения -- числа с одним единичным битом, они очень маленькие и google benchmark сам решает прогонять его несколько раз, число итераций он выбирает сам в этом случае.
Вот код бенчмарка
О, спасибо! Добротная книга, в такой статье грех не сослаться на неё, добавил в описание. Единственное, метода Де Брюина я там не увидел.
Вроде как все описанные методы описаны в TAOCP vol. 4a Кнута, но при всём моем к нему уважении там это написано максимально непонятно
Должны быть, но едва ли там требуется написать что-то из того, что я в статье описал. Сам я первый раз познакомился с подобными штуками на олимпиадном программировании, но как ни странно эти методы там не особо применимы.
Есть такой типичный сценарий когда нужен LSB: есть стандартное решение задачи о коммивояжёре динамическим программированием на подмножествах. Суть в том, чтобы посчитать функцию "Какая длина минимального пути, проходящего по множеству вершин S и заканчивающегося в T?". Чтобы её вычислить нужно перебрать предпоследнюю вершины из S и взят минимум по путям S\{T}. Перебирать можно все биты и там все просто, а можно методом, который я писал в статье x = x & (x - 1), это в среднем уменьшает в 2 раза количество итераций. Проблема остается в том, что мы выделяем число, у которого ровно один бит, но не знаем какой, а он нужен для вычислений, вот здесь и нужен LSB. Проблема в целом в том, что с использованием LSB в таком сценарии итоговый выигрышь по производительности не очень велик (максимум в 2 раза) -- это значительно для продакшена, но в рамках олимпиадной задачи обычно незначительно.
Я имел в виду ровно то, что в обычной ситуации такой алгоритм был бы неэффективен, но в случае когда доступны эффективные векторные инструкции он оказывается лучше.
@Exosphere пожалуйста, дайте работягам markdown вместо wysiwyg
В сообщении, на которое я отвечал, буквально написано
Я признаю, что мог неаккуратно подобрать, но хоть убейте я не понимаю где Вы в моём сообщении нашли шапкозакидательство с моей стороны. Могу отдельно обратить внимание на то, что вот это
Не подъеб и не предложение свалить в туман. Это интуитивное предположение, что азиатам, привыкшем к логографическому письму и которым в частности не привыкать делать клавиатуры с иероглифами "Я" может подойти гороздо лучше, чем в рускоязычном или англоязычном сегменте.
Пишу технические статьи осознавая, что я пишу их не для себя или своих коллег, продираюсь через адские проблемы c версткой формул с хабровским wysiwyg, получается не всегда.
Вы говорите о том, что плохо закидывать камнями авторов, а через пару предложений закидываете камнями комментатора.
Вы можете упрямиться и продолжать настаивать на том, что все вокруг неправильно делают, а надо делать так как вы предложили. Или можете попытаться понять почему другие люди пишут, что у них полная фрустрация от происходящего. Я подписываюсь под каждым пунктом в первом комментарии этого треда. Могу добавить, что мне пришлось лезть в интернет за тем, чтобы найти значение слова "логографический" при том, что я знаю разницу между графемами, морфемами и сенонами. За себя скажу, что если Вы пойдёте по первому пути, то я буду считать, что вы просто сделали язык под себя, и перестану им интересоваться совсем.
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" используется исключительно в образовательных целях