[Все темы по перестановкам]
Теория: Липский. Комбинаторика для программистов. 1988
Особое внимание нужно уделить понятиям инверсии перестановки и знаку перестановки.
sgn(f) = pow(-1,I(f)),
где sgn(f) – знак перестановки, I(f) – количество инверсий
В Липском описан алгоритм, который линейно определяет четность перестановки: четность перестановки равна четности количества четных циклов перестановки.
Мы же сегодня будем заниматься определением количества инверсий в перестановках.
Практика:
В качестве базовой задачи рассмотрим 1090.In the Army Now и решим ее тремя способами.
1 Способ: Сортировка слиянием (merge_sort) O(NlogN)
Суть метода можно легко понять на основе перестановки:
{4, 5, 6, 1, 2, 3}
При сортировке слиянием наступит момент, когда нужно будет сливать в один массив первую половину перестановки со второй. Отсюда видно, что 1 сразу встанет на первое место, миновав элементы 4,5,6 за одну итерацию. Тем самым учтется три инверсии за один шаг. За счет этого мы уходим от квадратичной сложности.
[Решение]
В следующих двух способах придерживаемся общего правила:
Последовательно проходим по каждому элементу перестановки и отвечаем на вопрос: “Сколько элементов было до текущего, которые больше него?”.
2 Способ: Карманная сортировка (bucket_sort) O(N)
Для ответа на вопрос при карманной сортировке нужно определить карман B, в который попадет текущий элемент. Затем найти количество элементов в старших карманах относительно B. Потом аккуратно подсчитать количество элементов, больших текущего в кармане B.
Карман A считается старшим для кармана B, если любой элемент из A больше любого элемента из B.
3 Способ: Дерево Фенвика (Fenwick_tree) O(NlogN)
Сложилось впечатление, что там, где пытаются пристроить карманную сортировку не по назначению, всегда есть место для Дерева Фенвика. И как показывает практика использование дерева Фенвика дает хороший выигрыш по времени, несмотря на свою алгоритмическую сложность.
Вспоминаются слова Михаила Мирзаянова: “Хорошо написанный куб может работать быстрее плохо написанного квадрата”.
По решению: Чтобы найти количество элементов, больше текущего, которые были раньше, необходимо уметь находить быстро сумму элементов в интервале от [cur+1,MAX_VALUE], где cur – текущий элемент, а MAX_VALUE – максимальный элемент в перестановке.
"Липский. Комбинаторика для программистов. 1988
ОтветитьУдалитьОсобое внимание нужно уделить понятиям инверсии перестановки и знаку перестановки.
sgn(f) = pow(-1,I(f)), "
В книге(стр 19):
1: begin
2: s := 1;
3: for i := I to n do HOBbII[i]:=ИCTИHА;
4: for i := I to n do
5: if HOBЫЙ[i] then (*найден цикл, содержащий i*)
6: begin
j := P[i];
7: while j <> i do
8: begin HOBЫЙ[i]:=ложь; s := -s; j := P[j];
end;
end;
end;
Мне кажется что в коде ошибка, HOBЫЙ[i]:=ложь; должно быть HOBЫЙ[j]:=ложь;
Потому что инчае не имеет смысла отмечать HOBЫЙ[i]:=ложь;.
Зачем i-ый элемент отмечать k (длина цикла) раз, ведь он уже точно рассмотрен не будет.
Это код из книги Липского, я думаю он не правильный.
ОтветитьУдалитьДа да, Вы безусловно правы. Там нужно писать в восьмой строке НОВЫЙ[j]:=ложь по причине, которой Вы сами огласили.
ОтветитьУдалитьТолько получается, что цикл будет исполняться на k раз, а k-1, т.к. в шестой строке мы обрабатываем первую вершину цикла, а все последующие k-1 вершины в рамках цикла while.
К сожалению опечатки прокрадываются даже в такие шедевральные издания.
Игорб, скажите, а почему вы решили, что второе решение O(N)? Линейную сложность имеет сама по себе сортировка корзинками, а изменённая под подсчёт количества инверсий - уже нет.
ОтветитьУдалитьВнешний цикл исполняется N раз явно. Про итоговую линейную сложность можно говорить, если тело цикла исполняется за O(1), а это не так. Там есть два отдельных цикла, один из которых O(количество корзинок), а второй O(размер корзинки). Если мы фиксируем количество корзинок (принимаем за константу), то размер корзинки пропорционален N, и, таким образом, цикл поиска точки вставки имеет линейную сложность. Если заменить его бинарным поиском, будет log(N), и O(N*log(N)) итого, но по связному списку бинарный поиск не сделаешь, а массив даст N на вставке. Итого - квадрат без вариантов.
Если же мы фиксируем размер корзинки, то количество корзинок пропорционально N, и цикл подсчёта суммы длин корзинок (в версии из видео) или цикл инкремента кэша инверсий (в версии с everfall) даёт O(N), что в итого даст квадрат. В версии из видео можно сумму считать на дереве Фенвика, тогда получится O(log(N)) тело цикла и O(N*log(N)) итого. Но не более.
А так в обоих версиях второго решения у вас квадрат. Проверьте на 100 000 элементов, или на миллионе - будет заметно.
1. По поводу подсчета количества инверсий с помощью карманной сортировки.
УдалитьВы не спорите, что карманная сортировка работает за O(N). Давайте вспомним, что там происходит:
a) Все элементы раскидываются по карманам.
b) Каждый карман сортируется сортировкой вставками.
Фиксируем количество карманов(константа С). Размер кармана пропорционален N, то тогда получается по Вашим доводам сортировка кармана работает за O(N*N), т.к. п.b) будет работать именно с такой сложностью. Итого общее время работы С*O(N*N). В Кормене(второе издание с.230-234) описываются мат. выкладки, доказывающие линейность карманной сортировки.
Что касается инверсий, то по сути дела в приведенной реализации происходит карманная сортировка в online режиме и вся мат.часть из Кормена подходит и под этот случай.
2. Не совсем понял конец фразы "В версии из видео можно сумму считать на дереве Фенвика, тогда получится O(log(N)) тело цикла и O(N*log(N)) итого. Но не более."
3. Пробовать на 100.000 элементов я не стал.
Изначально задача формулировалась для 10.000 элементов, собственно поэтому и родилась идея попробовать все три метода. 100.000 элементов лучше решать Фенвиком.
P.S: Напомню, что по условию задачи мы имеем дело с перестановкой, поэтому при использовании карманной сортировки все карманы забиваются равномерно. Идеально подходит случай, когда количество карманов равно количеству элементов внутри кармана. Т.е. случай когда количество карманов = sqrt(N). Для случая в 10.000 элементов размер кармана в 100 раз меньше размера всей коллекции, поэтому можно условно считать, что сортировка кармана выполняется за большую константу.
Хмм... Интересно.
УдалитьПрочитал выкладки из Кормена, которые, впрочем, полностью повторяют русскую Википедию, проникся.
Собственно, вопрос у меня возник потому, что в моей реализации (Ruby) на 100 000 чисел сортировка слиянием считает количество инверсий за 0,75с. Фенвик за 0,5с. А корзинки, если их 1000 и в каждой 100 элементов - за 7 секунд. Если их 100 и в каждой 1000 - за 3 секунды. Посмотрел, кто тормозит в каждом конкретном случае, так во втором конкретно тормозил поиск точки вставки - если его заменить на рандом, алгоритм отрабатывал за полсекунды. То есть, тормозила не вставка, а именно поиск. А поскольку я использовал обычный рубишный массив, то я имею возможность сделать по нему бинарный поиск, что тоже резко ускоряет алгоритм.
И вот с этого места мне стало казаться, что это не N.
Что вы думаете по этому поводу? Я уже понял (хотя и не понял, почему, так что, скорее поверил), что лучший случай, когда размер корзинки равен количеству корзинок. А для 100 000 лучше 100 корзинок по 1000, 1000 корзинок по 100 или 316 корзинок по примерно 317?
Карманная сортировка имеет скорее академический интерес. Работает с очень большой константой и при условии равномерного распределения значений внутри сортируемого массива.
УдалитьЧто касается выбора размера кармана(он же корзинка).
Тут следующие соображения:
Рассмотрим предложенный Вами случаи для 100.000 элементов:
1) Количество карманов = 100; Размер кармана = 1000
В этом случае не надо сортировать карман квадратичной сортировкой. Лучше подойдет какая нибудь из "быстрых".
2) Количество карманов = 1000; Размер кармана = 100
Учитывая, что размер кармана не велик, то возможно лучше подойдет эффективная реализация квадратичной сортировки. Известно, что маленькие массивы лучше сортировать квадратичной сортировкой. Но как узнать границу, после которой массив перестает быть маленьким? По моим наблюдениям в общем случае эта верхняя граница находится между 32 и 40. У Тима Петерсона в Tim Sort'e это 64(правда это на Python'e). 100 - не такое большое число и возможно нет принципиальной разницы чем и как сортировать.
3) Количество карманов = 317; Размер кармана = 316.
Вот тут самое интересное.
Пусть N - общее количество сортируемых элементов, M - количество карманов, С - количество элементов внутри кармана.
В данном коде: http://www.everfall.com/paste/id.php?oipol8yb4phq можно проследить, что общее время работы равно
O(N*(C+M)). Нужно минимизировать С+M, при этом M = N/C, т.е нужно минимизировать C+N/C.
Короче говоря все свелось к классической школьной задаче: Нужно найти отношение сторон прямоугольника с фиксированной площадью, так чтобы его периметр был минимальным. Данное условие достигается, когда стороны относятся как 1:1. Так и в нашем случае С должно быть равно M.
Собственно, именно академический интерес меня и ведёт, потому как деревья Фенвика - очевидно и самый красивый, и самый эффективный способ решения этой задачи.
УдалитьБольшое спасибо за выкладки. Многое у меня в голове прояснилось.
А кое-что запуталось, уже с точки зрения математики. O(N*(C+M)) = O(N*(C+N/C)) = O(N*C+N*N/C) = O(N*N). Так? В каком месте надо применить хак с матоожиданием, чтобы в этой выкладке не перейти к O(N*N)?
УдалитьАга. Что-то начало проясняться. При C =~ M это не квадрат, а O(2N*sqrt(N)). Но выхода на N всё равно не вижу.
УдалитьИ, кстати, при 316-317 работает всё те же 3 секунды.
Удалить1. Выход на O(N) читайте в Кормене
Удалить2. Опять повторюсь, не нужно ждать чудес от карманой сортировки. Случай 316-317 и вправду работает долговато.