Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Big-O notation как мы уже выяснили, она про время, а не про число операций.
CM>Тебе никогда не приходило в голову — а почему в Big-O notation фигурирует название сложность алгоритма, а не "скорость" или "время выполнения"?
Нет, расскажите!
CM>>>>>И вместо C1 * O(N) ты получишь C2 * O(N), где C2 < C1 ylp>>Зачем оспаривать бред людей, которые базовых вещей не понимают. Это скучно. Интереснее вас просто троллить. CM>Еще раз. Ты в состоянии оспорить утверждение выше, или будешь и дальше устраивать истерику?
Я в состоянии оспорить его, мне просто уже скучно, вчера весь вечер цирк был, сегодня уже надоедает по второму разу.
ylp>>Повторяю для особо одаренных: размер сортирующей сети пропорционален n*log^2(n).
CM>А теперь посчитай, какой размер сети тебе понадобится для массива в, хотя бы, 1 миллион элементов. Я уверен, ты сможешь справиться с этой не слишком сложной математикой.
Посчитал: на один миллион элементов понадобится порядка 36 миллионов компараторов, дальше что?
Я вам щас страшную тайну скажу: в одном современном процессоре около нескольких миллиардов транзисторов, прикиньте!
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Ага. ylp>>Задание для не совсем тупых: оценить количество операций сравнения символов в алгоритме, который указаным вами способом сортирует массив строк, длина каждой из которой равна размеру массива. Сравнить с квиксортом, много думать (надуюсь, у вас получится!).
CM>Даю намек. Попробуй оценить количество операций сравнения символов в алгоритме QuickSort, который сортирует массив строк, длина каждой из которой равна размеру массива.
Так я надеялся, вы это сделаете, но вы отказались. Давайте я подскажу: число операций сравнения символов в алгоритме квиксорт будет существенное меньше, чем в вашем алгоритме.
Здравствуйте, ylp, Вы писали:
ylp>Нет, расскажите!
Напряги мозги.
ylp>Я в состоянии оспорить его, мне просто уже скучно, вчера весь вечер цирк был, сегодня уже надоедает по второму разу.
То есть, внятных аргументов против у тебя нет.
ylp>Я вам щас страшную тайну скажу: в одном современном процессоре около нескольких миллиардов транзисторов, прикиньте!
Ты конкретное число давай. А потом прикинем — сколько транзисторов надо для каждого такого элемента, который сравнивает числа хотя бы по 32 бита.
Здравствуйте, ylp, Вы писали:
ylp>Давайте я подскажу: число операций сравнения символов в алгоритме квиксорт будет существенное меньше, чем в вашем алгоритме.
Давай конкретный результат, а я пока схожу за попкорном.
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Давайте я подскажу: число операций сравнения символов в алгоритме квиксорт будет существенное меньше, чем в вашем алгоритме.
CM>Давай конкретный результат, а я пока схожу за попкорном.
Давайте вы сами посчитаете. Подсказываю еще раз: для вашего алгоритма требуется всегда обрабатывать все символы всех строк. Для квиксорта — нет (для совсем тупых — результат сравнения двух строк обычно появляется раньше, чем будут обработаны все символы обеих строк). Как же вам все-таки нравится выставлять себя идиотом
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Нет, расскажите! CM>Напряги мозги.
не хочу!
ylp>>Я в состоянии оспорить его, мне просто уже скучно, вчера весь вечер цирк был, сегодня уже надоедает по второму разу. CM>То есть, внятных аргументов против у тебя нет.
ну то есть разговр про "наилучшая сложность алгоритмов сортировки" вы плавно слили и теперь мы обсуждаем сколько транзисторов нужно, чтобы сделать сеть компараторов для сортировки массива из миллиона элементов. Про то, что обсуждали мы сложность алгоритмов, а не детали их практической реализации в железе, предполчитаем тихонько молчать, понимаю.
>А потом прикинем — сколько транзисторов надо для каждого такого элемента, который сравнивает числа хотя бы по 32 бита.
давайте, прикидывайте. Сколько транзисторов нужно, чтобы сделать один компаратор на 32 бита, за вас гуглить я не хочу, уже надоело. "Упрешься в потолок", ага Люди, работащие с ASICами, смотрят на вас с еще большим недоумением, чем люди, которые писали сортировку подсчетом.
Здравствуйте, ylp, Вы писали:
ylp>Давайте вы сами посчитаете.
Нет, не давайте.
ylp>Подсказываю еще раз: для вашего алгоритма требуется всегда обрабатывать все символы всех строк.
Во первых, он не мой. Во вторых, не всегда, а только в худшем случае.
ylp>Для квиксорта — нет (для совсем тупых — результат сравнения двух строк обычно появляется раньше, чем будут обработаны все символы обеих строк).
Только в том случае, если у тебя этих строк горстка и они все начинаются на разные символы.
Ну так что, сможешь посчитать, какой О получается в реальности, а не в твоих розовых мечтах?
ylp>Как же вам все-таки нравится выставлять себя идиотом
Похоже, тебя кто-то очень сильно на работе обидел Но ты попробуй всё-таки быть мужиком и не срываться на посторонних.
А может, ты все-таки завяжешь со своими истериками?
ylp>ну то есть разговр про "наилучшая сложность алгоритмов сортировки" вы плавно слили и теперь мы обсуждаем сколько транзисторов нужно, чтобы сделать сеть компараторов для сортировки массива из миллиона элементов. Про то, что обсуждали мы сложность алгоритмов, а не детали их практической реализации в железе, предполчитаем тихонько молчать, понимаю.
Если рассуждать о гипотетической сложности алгоритмов, которые невозможно реализовать в железе, то на самом деле лучший алгоритм сортировки имеет константную сложность, так что твой ответ все равно неверен
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Давайте вы сами посчитаете.
CM>Нет, не давайте.
печально, чо. Так и будете пребывать в неведении.
ylp>>Подсказываю еще раз: для вашего алгоритма требуется всегда обрабатывать все символы всех строк. CM>Во первых, он не мой. Во вторых, не всегда, а только в худшем случае.
Неужели? В каком случае радикс сорт НЕ обрабатывает каждую цифру каждого числа при сортировке массива? Вы еще и про детали работы радикс сорта, похоже, не вполне в курсе, понимаю.
ylp>>Для квиксорта — нет (для совсем тупых — результат сравнения двух строк обычно появляется раньше, чем будут обработаны все символы обеих строк). CM>Только в том случае, если у тебя этих строк горстка и они все начинаются на разные символы.
Спасибо, КО!
CM>Ну так что, сможешь посчитать, какой О получается в реальности, а не в твоих розовых мечтах?
Я вам предлагаю то же самое. Давайте, продемонстрируйте свою крутизну, покажите тут всем как вы классно считать умеете.
ylp>>Как же вам все-таки нравится выставлять себя идиотом CM>Похоже, тебя кто-то очень сильно на работе обидел Но ты попробуй всё-таки быть мужиком и не срываться на посторонних.
Не надо свои проблемы на других проецировать. Обидели вас — завалили на скрининге в гугл, вас это до сих пор не отпускает, а я тут просто развлекаюсь, потому что вас весело троллить. Не волнуйтесь, скоро перестану — это невозможно целый рабочий день делать.
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>не хочу! CM>А может, ты все-таки завяжешь со своими истериками?
Почему вы называете истериками мое нежелание делать то, то вы мне указываете?
ylp>>ну то есть разговр про "наилучшая сложность алгоритмов сортировки" вы плавно слили и теперь мы обсуждаем сколько транзисторов нужно, чтобы сделать сеть компараторов для сортировки массива из миллиона элементов. Про то, что обсуждали мы сложность алгоритмов, а не детали их практической реализации в железе, предполчитаем тихонько молчать, понимаю.
CM>Если рассуждать о гипотетической сложности алгоритмов, которые невозможно реализовать в железе, то на самом деле лучший алгоритм сортировки имеет константную сложность, так что твой ответ все равно неверен
Сортирующие сети вполне можно реализовать в железе (и их вполне успешно реализуют). Я понимаю, очень не хочется это признавать, но жизнь гораздо многограннее однопроцессорных тьюринговых машин и алгоритмов сортировки для них. А вопросы на интервью надо внимательно слушать и уточнять, чтобы не садится в лужу.
Здравствуйте, ylp, Вы писали:
ylp>Неужели? В каком случае радикс сорт НЕ обрабатывает каждую цифру каждого числа при сортировке массива? Вы еще и про детали работы радикс сорта, похоже, не вполне в курсе, понимаю.
Если в бакете остается одна строка — то, совершенно очевидно, идти дальше не нужно.
ylp>Я вам предлагаю то же самое. Давайте, продемонстрируйте свою крутизну, покажите тут всем как вы классно считать умеете.
Число сравнений символов для N строк по N символов, лучший (абсолютно идеальный) случай, т.е. все строки начинаются на разные символы:
quick sort — O(N * log N)
radix sort — O(N)
Нормальный случай:
quick sort — O(N^2 * log N)
radix sort — O(N^2)
ylp>Не надо свои проблемы на других проецировать. Обидели вас — завалили на скрининге в гугл, вас это до сих пор не отпускает, а я тут просто развлекаюсь, потому что вас весело троллить. Не волнуйтесь, скоро перестану — это невозможно целый рабочий день делать.
Писать злобный тупняк — это не то же самое, что троллить. Увы, тупые люди этого не понимают.
Здравствуйте, ylp, Вы писали:
ylp>Почему вы называете истериками мое нежелание делать то, то вы мне указываете?
А указываю я — подтвердить слова конкретными аргументами. Так что да, у тебя именно истерика.
ylp>Сортирующие сети вполне можно реализовать в железе (и их вполне успешно реализуют).
Можно — для маленьких массивов. А для массивов чуть больше — увы, но технологии и просто законы физики не позволяют.
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Почему вы называете истериками мое нежелание делать то, то вы мне указываете?
CM>А указываю я — подтвердить слова конкретными аргументами. Так что да, у тебя именно истерика.
Да нет, вы мне указываете "включить мозг" и прочие странные вещи.
ylp>>Сортирующие сети вполне можно реализовать в железе (и их вполне успешно реализуют). CM>Можно — для маленьких массивов. А для массивов чуть больше — увы, но технологии и просто законы физики не позволяют.
Спасибо, КО! Вы не заметили, что теперь вы сами себе противоречите? Еще совсем недавно вы говорили про "невозможно реализовать в железе". теперь вы заголворили про "маленькие массивы". Еще совсем немного и вы скажете, что "маленькие" — это ваше личное понимание этого слова и "миллион" — тоже маленький, а вот сто миллиардов — нет.
Но хорошо хоть что признали, что алгоритм сортировки, сортирующий быстрее, чем O(N) таки существует (хоть и применим не всегда) и согласно вашей же логике, на интервью ответ O(N) без уточнение вопроса был неверным.
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Неужели? В каком случае радикс сорт НЕ обрабатывает каждую цифру каждого числа при сортировке массива? Вы еще и про детали работы радикс сорта, похоже, не вполне в курсе, понимаю.
CM>Если в бакете остается одна строка — то, совершенно очевидно, идти дальше не нужно.
ylp>>Я вам предлагаю то же самое. Давайте, продемонстрируйте свою крутизну, покажите тут всем как вы классно считать умеете.
CM>Число сравнений символов для N строк по N символов, лучший (абсолютно идеальный) случай, т.е. все строки начинаются на разные символы: CM>quick sort — O(N * log N) CM>radix sort — O(N)
Чтобы в массиве из миллиона строк каждая строка начиналась на разный символ, размер алфавита должен быть равен миллиону.
Дальше не читал, устал смеяться.
Здравствуйте, ylp, Вы писали:
ylp>Я попробую включить тепелата и предположить что в вопросе упоминались алгоритмы сортировки, сравнивающие элементы попарно. Для этих алгоритмов есть математическое доказательство того, что лучше чем в O(NLogN) они работать не могут, это видимо и был предполагаемый ответ на вопрос. А объяснять это вам не стали, потому что целью собеседующего не является вас просвещать.
А знаете ли вы, что в военное время значение синуса может достигать 4-х? Итак, дано: в войсковую часть привезли из прачечной носки зелёного и чёрного цвета в количестве N штук. Нужно их рассортировать по цвету. Достаём из коробки по 2 штуки и сравниваем попарно. Какова сложность алгоритма?
Здравствуйте, Тёмчик, Вы писали:
CM>>Непонятно — что конкретно сортировать? У тебя есть файл JSON, а в нем что? Тё>В каждой записи есть некое поле field1, field2
Есть файл JSON, а в нём есть записи... Тогда нужно сортировать курсором!
Здравствуйте, denisko, Вы писали:
mgu>>Когда меня впервые спросили про лучшую сортировку (их как раз канонизировали, а я не следил за новостями вселенских соборов), то я искренне ответил: "домЕнная". Слив был засчитан -- не спрашивать же, что это такое? Так что можно смело называть алгоритм Гогенфишмана-Макакагавы и получать три раза ку. D>Мы для этой цели придумали куст Лапласа. Применяется в контексте "Ну как же можно не знать таких простых вещей как куст лапласа" или "Или ну этот алгоритм сводится к правильному использованию куста лапласа" к людям которые любят именами разбрасываться. Что интересно почти ссегда работает. Чтобы вызывать у пациента смутное подозрение, что его развели, можно в конце разговора упомянуть пень гамильтона.
Если куст, то Канта. Думаю, что вы постесняетесь узнать, почему так.
Здравствуйте, ylp, Вы писали:
ylp>Да нет, вы мне указываете "включить мозг" и прочие странные вещи.
Что поделаешь, если тебе это крайне необходимо.
ylp>Спасибо, КО! Вы не заметили, что теперь вы сами себе противоречите? Еще совсем недавно вы говорили про "невозможно реализовать в железе".
Врешь. Мой контраргумент с самого начала, цитирую — "бесконечно большие сортирующие сети невозможны"
ylp>Еще совсем немного и вы скажете, что "маленькие" — это ваше личное понимание этого слова и "миллион" — тоже маленький, а вот сто миллиардов — нет.
Это вряд ли, поскольку уже миллион — далеко за пределами нынешних технологий. На самом деле, я очень удивлюсь, если удастся втиснуть хотя бы 100 тысяч.
ylp>Но хорошо хоть что признали, что алгоритм сортировки, сортирующий быстрее, чем O(N) таки существует (хоть и применим не всегда) и согласно вашей же логике, на интервью ответ O(N) без уточнение вопроса был неверным.
См выше про разницу между "сложностью алгоритма" и "скоростью алгоритма". Вопрос был про сложность, не про скорость или время. И да — включи, наконец, мозги.
Здравствуйте, ylp, Вы писали:
ylp>Чтобы в массиве из миллиона строк каждая строка начиналась на разный символ, размер алфавита должен быть равен миллиону.
Да, начинаешь немного соображать. Именно поэтому я написал "идеальный" и "реальный" случай отдельно.
Что-нибудь ответить по существу можешь?
Но ты попробуй всё-таки быть мужиком и не срываться на посторонних.
