ОК>>Видишь ли, я верю что ты можешь писать код на работе, но в данном случае это был больше вопрос не на написать а на помнишь ли ты как это работает изнутри. Такое быстро забывается после учебы. Поэтому я и отказываюсь верить что ты помнишь быструю сортировку.
G>Забывается то, что ты не понял. В универе, как и в школе, часто пытаются вбить в голову факты, вместо объяснения принципов. G>Чтобы понять принципы построения алгоритмов на основе рекурсии я прочитал немало книг, поэтому для меня не проблема написать быстрою сортировку.
Забывается то с чем дела не имеешь напостоянку.
Re[8]: Аморально ли требовать алгоритмы на архитектора
ОК>>Что значит не силен в алгоритмах? G>Если челоек считает что алгоритмы не надо спрашивать на собеседовании значит что он и ни не силен. Был бы силен — не писал бы на форуме.
Ты, чувак, видишь разницу между знать что есть такие-то структуры данных и такие-то алгоритмы версус того чтобы требовать их имплементацию?
G>У меня был случай — надо было написать функцию, которая превращает IEnumerable<T> в IEnumerable<IEnumerable<T>>, нарезая входную последовательность на блоки по определенному условию, зависящему от нескольких предыдущих элементов. G>Я потом эту задачу на собеседовании давал. Код менее чем на 20 строк. Из 10 кандидатов справилось два. При этом все прекрасно знали linq, yield, как устроен IEnumerable и то, что енумератор — value type.
Что-то ты переусложняешь все.
Re[8]: Аморально ли требовать алгоритмы на архитектора
N>А поставлю я тебе минус за незнание стандартной библиотеки. Никто тебе не гарантирует, что в STL есть быстрая сортировка. Про std::sort все знают, что там быстрая сортировка внутри может или вызываться всегда, или в частном случае, или вообще не быть реализованной. Но и функция std::qsort ведёт себя совершенно аналогично, цитирую оттуда: N>
N>Despite the name, C++, C, and POSIX standards do not require this function to be implemented using quicksort or make any complexity or stability guarantees.
Да хоть десять, чувак! Пойнт который ты не понял это то, что ты будешь использоваться сишный qsort() или std::sort<>() как бы ты тут не рассуждал об алгоритмах сортировки.
То чем занимаешься ты называется буквоедство. В реальном коде нужно использовать стандартную библиотеку и понимать, что автор в них сделал разумные вещи (а не какую-нибудь пузырьковую сортировку). Все!
N>Так что твои знания в области алгоритмов совсем не достаточны для архитектора.
Ну ясно, в общем. Ты, как я понял, будешь городить свою сортировку вместо библиотечной. Знания-то надо применить!
Re[5]: Аморально ли требовать алгоритмы на архитектора
DB>И ещё момент. Когда ты поправишь первую ошибку, начнёт ломаться здесь.
Да это мелочи. Разумеется, дай ему время, спокойную обстановку, компьютер и литературу, и он сделает все правильно.
Тут вопрос в другом. Помнит он этот квиксорт как он говорит или все-таки полез в википедию?
Ну и еще тут один момент. Сэджвик защитил диссертацию по квиксорту, а тут некоторые товарищи утверждают что напишут код слету да еще и на интервью. Поражаюсь ихней самоуверенности.
Re[9]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Олег К., Вы писали:
ОК>Да хоть десять, чувак! Пойнт который ты не понял это то, что ты будешь использоваться сишный qsort() или std::sort<>() как бы ты тут не рассуждал об алгоритмах сортировки. ОК>То чем занимаешься ты называется буквоедство. В реальном коде нужно использовать стандартную библиотеку и понимать, что автор в них сделал разумные вещи (а не какую-нибудь пузырьковую сортировку). Все!
Не буквоедство. Я буду использовать именно то, что мне лучше подходит в данный момент.
N>>Так что твои знания в области алгоритмов совсем не достаточны для архитектора. ОК>Ну ясно, в общем. Ты, как я понял, будешь городить свою сортировку вместо библиотечной. Знания-то надо применить!
Ничего тебе не ясно. Я буду использовать подходящий алгоритм. А знать, что скрывается за стандартными сортам всё равно надо, ведь всегда могут попасться данные, которые могут сильно замедлить ту же быструю сортировку. Вот невежда и не будет использовать тот же qsort. Если же он будет знать, что за ним скрывается, то и проблем не будет. Так что в архитекторы ты точно не годишься.
Простому кодеру пофиг — использует то, что есть.
Re[10]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Nuzhny, Вы писали:
N>Ничего тебе не ясно. Я буду использовать подходящий алгоритм. А знать, что скрывается за стандартными сортам всё равно надо, ведь всегда могут попасться данные, которые могут сильно замедлить ту же быструю сортировку. Вот невежда и не будет использовать тот же qsort. Если же он будет знать, что за ним скрывается, то и проблем не будет. Так что в архитекторы ты точно не годишься. N>Простому кодеру пофиг — использует то, что есть.
И будешь ты его использовать, разумеется, сразу, а не потом, когда выяснишь, что твой qsort узкое место в производительности...
Re[10]: Аморально ли требовать алгоритмы на архитектора
ОК>>Да хоть десять, чувак! Пойнт который ты не понял это то, что ты будешь использоваться сишный qsort() или std::sort<>() как бы ты тут не рассуждал об алгоритмах сортировки. ОК>>То чем занимаешься ты называется буквоедство. В реальном коде нужно использовать стандартную библиотеку и понимать, что автор в них сделал разумные вещи (а не какую-нибудь пузырьковую сортировку). Все!
N>Не буквоедство. Я буду использовать именно то, что мне лучше подходит в данный момент.
То есть ты все-таки пишешь свою версию сортировки, ака изобретение велосипеда, вместо того чтобы использовать стандартную функцию?
N>>>Так что твои знания в области алгоритмов совсем не достаточны для архитектора. ОК>>Ну ясно, в общем. Ты, как я понял, будешь городить свою сортировку вместо библиотечной. Знания-то надо применить!
N>Ничего тебе не ясно. Я буду использовать подходящий алгоритм. А знать, что скрывается за стандартными сортам всё равно надо, ведь всегда могут попасться данные, которые могут сильно замедлить ту же быструю сортировку. Вот невежда и не будет использовать тот же qsort. Если же он будет знать, что за ним скрывается, то и проблем не будет. Так что в архитекторы ты точно не годишься. N>Простому кодеру пофиг — использует то, что есть.
Ты, чувак, теоретизируешь или ты уже писал свои функции сортировки вместо того чтобы использовать в коде стандартную функцию в нужный момент?
В общем, как ни крути тут, либо ты фантазер либо ты мега-архитектор.
Re[10]: Аморально ли требовать алгоритмы на архитектора
N>Ничего тебе не ясно. Я буду использовать подходящий алгоритм. А знать, что скрывается за стандартными сортам всё равно надо, ведь всегда могут попасться данные, которые могут сильно замедлить ту же быструю сортировку.
Могут и попасться. Наверняка, это случается один раз в триллион лет. Естественно, несмотря на то, что стандарт библиотеки не гарантирует хорошую реализацию quick-sort, все часто используемые реализации библиотеки имеют хорошую реализацию. И не использовать этот библиотечный метод — это самого себя перемудрить.
Re[11]: Аморально ли требовать алгоритмы на архитектора
N>>Ничего тебе не ясно. Я буду использовать подходящий алгоритм. А знать, что скрывается за стандартными сортам всё равно надо, ведь всегда могут попасться данные, которые могут сильно замедлить ту же быструю сортировку.
DB>Могут и попасться. Наверняка, это случается один раз в триллион лет. Естественно, несмотря на то, что стандарт библиотеки не гарантирует хорошую реализацию quick-sort, все часто используемые реализации библиотеки имеют хорошую реализацию. И не использовать этот библиотечный метод — это самого себя перемудрить.
Да он фантазирует тут. Разумеется он будет использовать стандартную функцию.
Re[12]: Аморально ли требовать алгоритмы на архитектора
ОК>Да он фантазирует тут. Разумеется он будет использовать стандартную функцию.
Здесь скорее проблема в том, что плохое знание зачастую хуже незнания. Та же быстрая сортировка. Кто не знает ничего, будет использовать библиотечную реализацию и никогда не будет иметь никаких проблем. Тот, кто знает тему плохо, будет считать, что существую данные, на которых библиотечная реализация qSort работает медленно и для критичных моментов будет реализовывать какой-то велосипед, который наверняка окажется ещё медленнее и ещё багованнее.
Re[11]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Олег К., Вы писали:
ОК>То есть ты все-таки пишешь свою версию сортировки, ака изобретение велосипеда, вместо того чтобы использовать стандартную функцию?
Я не буду использовать свою, практически 100%, что найду уже существующую реализацию необходимого. Также как с аллокаторами, например.
ОК>Ты, чувак, теоретизируешь или ты уже писал свои функции сортировки вместо того чтобы использовать в коде стандартную функцию в нужный момент? ОК>В общем, как ни крути тут, либо ты фантазер либо ты мега-архитектор.
Не писал, но сторонние использовал. Как раз потому, что знал, что внутри стандартной сортировки была не быстрая. Ты хоть в исходники той же std::sort заглядывал?
Re[11]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, De-Bill, Вы писали:
DB>Могут и попасться. Наверняка, это случается один раз в триллион лет. Естественно, несмотря на то, что стандарт библиотеки не гарантирует хорошую реализацию quick-sort, все часто используемые реализации библиотеки имеют хорошую реализацию. И не использовать этот библиотечный метод — это самого себя перемудрить.
Я как раз говорю, что для твоих данных при вызове std::sort может вызываться не быстрая сортировка, а другая. НИКТО не говорит, что в stl используется быстрая сортировка, по факту так ЧАСТО и происходит. Это просто функция-диспетчер, которая вызывает один из алгоритмов, в зависимости от своих внутренних соображений. Но для конкретных данных может быть больше пригоден другой. Вот об этом я и говорю, что надо знать устройство stl и то, как работают сортировки.
С другой стороны, всегда можно выбирать между вариантами: std::list + std::list::sort, std::vector + std::sort, std::map, std::unordered_map. И этот выбор можно и нужно делать до того, как писать код.
Re[11]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, UVV, Вы писали:
UVV>И будешь ты его использовать, разумеется, сразу, а не потом, когда выяснишь, что твой qsort узкое место в производительности...
Может быть и да в том момент, когда делаю выбор между, например std::map и отсортированным вектором с поиском по нему. Почему нет?
Re[12]: Аморально ли требовать алгоритмы на архитектора
ОК>>То есть ты все-таки пишешь свою версию сортировки, ака изобретение велосипеда, вместо того чтобы использовать стандартную функцию?
N>Я не буду использовать свою, практически 100%, что найду уже существующую реализацию необходимого. Также как с аллокаторами, например.
Ты заканчивай предложения точками. Непонятно порой читать что к чему.
Ну то есть не ты напишешь, так кто-то еще? Пойнт в том, что это опять будет изобретенный велосипед. Не тобой так кем-то другим. А ты, как мега-архитектор, опять притащишь нестандартный код либо еще одну библиотеку.
ОК>>Ты, чувак, теоретизируешь или ты уже писал свои функции сортировки вместо того чтобы использовать в коде стандартную функцию в нужный момент? ОК>>В общем, как ни крути тут, либо ты фантазер либо ты мега-архитектор.
N>Не писал, но сторонние использовал. Как раз потому, что знал, что внутри стандартной сортировки была не быстрая. Ты хоть в исходники той же std::sort заглядывал?
Заглядывал и что? Сколько ты процентов сэкономил используя нестандартную функцию? Или это все делалось ради одной десятой наносекунды?
Re[12]: Аморально ли требовать алгоритмы на архитектора
UVV>>И будешь ты его использовать, разумеется, сразу, а не потом, когда выяснишь, что твой qsort узкое место в производительности...
N>Может быть и да в том момент, когда делаю выбор между, например std::map и отсортированным вектором с поиском по нему. Почему нет?
Это уже другой сценарий! Сравни: выбор между стандартными контейнарами и алгоритмом версус сказать что стандартный алгоритм плохо реализован и написать свой.
Плохой из тебя архитектор если ты разницу не видишь.
Re[12]: Аморально ли требовать алгоритмы на архитектора
DB>>Могут и попасться. Наверняка, это случается один раз в триллион лет. Естественно, несмотря на то, что стандарт библиотеки не гарантирует хорошую реализацию quick-sort, все часто используемые реализации библиотеки имеют хорошую реализацию. И не использовать этот библиотечный метод — это самого себя перемудрить.
N>Я как раз говорю, что для твоих данных при вызове std::sort может вызываться не быстрая сортировка, а другая. НИКТО не говорит, что в stl используется быстрая сортировка, по факту так ЧАСТО и происходит. Это просто функция-диспетчер, которая вызывает один из алгоритмов, в зависимости от своих внутренних соображений. Но для конкретных данных может быть больше пригоден другой. Вот об этом я и говорю, что надо знать устройство stl и то, как работают сортировки.
Да ты тут опять абстрактно говоришь что может быть.
N>С другой стороны, всегда можно выбирать между вариантами: std::list + std::list::sort, std::vector + std::sort, std::map, std::unordered_map. И этот выбор можно и нужно делать до того, как писать код.
Это другой сценарий! Выбрать один из стандартных контейнеров версус сказать, что медленно работает и реализовать свой велосипед. Ты уже в сторону уходишь, чувак.
Re[12]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Олег К., Вы писали:
ОК>Ты заканчивай предложения точками. Непонятно порой читать что к чему.
Заканчиваю. Монитор у тебя заляпан, может?
ОК>Ну то есть не ты напишешь, так кто-то еще? Пойнт в том, что это опять будет изобретенный велосипед. Не тобой так кем-то другим. А ты, как мега-архитектор, опять притащишь нестандартный код либо еще одну библиотеку.
Я ещё boost использую и много чего ещё. Да, оно было написано кем-то другим. Это преступление?!!
N>>Не писал, но сторонние использовал. Как раз потому, что знал, что внутри стандартной сортировки была не быстрая. Ты хоть в исходники той же std::sort заглядывал? ОК>Заглядывал и что? Сколько ты процентов сэкономил используя нестандартную функцию? Или это все делалось ради одной десятой наносекунды?
Много. У меня недавно был топик в алгоритмах, где я смог уйти от задачи O(n^3) к O(N^2 * log(M)). И это дало охрененное ускорение. Представь, что может случиться, когда у тебя сортировка, вдруг, вместо O(logN) даёт O(n^2). Для меня это было пиз..ц как медленно. Кстати, зачем, по-твоему, существуют различные алгоритмы сортировки? Почему эту тему не закрыли после диссертации Сэджвика? Подумай над этим на досуге.
Re[13]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Олег К., Вы писали:
ОК>Да ты тут опять абстрактно говоришь что может быть.
Не абстрактно, я тебе уже 100 раз сказал, что std::qsort — это не быстрая сортировка и цитату привёл. Зачем, как считаешь, не используют внутри именно быструю сортировку? Зачем это описывают в документации? Зачем вообще занимаются сортировками, когда идеал уже есть в std?
N>>С другой стороны, всегда можно выбирать между вариантами: std::list + std::list::sort, std::vector + std::sort, std::map, std::unordered_map. И этот выбор можно и нужно делать до того, как писать код. ОК>Это другой сценарий! Выбрать один из стандартных контейнеров версус сказать, что медленно работает и реализовать свой велосипед. Ты уже в сторону уходишь, чувак.
Нет, это часть того же сценария. Зная, как изначально отсортированы данные, что это за данные, подходит ли in-place в конце концов? Нюансов много. Понятно, что все сразу смотрят на std::sort, но мало кто тут же пишет код. Обычно думают сперва.