Здравствуйте, CoderMonkey, Вы писали:
CM>ХЗ кто это написал, но общего с обычным квиксортом — практически ничего.
Ну конечно!
BFE>>Так что ответите про количество операций? CM>Как уже было написано — в худшем случае, O(N*K). Если K=N, то О(N^2).
А если K=N2, то...
CM>У квиксорта в этом же случае будет от O(N^2 * log N) до O(N^3 * log N)
О небо! В этом же? Вы настаиваете?
для 10 тысяч строк длиной по миллиону символов каждая, например.
CM>>У квиксорта в этом же случае будет от O(N^2 * log N) до O(N^3 * log N) BFE>О небо! В этом же? Вы настаиваете?
Абсолютно очевидно, что сравнение строк длиной N символов — обойдется куда дороже, что сравнение строк по C символов.
Здравствуйте, B0FEE664, Вы писали:
ylp>>Смысл в отсеивании неадекватных людей на ранних стадиях собеседования BFE>Если все адекватные, так на работе и поговорить будет не о чем. Скучно.
для этого есть RSDN!
>>> В большинстве контор прямо запрещено писать свои сортировки. ylp>>Запрещено переизобретать велосипед. Писать свои алгоритмы, весьма похожие на сортировку, иногда приходится. Например, когда данные лежат на ~500 разных машинах и суммарно занимают несколько сотен терабайт. BFE>Ну если у вас 500 разных машинах и несколько сотен терабайт, то тогда, конечно, сортировку имеет смысл спрашивать.
в Гугле и ряде других мест, где именно так, ее и спрашивают
Здравствуйте, CoderMonkey, Вы писали:
рытий сделате.
CM>Для начала, хотелось бы увидеть какие-то доказательства
Ну вот и начали сливаться, как и ожидалось. А как дышал, как дышал!
CM>А писать ничего не надо — старый код уже лежит у меня на диске.
Подозреваю, что вы типичный балабол-фантаст. Кода, реализующего radix sort для массива из N строк длины N у вас нет. Потому как если он есть, его можно выложить, чтобы все желающие его могли запустить и протестировать, а если нет, приходится вот выкручиваться и отползать, что мы и наблюдаем.
Здравствуйте, ylp, Вы писали:
ylp>Подозреваю, что вы типичный балабол-фантаст. Кода, реализующего radix sort для массива из N строк длины N у вас нет. Потому как если он есть, его можно выложить, чтобы все желающие его могли запустить и протестировать, а если нет, приходится вот выкручиваться и отползать, что мы и наблюдаем.
Не собираюсь метать бисер перед трололо, который даже сам признался, что он трололо.
CM>AAAAAA.....AAAAAAAAZ CM>AAAAAA.....AAAAAAAAY CM>.... CM>AAAAAA.....AAAAAAAAA
CM>Абсолютно очевидно, что сравнение строк длиной N символов — обойдется куда дороже, что сравнение строк по C символов.
Ну очень упрямый мальчик
До все все никак не дойдет, что дело не в том, что на таких данных квиксорт работать будет плохо (да, будет), а в том, что radix sort будет реботать еще хуже либо не будет работать совсем. Но чтобы понять, почему именно, вам нужно будет код напиать и на таких данных его запустить.
Но, как мы все тут видим, когда дело доходит до написания кода, вы предсказуемо сливаетесь. Так мы и будем мучаться неведением
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Подозреваю, что вы типичный балабол-фантаст. Кода, реализующего radix sort для массива из N строк длины N у вас нет. Потому как если он есть, его можно выложить, чтобы все желающие его могли запустить и протестировать, а если нет, приходится вот выкручиваться и отползать, что мы и наблюдаем.
CM>Не собираюсь метать бисер перед трололо, который даже сам признался, что он трололо.
А как дышал, как дышал! Три дня бился и троллям что-то доказывал!
Чао! Но вы вернетесь, я знаю. Как тот охотник из анекдота
PS: У меня для вас есть отличный тестовый набор строк; дико интересно, как ваша реализация себя на нем поведёт.
Здравствуйте, ylp, Вы писали:
ylp>Ну очень упрямый мальчик
Я вижу
ylp>До все все никак не дойдет, что дело не в том, что на таких данных квиксорт работать будет плохо (да, будет), а в том, что radix sort будет реботать еще хуже либо не будет работать совсем.
На самом деле — ровно наоборот. И чтобы это понять, тебе все-таки надо постараться и напрячь мозги.
ylp>Но, как мы все тут видим, когда дело доходит до написания кода, вы предсказуемо сливаетесь. Так мы и будем мучаться неведением
За риталином — бегооом марш. И еще — "мы" про себя уместно говорить только королям, понтификам и людям с глистами.
Здравствуйте, CoderMonkey, Вы писали:
CM>То квиксорт вообще сдохнет нахрен. CM>Попробуй например такие данные:
CM>AAAAAA.....AAAAAAAAZ CM>AAAAAA.....AAAAAAAAY CM>.... CM>AAAAAA.....AAAAAAAAA
CM>для 10 тысяч строк длиной по миллиону символов каждая, например.
Это ваш (MSD) radix sort сдохнет, а квиксорт отработает за O(N^2) или быстрее.
И я даже вам могу объяснить почему.
Рассмотрим 3 строки:
AAAAAA.....AAAAAAAAX // X строка
AAAAAA.....AAAAAAAAY // Y строка
AAAAAA.....AAAAAAAAZ // Z строка
В квиксорт учитывается следующие знание: если мы сравнили строку X со строкой Y и строку Y со строкой Z, то мы знаем, что строка X меньше строки Z (и сравнивать X строку с Z строкой не нужно), а вот radix sort это не учитывает и выполнит перекладывание по каждому символу до конца всех строк.
ЗЫ А ещё я знаю умное слово 'транзитивность'.
PSS Спасибо, что доказали, что в википедии фигня написана. Действительно, MSD radix sort не квиксорт.
Здравствуйте, B0FEE664, Вы писали:
BFE>Это ваш (MSD) radix sort сдохнет, а квиксорт отработает за O(N^2) или быстрее.
Не надо выдумывать. Надо запустить и посмотреть, как квиксорт встанет раком на довольно небольшом массиве таких данных.
BFE>PSS Спасибо, что доказали, что в википедии фигня написана. Действительно, MSD radix sort не квиксорт.
Здравствуйте, CoderMonkey, Вы писали:
BFE>>Это ваш (MSD) radix sort сдохнет, а квиксорт отработает за O(N^2) или быстрее. CM>Не надо выдумывать. Надо запустить и посмотреть, как квиксорт встанет раком на довольно небольшом массиве таких данных.
Вы так говорите, как будто квиксорт лучшая сортировка и я её рекомендую.
Здравствуйте, B0FEE664, Вы писали:
BFE>Вы так говорите, как будто квиксорт лучшая сортировка и я её рекомендую.
Отож.
На самом деле, одна очень простая вещь, до которой так и не допер ylp — что слабое место радикс сорта вовсе не большие данные, а наоборот маленькие. Массивы меньше ~1000 элементов — там квиксорт и правда быстрее.
А на больших данных, квиксорт сливается стабильно, и чем больше данных — тем сильнее.
Здравствуйте, CoderMonkey, Вы писали:
CM>Отож. CM>На самом деле, одна очень простая вещь, до которой так и не допер ylp — что слабое место радикс сорта вовсе не большие данные, а наоборот
Вам думать много вредно, вы каждый раз когда думать пытаетесь, все время чушь писать начинаете То про алфавит размера миллион, то про асимтотику радикс сорта.
>маленькие. Массивы меньше ~1000 элементов — там квиксорт и правда быстрее. CM>А на больших данных, квиксорт сливается стабильно, и чем больше данных — тем сильнее.
На больших данных ваш алгоритм тупо не работает. Но вам до этого допереть будет невозможно, вы его не в состоянии написать и понять, почему
Здравствуйте, ylp, Вы писали:
ylp>Вам думать много вредно, вы каждый раз когда думать пытаетесь, все время чушь писать начинаете То про алфавит размера миллион
То есть, про UTF-32 ты тоже никогда не слышал. Макс число символов — как раз миллион с хвостиком
Иди уже учебники почитай, собеседующий в перьях.
Но в целом да, демонстрация неадекватности тебе удалась на отлично. Спасибо за наглядный пример.
Здравствуйте, CoderMonkey, Вы писали:
BFE>>Вы так говорите, как будто квиксорт лучшая сортировка и я её рекомендую. CM>Отож.
А нет. Сортировка кучей будет круче.
CM>На самом деле, одна очень простая вещь, до которой так и не допер ylp — что слабое место радикс сорта вовсе не большие данные, а наоборот маленькие. Массивы меньше ~1000 элементов — там квиксорт и правда быстрее. CM>А на больших данных, квиксорт сливается стабильно, и чем больше данных — тем сильнее.
Ну что тут скажешь. radix sort вам к лицу: не стоит останавливаться, если биты ещё не закончились.
Здравствуйте, CoderMonkey, Вы писали:
CM>За риталином — бегооом марш. И еще — "мы" про себя уместно говорить только королям, понтификам и людям с глистами.
Не, как минимум я ещё с интересом наблюдаю за очередным вашим сливанием при просьбе предоставить код.
Кстати, в прошлый раз вы оправдывались тем, что "А где же я Delphi найду". А теперь какие превратности судьбы мешают вам писать код?
Здравствуйте, Somescout, Вы писали:
S>Не, как минимум я ещё с интересом наблюдаю за очередным вашим сливанием при просьбе предоставить код. S>Кстати, в прошлый раз вы оправдывались тем, что "А где же я Delphi найду". А теперь какие превратности судьбы мешают вам писать код?
А какой смысл показывать код человеку, который все равно ни черта не поймет и будет пороть полную чушь?
Безотносительно к твоему мнению о текущем споре, скажи честно — ты можешь не согласиться с этим утверждением?
