back to basics
Feb. 23rd, 2015 01:24 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonА вот кто не поленился дочитать книжки про построение алгоритмов, вас там научили их строить? Вот есть такая простейшая задачка: дан массив из 8 чисел, нужно найти "почти самое маленькое" и "почти самое большое", т.е.
Надо это сделать за минимальное число действий. Под действиями подразумеваются сравнения, ну и копирования с перестановками, хотя сравнения важнее. На особенности современного железа и его наборов инструкций пока положим, интересует классический теоретический подход. Как положено подходить к решению? Массив можно менять на месте, можно использовать дополнительную память. Я знаю, как это сделать за 14 сравнений. Можно ли за меньшее число? Можно ли доказать, что за меньшее нельзя?
sort(xs); return (xs[1], xs[6]);
Надо это сделать за минимальное число действий. Под действиями подразумеваются сравнения, ну и копирования с перестановками, хотя сравнения важнее. На особенности современного железа и его наборов инструкций пока положим, интересует классический теоретический подход. Как положено подходить к решению? Массив можно менять на месте, можно использовать дополнительную память. Я знаю, как это сделать за 14 сравнений. Можно ли за меньшее число? Можно ли доказать, что за меньшее нельзя?
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2015-02-23 06:30 am (UTC)no subject
Date: 2015-02-23 06:36 am (UTC)или отсортировать? разные вещи
no subject
Date: 2015-02-23 06:40 am (UTC)чётко же всё сформулированно.
no subject
Date: 2015-02-23 06:51 am (UTC)Я бы минимизировалъ съ помощью перебора между различными алгоритмами.
no subject
Date: 2015-02-23 07:06 am (UTC)no subject
Date: 2015-02-23 07:12 am (UTC)Поиск k-й порядковой статистики есть двусторонний сразу? А то если искать сначала в одну сторону, потом в другую, это слишком долго.
no subject
Date: 2015-02-23 07:14 am (UTC)no subject
Date: 2015-02-23 07:24 am (UTC)Почему, "интересует классический теоретический подход"?
задачка может и интересная но непонятно зачем.
no subject
Date: 2015-02-23 07:50 am (UTC)Скажем, можно же по теории информации тут вывести требуемое число бит и стало быть минимальное число сравнений. Для сортировок довольно несложно выводилось (логарифм числа перестановок или около того).
no subject
Date: 2015-02-23 08:23 am (UTC)Пусть мы как-нибудь нашли минимум. В процессе были просмотрены все элементы, по одному разу каждый. То есть мы имеем двоичное дерево поиска минимума. Где может быть второй минимум? Только в той ветке, из которой пришел минимум. Следовательно, ее требуется укоротить. Следовательно строим сбалансированное дерево поиска минимума.
таким образом, на поиск второго минимума будет потрачено (n-1) сравнение при нахождении минимума плюс (log(n)-1) сравнение для поиска второго минимума.
Теперь заметим, что на первом уровне дерева поиска максимума мы можем сравнивать те же пары элементов, что и в дереве поиска минимума. Таким образом, мы сэкономим n/2 сравнений.
Итого, общее время работы (n+log(n)-2)*2-n/2. Подставляя n=8 получим 14.
Про оценку надо думать. Сейчас я умею доказывать, что менее чем 11 сравнениями не обойтись.
а вот ещё задача
Date: 2015-02-23 08:39 am (UTC)no subject
Date: 2015-02-23 09:21 am (UTC)Это коммент о корректности вопроса. Можно было бы понять какую-то формулировку типа "нельзя быстрее, чем (n-1)*(n/4)", но тогда в последнее тоже много чего подходит; например, поиск максимума и минимума одновременно - (n-2); тогда поиск максимума и минимума в оставшемся - ещё (n-4); хотя самих сравнений может быть в 2 раза больше.
no subject
Date: 2015-02-23 09:38 am (UTC)И есть реализация на 11 сравнений?
А то, это как бы известный эффект -- минимальная оценка есть, но как построить алгоритм её реализующий? ;)
no subject
Date: 2015-02-23 10:17 am (UTC)1. Если известно, что исходные массивы уже отсортированы, то можно найти за 0 действий.
2. Если известно, что уже отсортированы в прямом или обратном порядке, то за 1 действие (проверка, в прямом или обратном).
3. Если дано множество из всех возможных восьмерок 32-битный чисел (такое нехилое множество размером 2^32^8) и, запуская разные алгоритмы, надо выбрать из них такой, который в сумме по всем элементам этого множества даст минимальное число действий. (Это будет выбор алгоритма, оптимального "в среднем" по всем наборам входных данных.)
4. Если дано множество всех возможных алгоритмов и для каждого из них выбран наихудший массив, заставляем алгоритм работать - и выбираем из них тот, который будет давать наименьшее число сравнений для своего наихудшего варианта. Но такой способ на практике может быть малопригоден, т.к. вполне может существовать алгоритм, который дает в своем наихудшем случае миллион сравнений, но этот наихудший случай, положим, всего один, а для остальных случаев он в среднем оказывается неплох.
5. Если нет ограничения по памяти, то трактуем 8-элементный массив в качестве 64-битного целого числа (в случае, если у нас элементы массива - байты), предзаполняем в памяти огромный массив ответами по соответствующим огромным индексам и извлекаем ответ по индексу за 0 сравнений. Конечно, на практике это нереальный способ решения, но раз уж запрашивается теоретически оптимальный алгоритм и теоретическое доказательство того, можно меньше или нет, то вот оно, доказательство - можно за 0 действий решить в теории.
12 сравнений
Date: 2015-02-23 10:29 am (UTC)Выбрасываем их и находим максимум и минимум оставшихся - 5 сравнений.
no subject
Date: 2015-02-23 10:35 am (UTC)Re: 12 сравнений
Date: 2015-02-23 11:22 am (UTC)no subject
Date: 2015-02-23 11:25 am (UTC)На самом деле, описанный алгоритм нахождения второго минимума является оптимальным, что доказано, например, здесь (http://web.engr.illinois.edu/~jeffe/teaching/497/02-selection.pdf).
Если мы построим два отдельных дерева для минимума и максимума, то легко построить пример, когда они делают только независимые (то есть с непредсказуемым результатам) сравнения на всех уровнях, начиная со второго. При этом, 14 -- точная оценка.
Однако, потенциально, мы можем сделать смесь двух этих деревьев, и как их оценить в этом случае -- совершенно не понятно.
no subject
Date: 2015-02-23 12:26 pm (UTC)Пусть нам заранее известно, где находятся минимальный и максимальный элемент (это log(n)+log(n-1) бит). Тогда нам осталось найти минимум и максимум среди оставшихся n-2 чисел.
Найти минимум и максимум среди k чисел можно за 3k/2-2 сравнения. При k=n-2 получим 3n/2-5 сравнений.
В сумме получим 3n/2-5+log(n)+log(n-1) сравнений.
Итого имеем зазор в 1 (часто) или 2 (для специально подобранных n) сравнения.
no subject
Date: 2015-02-23 12:53 pm (UTC)Берём какую-нибудь достаточно хорошую сортирующую сеть и отрезаем лишнее.
Дальше получается задача комбинаторной оптимизации, чем-то похожая на построение оптимального умножителя на набор констант (c1, ..., cN) с использованием сложений-вычитаний и двоичного сдвига.
P.S. Не исключено, что можно проще. Это первое, что пришло в голову.
Re: 12 сравнений
Date: 2015-02-23 02:36 pm (UTC)no subject
Date: 2015-02-23 02:40 pm (UTC)no subject
Date: 2015-02-23 02:42 pm (UTC)Почему?
Re: 12 сравнений
Date: 2015-02-23 02:47 pm (UTC)no subject
Date: 2015-02-23 04:06 pm (UTC)И не верю в них.
Насчет же доказательств - это Кнут, второй том.
no subject
Date: 2015-02-23 07:38 pm (UTC)no subject
Date: 2015-02-23 08:37 pm (UTC)no subject
Date: 2015-02-23 11:12 pm (UTC)no subject
Date: 2015-02-24 01:09 am (UTC)no subject
Date: 2015-02-24 03:23 am (UTC)no subject
Date: 2015-02-24 08:02 am (UTC)sort8 (s,t,u,v,w,x,y,z) = (if k < o then min l o else min k p, -- 2 comparisons if n > r then max m r else max n q) where -- 2 comparisons ((a,b),(c,d)) = sort4 (s,t,u,v) -- 2 comparisons ((e,f),(g,h)) = sort4 (w,x,y,z) -- 2 comparisons ((k,l),(m,n)) = if a < c then -- 1 cmp sort3 (a,b) (c,d) -- 1 or 2 cmps else sort3 (c,d) (a,b) -- 1 or 2 cmps ((o,p),(q,r)) = if e < g then -- 1 cmp sort3 (e,f) (g,h) -- 1 or 2 cmps else sort3 (g,h) (e,f) -- 1 or 2 cmps sort3 (a,b) (c,d) = if b < c then ((a,b),(c,d)) else ((a,c), sort2 (b,d)) -- sorts the last 3 numbers -- assuming a < b, a < c, c < d; 1 or 2 cmps sort2 (a,b) = if a < b then (a,b) else (b,a) sort4 (a,b,c,d) = (sort2 (a,b), sort2 (c,d))видимо, есть ветвление, где может быть 2, а может быть 3 сравнения. Тогда есть 4 исхода: 4, 5, 5 и 6 сравнений в совокупности, а в среднем 5. Добавляем к остальным и получаем от 12 до 14, в среднем 13.
no subject
Date: 2015-02-24 04:37 pm (UTC)no subject
Date: 2015-02-24 04:50 pm (UTC)no subject
Date: 2015-02-26 03:59 pm (UTC)if stats: min=12 max=14 avg=13.3333
swap stats: min=0 max=12 avg=6
copy stats: min=0 max=2 avg=1.57143
all stats: min=12 max=28 avg=20.9048
score=842922 ok=true
До этого у меня было:
if stats: min=14 max=14 avg=14
swap stats: min=0 max=10 avg=5.33333
copy stats: min=0 max=2 avg=1.57143
all stats: min=14 max=26 avg=20.9048
score=842912 ok=true
no subject
Date: 2015-02-26 09:52 pm (UTC)sort3 (a,b) (c,d) = if b <= c then ((a,b),(c,d)) else ((a,c), sort2 (b,d))no subject
Date: 2015-02-27 03:13 am (UTC)no subject
Date: 2015-02-27 07:52 am (UTC)