Кросс-пост из Study: Сортировка массива с множетсвенным сравнением

0000

Есть массив a1, ..., aN
Есть оператор сравнения принимающий на вход фиксированное количество элементов (напр. 10) и выдающий сортированную подпоследовательность.
Кто нить знает видел алгоритм с сортировками такого типа сравнения? Или хотя бы как они называются правильно?
Уточнения:
0. расход памяти не важен. Сравнение считается долгим и потому надо минимизировать количество вызовов.
1. Одинаковых элементов в входном массивет нет
2. Оператор сравнения возвращает тот же входной набор, но упорядоченный. Напр cmp(1, 6, 5, 2) вернет (1, 2, 5, 6). Длина оператора фиксированна (некоторое K << N). Сравнения просто двух элементов нет. Использование k-множественного чревато большими расходами на вызов функций сравнения.
3. В реальной задаче k ~ 25, N = 30 000.

pitrik2

сортировки с разбиением?
ну как бы кусорт тоже также сортирует, токо там функция 2 значения принимает
ну а вообще мердж сорт похож на енто
там типа разбиение на 2 куска, сортировка их по отдельности а потом мерджинг
upd:
http://en.wikipedia.org/wiki/Merge_sort
там даж упоминается tiled merge sort algorithm который как раз списки длиной S (твои 10) сортирует внешней функцией, а дальше мерджит как обычно

0000

Понятно, что в случае если функция принимает на вход два элемента, то это классическая сортировка.
Вдруг кто то видел-слышал-знает алгоритм/реализацию этой ботвы. Задачка то вполне академическая.

Serab

Чув, у тебя в Hobbies gamedev и ты не можешь рализовать такой алгоритм, прочитав предыдущий ответ? Несладко тебе придется.

Dasar

там даж упоминается tiled merge sort algorithm который как раз списки длиной S (твои 10) сортирует внешней функцией, а дальше мерджит как обычно

т.е. дальше вызываем эту функцию для 10 элементов, но передаем всего два?
а если там не 10, а 1000?

0000

Несладко тебе придется.

Конфет уже купил
Если никто не слышал, про уже имеющийся, то придется реализовывать.

Serab

Ну че за бред? Все же ясно описано. Что значит "придется реализовывать"? А раньше ты как обходился? Только копипастой действуешь что ли?

Serab

Ты чего-то недопонял, либо никогда не писал merge sort.
upd: это я чего-то недопонял, а точнее не заметил, что в условии именно фиксированное число элементов, т.е. не просто как бонус к обычному сравнению, а именно вместо обычного сравнения. Ясно, надо думать.

0000

А раньше ты как обходился? Только копипастой действуешь что ли?

Если есть возможность, то да.
P.S. Merge sort, как и другие сортировки никогда не писал. Может быть в школе, но это было 10+ лет назад.

vall

мердж сорт тут будет не очень эффективен.

Serab

Ну так это что с ходу в голову пришло. Согласен, чувствуется расточительность при слиянии.
Что лучше?

pitrik2

т.е. дальше вызываем эту функцию для 10 элементов, но передаем всего два?

кажется я понял что ты хошь сказать
ты хошь сказать что если нет попарного сравнения то мы не сможем сделать мердж?
однако...

Serab

да, вот до меня не сразу дошло. Можем, конечно, но не слишком эффективно.

vall

для k-арного сортировщика можно делать k/m потоковое слияние которое будет выдавать от m до k/m элементов за такт.
или sqrt(k) потоковое, которое будет стабильно выдавать sqrt(k) =)

Serab

8-o
можно подробнее?

pitrik2

Можем, конечно, но не слишком эффективно.

можем это как?
типа сравнивать 9 уже сравненых и десятый
если десятый в конце оказался значит он больше всех
если в начале то меньше
если в середине, то нада другие брать 9
ужас нах

Serab

нет, просто если надо сравнить два числа, то забиваем весь массив из них (просто любое ненулевое количество одного и другого какое на первом месте - то и меньше.
Но ясно, что это все жестоко, надо думать, ща пойду посоветуюсь с гуру.

klyv

можем это как?
типа сравнивать 9 уже сравненых и десятый
если десятый в конце оказался значит он больше всех
если в начале то меньше
если в середине, то нада другие брать 9
ужас нах

Есть оператор сравнения принимающий на вход фиксированное количество элементов (напр. 10) <font size=""> [/size] и выдающий сортированную подпоследовательность.

Мне кажется, что cmp(3,2,5,4,6) выдаст типа (3,5,6) или (3,4,6 т.е. тот самый "десятый" может просто не появиться

pitrik2

Мне кажется, что cmp(3,2,5,4,6) выдаст типа (3,5,6) или (3,4,6 т.е. тот самый "десятый" может просто не появиться

это жесть какая-то

klyv

это жесть какая-то

ну а как ещё понимать слово "подпоследовательность"?

kokoc88

ну а как ещё понимать слово "подпоследовательность"?

(=

pitrik2

ненаю
но ведь же жесть
а что если эта фигня число 6 вообще всегда выкидывает?
т.е. какие бы остальные 9 не дали в резалте 6 не будет
и как тогда сортировать?

klyv

но ведь же жесть

ага.
а на простые вопросы ответы сами находятся.

а что если эта фигня число 6 вообще всегда выкидывает?
т.е. какие бы остальные 9 не дали в резалте 6 не будет
и как тогда сортировать?

Зет из зе квешн.

Andbar

это жесть какая-то

К тому-же, результат, вроде, неоднозначен в данной формулировке.

Dasar

k-арного сортировщика

это что такое?

Dasar

Мне кажется, что

если учесть, что постановщик задачи далек от строгих формальных рассуждений, то это скорее неправильное использование термина "подпоследовательность" вместо "последовательность", чем что-то более хитрое.

Dasar

k-арный сортировщик сольёт две упорядоченные поседовательности по n в каждой худшем за 2*n/k применений.

каким образом?
допустим n=k=10000
каким образом за два вызова - две упорядоченные последовательности сольются?

Serab

А по вашему "1 2 3" — это подпоследовательность "3 2 1"?

Dasar

Есть оператор сравнения принимающий на вход фиксированное количество элементов (напр. 10)

при условии, что само такое сравнение очень дорогое, а сравнение ключей/индексов много дешевле, то такой сортировщик можно представить как сортировщик - который умеет за раз сравнивать k/2 - пар
тогда можно использовать параллельное слияние - делаем k/2 - "потоков", в каждом из которых сливаем по две полоски
в конце - сортировщик будет использоваться неэффективно, когда полосок останется меньше, чем k
при k << n - будет довольно эффективно (т.к. есть что распараллеливать а вот при k сравнимом с n - фигня получается, т.к. сортировщик будет использоваться сразу неэффективным образом.

Dasar

А по вашему "1 2 3" — это подпоследовательность "3 2 1"?

чего?
ps
"1 2 3" - это упорядоченная по возрастанию последовательность "3 2 1"
pps
еще раз прочитай что я написал в предыдущем посте

Serab

Да, но 3 2 1 - это НЕ подпоследовательность 1 2 3, т.е. ты написал правильно, но недостаточно уверенно. Раньше упоминался только вопрос повторения элементов. В общем, никаких подпоследовательностей.

Dasar

Да, но 3 2 1 - это НЕ подпоследовательность 1 2 3, т.е. ты написал правильно, но недостаточно уверенно. Раньше упоминался только вопрос повторения элементов. В общем, никаких подпоследовательностей.

прочитай еще раз
и расскажи своими словами что там написано

Serab

при k << n - будет довольно эффективно (т.к. есть что распараллеливать)

Ну какое еще распараллеливание? Это каждому ребенку известно, что merge sort параллелится на ура.
Это задача чисто алгоритмическая (или как выразился топикстартер, академическая и не надо тут заводить разговор о распараллеливании, потоках, кэше, это все очень хорошо, но абсолютно не в кассу.
Тут главный фокус в том, чтобы использовать эту операцию, сортирующую 10 элементов как можно менее дубово (читай менее часто).
Сам решения пока не знаю.

agaaaa

Кто нить знает видел алгоритм с сортировками такого типа сравнения?

let sorted lst =

  if lst.Length >= n then

    let start = List.take n lst

    if start = nsort start then

      sorted List.skip (max (n - 1) (lst.Length - n

    else

      false

  else

    fail_with "list size must be greater or equal to n"



let rec sort lst =

  if not (sorted lst) then

    let lst = randomize lst

    sort lst

  else lst

где randomize переставляет элементы в случайном порядке
работает за время порядка O(n!)

Serab

работает за время порядка O(n!)

БОООООООжеж ты мой!

Dasar

Это задача чисто алгоритмическая (или как выразился топикстартер, академическая и не надо тут заводить разговор о распараллеливании, потоках, кэше, это все очень хорошо, но абсолютно не в кассу.

тебя заносит, ты читаешь не то, что написано.
слово распараллелить в данном случае означало лишь, что мы одновременно(специально для тебя: в одном потоке) можем сливать не пару ленточек, а сразу - k/2 пар

vall

каким образом?допустим n=k=10000каким образом за два вызова - две упорядоченные последовательности сольются?

a[1..k/2] b[1..k/2] -> на вход и выход 1..min(idx(a[k/2] idx(b[k/2] можно уже забирать
в худшем случае это будет k/2
так что да, на двойку я ошибся в тривиальной оценке (4* там) , ИМХО и оценку 2* тоже можно попробовать доказать.

Serab

Да, причудилось что-то.
Все равно пока что решение далеко до идеала.

Dasar

работает за время порядка O(n!)

пузырек при всей своей неэффективности, и то быстрее будет
(n+1-k)*(n-k)/2

Dasar

так что да, на двойку я ошибся в тривиальной оценке (4* там) , ИМХО и оценку 2* тоже можно попробовать доказать.

допустим n=k=10000
каким образом за четыре вызова - две упорядоченные последовательности сольются?

agaaaa

Это было решение-шутка.
Вропчем, я не думаю, что кто-то здесь предложит реализацию значительно лучше qsort'а за O(n*log n/(k-1

vall

операцию я написал — каждый раз одна из последовательностей будет укорачиваться на k/2
или исчезнет полностью и тогда сравнивать больше нечего.

Dasar

операцию я написал — каждый раз одна из последовательностей будет укорачиваться на k/2
или исчезнет полностью и тогда сравнивать больше нечего.

покажи, пожалуйста, пальцем - на простом пример k=n=10000
там не все так просто.
например, непонятно как ты в алгоритм будешь вот это запихивать "каждый раз одна из последовательностей будет укорачиваться на k/2".

Dasar

кто-то здесь предложит реализацию значительно лучше qsort'а за O(n*log n/(k-1

ты знаешь хотя бы такой алгоритм для больших k?

Dasar

операцию я написал — каждый раз одна из последовательностей будет укорачиваться на k/2
или исчезнет полностью и тогда сравнивать больше нечего.

ты понимаешь тот факт, что это будет срабатывать только пока у тебя k << n, а на сравнимых k и n - этого не будет, а придется делать все равно n-k вызовов?

Devid

Таких N, что N >> k неверно, пренебрежимо мало на числовой прямой. Хотя на практике это и может сказаться.

vall

обе последовательности суммарно уменьшатся тоже как минимум на k/2 так что всё нормально.

Dasar

обе последовательности суммарно уменьшатся тоже как минимум на k/2 так что всё нормально.

т.е. ты не можешь привести те 4 действия, которые будет делать твой алгоритм для k=n=10000, но при этом утверждаешь, что такие 4 действия есть?

Dasar

Таких N, что N >> k неверно, пренебрежимо мало на числовой прямой. Хотя на практике это и может сказаться.

мы говорим о мат. абстракциях, или о реальных задачах?

0000

Как обычно точно сформулировать задачу у меня не получилось
Уточнения:
1. Одинаковых элементов в входном массивет нет
2. Оператор сравнения возвращает тот же входной набор, но упорядоченный. Напр cmp(1, 6, 5, 2) вернет (1, 2, 5, 6). Длина оператора фиксированна (некоторое K << N). Сравнения просто двух элементов нет. Использование k-множественного чревато большими расходами на вызов функций сравнения.
3. В реальной задаче k ~ 25, N = 30 000.

Andbar

3. В реальной задаче k ~ 25, N = 30 000.

N делится на k? По большому счёту, это не важно, но мало ли...

Dasar

3. В реальной задаче k ~ 25, N = 30 000.

из того, что было предложено - мне пока реальным видется только параллельный merge,
 на твоих числах сложность будет хуже, чем n*logn/(k/2 но лучше чем n*logn, причем ближе к первой оценке, чем ко второй.
точно считать лень.

Devid

те 4 действия, которые будет делать твой алгоритм для k=n=10000

Можно даже за 3.
Сначала сравниваем 5000 наибольших из первой и 5000 из второй, в результате имеем минимум 5000 самых наибольших.
На втором шаге повторяем первый (после первого в каждой посл. останется минимум 5000 чисел так что все нормально) и имеем еще 5000 наибольших.
Третьим шагом упорядычиваем остальные 10000.

Dasar

Можно даже за 3.
Сначала сравниваем 5000 наибольших из первой и 5000 из второй, в результате имеем минимум 5000 самых наибольших.
На втором шаге повторяем первый (после первого в каждой посл. останется минимум 5000 чисел так что все нормально) и имеем еще 5000 наибольших.
Третьим шагом упорядычиваем остальные 10000.

так вы с -ом в курсе, что это так называемая идеальная сортировка, которую еще практически никто не написал? вернее она написана, но только для n<=7 (или что-то такое)
как вы после первого шага будете понимать - сколько у вас из 5000 наибольших взято из первой цепочки, а сколько из второй?
тоже самое более формально:
на входе два сортированных массива: a1, a2
на первом шаге вы делаете
a = sort (a1[1..5000] + a2[1..5000])
result[1..5000] = a[1..5000] получаете 5000 наибольших элементов, а дальше как?
sort(a1[i1..i1+5000]+a2[i2..i2+5000])?
 каким образом здесь определяются i1 и i2? или вы как-то хитрее поступаете?

Devid

Это частности. Можно, например, хранить в элементе его номер в последовательности, которой он сейчас принадлежит, а оператору сравнения передавать указатели.
Тогда после первого шага смотрим на число номер 5001 (самое большое из тех, которым не посчастливилось попасть в 5000 наибольших) и понимаем где надо обрубать последовательность, которой оно принадлежит. Потом смотрим на 5002 и т.д., пока не найдем число из второй последовательности, в среднем это не займет много времени.

Dasar

Это частности.

в частностях часто и прячется дьявол, который убивает все решению на корню.
но здесь -да, все тривиально, даже проще, чем ты предлагаешь

vall

неважно как мы это реализуем, главное что это реализуется в сумме за o(n если каждый элемент помнит свой номер или сортировщик выдаёт нам перестановку а не сами элементы.
и очевидно оптимизаруется тут число вызовов оракула.

Dasar

после каждого шага получается мы получаем 3 упорядоченных последовательности:
результат сорта, хвост первой ленточки, хвост второй ленточки
половина результата - это самые лучшие и идут в конечный результат
далее имеем три упорядоченных последовательности:
хвост результата сорта, хвост ленты1, хвост ленты2
можно заметить, что хвост сорта или полностью лучше ленты1, или полностью лучше ленты2, смотря откуда был взят элемент, который сейчас последний в хвосте сорта - это делается через одно сравнение ключей, и соответственно хвост результата можно "пристыковать" к одной из лент
на следующем шаге сортируем хвост предыдущего результата + элементы из той ленты, которая противопожная предыдущей пристыковке

Dasar

спасибо -у за идею
у меня только пожелание, чтобы в следующий раз идея формулировалась более удобным образом.

vall

хыхы, не дождёшься =)

kruzer25

спасибо -у за идею

Что делать в случае, если:
1) Заданная функция мультисравнения - чёрный ящик, сравнивает именно тех слонов, которые описываются в условии задачи, и
2) Выдаёт набор элементов, а не их индексов?

Dasar

1) Заданная функция мультисравнения - чёрный ящик, сравнивает именно тех слонов, которые описываются в условии задачи, и
2) Выдаёт набор элементов, а не их индексов?

индексы не нужны
нужно только уметь сравнивать ключи(сами элементы) на равенство

Andbar

нужно только уметь сравнивать ключи(сами элементы) на равенство

А если элементы - чёрные ящики?

Dasar

А если элементы - чёрные ящики?

но ссылка на ящики же все равно есть.
и эту ссылку можно сравнить на equals

Serab

А если элементы - чёрные ящики?

там в одном из уточнений топикстартера было указано «все элементы различны». Если же у нас кроме этой странной функции сравнения о них больше ничего не известно, то это понятие «различности» придется вводить несколько пугающе. Так что я думаю, там как раз подразумевалось именно то, что на равенство сравнить можно легко.

0000

Элементы различные - да, по условию.
Грубо говоря: массив это разные слова (~30 000 функция сравнения - может быть лексикографический порядок или сначала маленькие потом большие или какой нить хитрый, определенная на k слов (за раз можно упорядочить k эелементов). Необходимо упорядочить весь массив по заданному порядку.

Devid

Если речь идет о строках то можно попробовать использовать этот алгоритм http://en.wikipedia.org/wiki/ix_sort, там время O(kN где k - длина.

kruzer25

Речь идёт об объектах, которые ты можешь быстро сравнить на равенство, илимедленно узнать, какой из них больше, а какой - меньше, передав их функции сортировки (которая, в отличие от обычной, принимает на вход не два аргумента, а N, и упорядочивает их).