Здравствуйте, CoderMonkey, Вы писали:
CM>Имел собеседование со "специалистом" из Гугла. На вопрос "какова лучшая сложность для алгоритмов сортировки", ответил ему, что O(n). Нет, говорит, это неправильно — должно быть O(n * log n). Правильно, говорю, именно O(n). Есть такой radix sort, у него сложность именно такая. В ответ — недоуменно-возмущенное молчание. Похоже, не поверил.
Radix sort'ом нельзя сортировать гномиков. Для гугля это существенное ограничение. С такими ограничениями для них этого алкогоритма считай, что нет.
Здравствуйте, vsb, Вы писали:
vsb>Здравствуйте, kov_serg, Вы писали:
_>>Вообще-то у него этот логарифм в константе спрятан. Для чисел в два раза шире понадобиться в два раза больше операций. А рост n предполагает рост ширины данных иначе сортировка счетом
vsb>А сравнение двух чисел не предполагает O(ширины_числа)? А то тогда надо пересматривать сложность всех алгоритмов.
Предполагает, но там база у логарифмов разная. Для radix sort в случае с по-разрядной обработкой будет десятичный логарифм от максимального размера чисел. В случае сравнения базой логарифма будет скорее всего 2^64, а то и 2^128, что будет какую-то роль играть только в случае гигантских чисел при каких-нибудь хардкорных математических вычислениях, в реальных задачах, работающих с объектами реального мира, такие числа не используются.
Здравствуйте, VladiCh, Вы писали:
vsb>>Здравствуйте, kov_serg, Вы писали:
_>>>Вообще-то у него этот логарифм в константе спрятан. Для чисел в два раза шире понадобиться в два раза больше операций. А рост n предполагает рост ширины данных иначе сортировка счетом
vsb>>А сравнение двух чисел не предполагает O(ширины_числа)? А то тогда надо пересматривать сложность всех алгоритмов.
VC>Предполагает, но там база у логарифмов разная. Для radix sort в случае с по-разрядной обработкой будет десятичный логарифм от максимального размера чисел. В случае сравнения базой логарифма будет скорее всего 2^64, а то и 2^128, что будет какую-то роль играть только в случае гигантских чисел при каких-нибудь хардкорных математических вычислениях, в реальных задачах, работающих с объектами реального мира, такие числа не используются.
Какая разница, мы же про теоретическую сложность говорим. А сравнивать можно не только числа, но и строки, в том числе потенциально длинные, например.
Здравствуйте, vsb, Вы писали:
vsb>Какая разница, мы же про теоретическую сложность говорим. А сравнивать можно не только числа, но и строки, в том числе потенциально длинные, например.
Константа отбрасывается, потому что главный вопрос O-нотации — это как растет сложность с ростом объема данных. Размерность каждого элемента — это, как правило, именно константа. Но если это все же переменная, то ее тоже надо учитывать.
Здравствуйте, vsb, Вы писали:
vsb>Здравствуйте, VladiCh, Вы писали:
vsb>>>Здравствуйте, kov_serg, Вы писали:
_>>>>Вообще-то у него этот логарифм в константе спрятан. Для чисел в два раза шире понадобиться в два раза больше операций. А рост n предполагает рост ширины данных иначе сортировка счетом
vsb>>>А сравнение двух чисел не предполагает O(ширины_числа)? А то тогда надо пересматривать сложность всех алгоритмов.
VC>>Предполагает, но там база у логарифмов разная. Для radix sort в случае с по-разрядной обработкой будет десятичный логарифм от максимального размера чисел. В случае сравнения базой логарифма будет скорее всего 2^64, а то и 2^128, что будет какую-то роль играть только в случае гигантских чисел при каких-нибудь хардкорных математических вычислениях, в реальных задачах, работающих с объектами реального мира, такие числа не используются.
vsb>Какая разница, мы же про теоретическую сложность говорим. А сравнивать можно не только числа, но и строки, в том числе потенциально длинные, например.
При сравнении строк обычно никто и не говорит что сложность сравнения является константой. Там длина строки принимается во внимание.
Мы же сейчас говорим про числа, а здесь с практической точки зрения сравнение является константой, за исключением специфических математических вычислений, когда верхний предел чисел не задан, тогда длину числа тоже нужно принимать во внимание.
Здравствуйте, CoderMonkey, Вы писали:
CM>Имел собеседование со "специалистом" из Гугла. На вопрос "какова лучшая сложность для алгоритмов сортировки", ответил ему, что O(n). Нет, говорит, это неправильно — должно быть O(n * log n). Правильно, говорю, именно O(n). Есть такой radix sort, у него сложность именно такая. В ответ — недоуменно-возмущенное молчание. Похоже, не поверил. CM>Кажется, никакое продолжение мне не светит
Смотрю на тред, читаю что пишешь и понимаю — гугл интервью работает. Таких как ты нельзя пускать в хорошие конторы. Проф уровень не дотягивает пока, извините, попробуйте через год.
ПС. Работал в Гугле, собеседовал.
Не стыдно попасть в дерьмо, стыдно в нём остаться!
Здравствуйте, vsb, Вы писали:
vsb>А сравнение двух чисел не предполагает O(ширины_числа)? А то тогда надо пересматривать сложность всех алгоритмов.
Ну это вдвое больше операций внутри процессора, но снаружи торчит О(1).
Что касается радикса, то таки да, для 64-битных чисел вдвое больше операций, чем для 32-битных.
Здравствуйте, CoderMonkey, Вы писали:
CM>Данные можешь представить алгоритму в любой форме, которая тебе нужна. Не намного сложнее, чем написать компаратор для классов (хотя, конечно, и с этим многие не справляются) CM>[cs] CM>int GetDigit(SomeClass field, int index)
Ну напиши что ли реализацию сего метода для класса BigInt. Ну или хотя бы для сраного Float32.
Здравствуйте, demi, Вы писали:
D>Смотрю на тред, читаю что пишешь и понимаю — гугл интервью работает. Таких как ты нельзя пускать в хорошие конторы. Проф уровень не дотягивает пока, извините, попробуйте через год.
D>ПС. Работал в Гугле, собеседовал.
Что самое характерное, по делу — вообще ни слова, только битье себя пяткой в грудь. Если гугл-интервью и работают, то скорее в обратную сторону — пропускают только некомпетентных зубрил.
Здравствуйте, CodeMonkey, Вы писали:
CM>Здравствуйте, T4r4sB, Вы писали:
TB>>Ну напиши что ли реализацию сего метода для класса BigInt. Ну или хотя бы для сраного Float32.
CM>А в чем проблема вообще?
Напиши, я гляну и скажу. Я вот не могу, например. Ну может, это я тупой. Но всё же докажи мне это.
Здравствуйте, T4r4sB, Вы писали:
TB>Напиши, я гляну и скажу. Я вот не могу, например. Ну может, это я тупой. Но всё же докажи мне это.
А после этого ты напишешь, что это ничего не значит, и потребуешь еще чего-нибудь?
Начнем с того, что постановка задачи ни к черту не годится. BigInt — это вообще что за тип, из какого языка?
Здравствуйте, CodeMonkey, Вы писали:
CM>А после этого ты напишешь, что это ничего не значит, и потребуешь еще чего-нибудь?
Нет, я просто хочу видеть, как ты напишешь радикс-сорт для бигинтов или флоатов.
CM>Начнем с того, что постановка задачи ни к черту не годится. BigInt — это вообще что за тип, из какого языка?
А сейчас ты придуриваешься. Это реализация ооочень больших целых. Пусть бигинт представляет собой вектор из десятичных цифр, от младшей к старшей. Ну, показывай свою функцию извлечения разряда.
Здравствуйте, T4r4sB, Вы писали:
TB>А сейчас ты придуриваешься.
Я мысли читать не умею.
TB>Это реализация ооочень больших целых. Пусть бигинт представляет собой вектор из десятичных цифр, от младшей к старшей. Ну, показывай свою функцию извлечения разряда.
Принцип тот же, что со строками переменной длины. Либо сначала делаем проход по всем значениям и находим максимальное число разрядов, далее всё тривиально. Либо считаем, что на первом шаге сортировки номер корзины — это число разрядов в данном числе.
Разжевывать надо?
CM>Принцип тот же, что со строками переменной длины. Либо сначала делаем проход по всем значениям и находим максимальное число разрядов, далее всё тривиально.
Ааа, то есть универсальность уже не та?
CM>Либо считаем, что на первом шаге сортировки номер корзины — это число разрядов в данном числе. CM>Разжевывать надо?
Да, такой вариант сработает. Но мы уже видим, что радикс уже не столь универсален и для каждого типа приходится делать свои уникальные вставки в общий алгоритм.
Как будешь флоаты сортировать?
Здравствуйте, T4r4sB, Вы писали:
TB>Ааа, то есть универсальность уже не та?
Если не написана функция сравнения, то квиксорт работать не будет. Квиксорт уже не тот!
TB>Да, такой вариант сработает. Но мы уже видим, что радикс уже не столь универсален и для каждого типа приходится делать свои уникальные вставки в общий алгоритм.
Не в алгоритм, а всего лишь в функцию выборки. Учись проектировать, юнга
TB>Как будешь флоаты сортировать?
Примерно так же. Сначала по порядку, потом по мантиссе.
Здравствуйте, CodeMonkey, Вы писали:
CM>Если не написана функция сравнения, то квиксорт работать не будет. Квиксорт уже не тот!
Написать сравнивалку как-то проще и понятнее. Я вот впаду в ступор, если увижу алгоритм, который требует на вход "определить максимальный порядок", и "взять цифру данного порядка, зная максимальный порядок", как-то сложновато как по мне.
TB>>Как будешь флоаты сортировать?
CM>Примерно так же. Сначала по порядку, потом по мантиссе.
А, для них это, допустим, прокатит. Но это скорее везение.
Здравствуйте, T4r4sB, Вы писали:
TB>Написать сравнивалку как-то проще и понятнее. Я вот впаду в ступор, если увижу алгоритм, который требует на вход "определить максимальный порядок", и "взять цифру данного порядка, зная максимальный порядок", как-то сложновато как по мне.
Для тривиальных типов, естественно, нужно сделать функции выборки еще при разработке алгоритма.
Но это всё мимо темы. Вопрос был про алгоритмическую сложность, а не сложность реализации.
TB>А, для них это, допустим, прокатит. Но это скорее везение.
