Здравствуйте, Олег К., Вы писали:
ОК>Ну так может ты просветишь нас какая сортировка используется когда не используется быстрая? Нам это тоже полезно будет знать, но ты почему-то умолчал об этом.
Конкретно в том случае — никакая. Была функция для определения площади пересечения двух прямоугольников, которая вызывалась очень много раз. В этой функции дважды вызывалась std::sort: для x и y координат. И очень часто так получалось, что данные были обратно упорядочены и сортировка тормозила. Но я убрал сортировку совсем и функцию переписал без неё. Вот и все дела.
Вполне допускаю, что сейчас эта функция могла и не оказаться в числе медленных, как раз потому, что для таких небольших массивов быстрая сортировка внутри std::sort не используется вообще.
Re[16]: Аморально ли требовать алгоритмы на архитектора
L>Идея сортировать связанный список уже сама по себе намекает...
Не совсем понял, на что именно намекает? В-принципе, нет ничего плохого в том, чтобы отсортировать список. Асимптотика O(n log n) в худшем случае. Но, скорее всего, будет эффективнее скопировать список в массив, отсортировать массив, и преобразовать обратно в список, если это возможно.
Re[17]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, De-Bill, Вы писали:
L>>Идея сортировать связанный список уже сама по себе намекает...
DB>Не совсем понял, на что именно намекает?
Намекает на серьезный косяк. Причем, по моим наблюдениям, косяк типа "лечим простуду зеленкой", когда факап отрастает из вкорне неправильного подхода к решению задачи, нежели реализации алгоритмов.
DB>В-принципе, нет ничего плохого в том, чтобы отсортировать список.
Если это нужно один раз за лайфтам процесса и никого это не напрягает, может быть.
DB>Асимптотика O(n log n) в худшем случае. Но, скорее всего, будет эффективнее скопировать список в массив, отсортировать массив, и преобразовать обратно в список, если это возможно.
Или подумать, откуда взялся список, почему именно список и зачем нужно сортировать.
Здравствуйте, landerhigh, Вы писали:
DB>>Сортировками занимаются потому что разные структуры данных невозможно сортировать одним и тем же способом. Т.е. сначала принимается решение на счёт использования структур данных, а только потом решение о способе упорядочивания. Например, если мы можем сортировать массив с помощью быстрой сортировки, то сортировать связанный список так невозможно.
L>Идея сортировать связанный список уже сама по себе намекает...
На незнание merge sort?
Re: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Тёмчик, Вы писали:
Тё>Аморально ли проверять знание алгоритмов, если на рассматриваемую позицию человек не будет их писать? Ведь задача архитектора- иметь высокоуровневое видение продукта, каким он будет и выбор, какие фреймворки использовать.
На лицо явное непонимание обязанностей архитекторов в больших конторах. В маленьких они нафиг не нужны. Код архитекторы не пишут, алгоритмы не применяют, высокоуровневое видение продукта — это как заставить 500+ стратегических приложений работать вместе, а для этого нужно строчить стандарты и со всеми договариваться.
P.S. Умиляют программисты, заявляющие что они "архитекторы" в CV.
Re[2]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, 0x7be, Вы писали:
Тё>>Аморально ли проверять знание алгоритмов, если на рассматриваемую позицию человек не будет их писать? Ведь задача архитектора- иметь высокоуровневое видение продукта, каким он будет и выбор, какие фреймворки использовать. Тё>>Дискас. 0>Аморально требовать те знания, которые не будут востребованы на этой позиции.
Да нет там ничего аморального в любом случае, можно спрашивать всё из computer science. Аморально — это когда требуют стоять на одной ноге, или сдать денег на благотворительность, или сиськи показать.
0>Если в данном конкретном месте роль архитектора такая, что ему эти знания нужны — требовать надо.
Ну, это как бы архитектор думает в проекте про структуру данных — как часто будет использоваться, сортироваться, расти/уменьшаться, если он не будет представлять как алгоритмы работают — мне было б страшно с таким архитектором работать.
Правда, по мне как то несколько странно архитектора тестировать задачками — их или лучше самим растить, или переманивать, но в обоих случаях должно уже быть ясно с кем имеем дело и без задачек.
Re[11]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Олег К., Вы писали:
ОК>>>Видишь ли, я верю что ты можешь писать код на работе, но в данном случае это был больше вопрос не на написать а на помнишь ли ты как это работает изнутри. Такое быстро забывается после учебы. Поэтому я и отказываюсь верить что ты помнишь быструю сортировку.
G>>Забывается то, что ты не понял. В универе, как и в школе, часто пытаются вбить в голову факты, вместо объяснения принципов. G>>Чтобы понять принципы построения алгоритмов на основе рекурсии я прочитал немало книг, поэтому для меня не проблема написать быстрою сортировку.
ОК>Забывается то с чем дела не имеешь напостоянку.
Я не имею на постоянку дел с быстрой сортировкой, но все равно могу её написать.
Re[3]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Тёмчик, Вы писали:
KP>>Аморально не знать основных алгоритмов и структур данных если ты позиционируешь себя как архитектор Тё>Смотря что считать основными алгоритмами. Задачки про гномиков, или про обход лабиринта- это основные алгоритмы?
Джаззер был прав, если ты программист/архитект, то должен помнить про алгоритмы и раз в 1-2 года пролистывать кормена и/или сэджвика. От себя добавлю, не лишним будет почитывание прикладного матана и изучения чего-то нового из этой сферы. С гномиками можно справится если поддерживаешь мозги в тонусе.
Sic luceat lux!
Re[9]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Олег К., Вы писали:
ОК>Ты, чувак, видишь разницу между знать что есть такие-то структуры данных и такие-то алгоритмы версус того чтобы требовать их имплементацию?
Ты сам придумал что надо спрашивать имплементацию и продолжаешь с этим героически спорить.
G>>У меня был случай — надо было написать функцию, которая превращает IEnumerable<T> в IEnumerable<IEnumerable<T>>, нарезая входную последовательность на блоки по определенному условию, зависящему от нескольких предыдущих элементов. G>>Я потом эту задачу на собеседовании давал. Код менее чем на 20 строк. Из 10 кандидатов справилось два. При этом все прекрасно знали linq, yield, как устроен IEnumerable и то, что енумератор — value type. ОК>Что-то ты переусложняешь все.
Что именно?
Re[12]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, rumit7, Вы писали:
R>Здравствуйте, gandjustas, Вы писали:
G>>Я не имею на постоянку дел с быстрой сортировкой, но все равно могу её написать.
R>"могу её написать" и "могу её написать без ошибок" две большие разницы, в данном случае Вам намекают про второй случай, а Вы упорно давите на первое))
Написать на бумаге\на форуме и на компьютере — две большие разницы, я говорю про первый случай, а все упорно делают вид, что это второй
Re[6]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Олег К., Вы писали:
ОК>Тут вопрос в другом. Помнит он этот квиксорт как он говорит или все-таки полез в википедию?
Не отпускает до сих пор?
ОК>Ну и еще тут один момент. Сэджвик защитил диссертацию по квиксорту, а тут некоторые товарищи утверждают что напишут код слету да еще и на интервью. Поражаюсь ихней самоуверенности.
Ты плохо представляешь суть диссертации по computer science. Диссертация заключается не в написании кода, а в формальном доказательстве свойств кода.
Докажи формально, что выбор срединного элемента в качестве опорного лучше чем выбор первого. А если выбирать случайный элемент в качестве опорного, как это скажется на свойствах квиксорта?
Re: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Тёмчик, Вы писали: Тё>Аморально ли проверять знание алгоритмов, если на рассматриваемую позицию человек не будет их писать? Ведь задача архитектора- иметь высокоуровневое видение продукта, каким он будет и выбор, какие фреймворки использовать.
Иногда ты очень хорошо накидываешь, смотрите как кто-то пыхнул в личке!!! Я бы сказал что просто взрыв какой-то!!!
мат я запипал
"Ну, раз уж алгоритмические вопросы заставляют таким факелом полыхать кандидатов вроде тебя, такие вопросы просто необходимо задавать для грамотного отбора"
Я тебе уже говорил, что ты — ДЕБИЛ? Могу еще раз повторить, то ты — ДЕБИЛ! Нет никакой необходимости помнить многие алгоритмы. Напиши, к примеру, сходу алгоритм push_heap, который добавляет элемент в кучу, не заглядывая в книгу. Кому это надо помнить?!
А чтобы ты, ДЕБИЛ, заткнулся, то я тебе скажу, что это именно я предложил комитету стандартизации по C++ внести изменения относительно этого алгоритма так как имеет место неоднозначность вставки нового элемента. Но мне совершенно не нужно помнить этот алгоритм. Когда понадобиться, я смогу освежить свою память.
Слушай, шел бы ты ПИИИИИП от обсуждения программирования, так как ты — НИКТО, и зовут тебя — НИКАК. Я посмотрел на Stackoverflow, так там такого kaa.python и в помине нет. Что ты лезешь ЧМОШНИК со своими куриными мозгами в калашный ряд?!
тут, походу, веселуха продолжается
"смотрите как Олежка пыхнул в личке" — Слушай, ДЕБИЛ, я к этому "Олежке" никакого отношения не имею. Я вообще не принимаю участие на этом форуме. Я — сторонний читатель.. Просто уже никаких сил нет читать твою ДЕБИЛЬНУЮ ЧУШЬ.
О себе. Автор нескольких предложений по изменению стандарта C++, которые были включены в стандарт. Имею золотые знаки отличия по C и C++ на Stackoverflow. Репутация составляет более 100 тысяч баллов. Это все я пишу, чтобы до твоих куриных мозгов хоть что-то дошло, правда, как показывает жизнь, таких ДЕБИЛОВ чему-либо не научишь. Тебе уже сказано было: "Заткнись!" Глядишь, и за умного сойдешь.
Здравствуйте, kaa.python, Вы писали:
KP>Иногда ты очень хорошо накидываешь, смотрите как Олежка пыхнул в личке!!! Я бы сказал что просто взрыв какой-то!!!
Если это личная переписка, то ты как минимум не прав выкладывая её.
Sic luceat lux!
Re[3]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, kaa.python, Вы писали:
KP>Здравствуйте, Kernan, Вы писали:
K>>Если это личная переписка, то ты как минимум не прав выкладывая её.
KP>Я имею полное право делать что угодно с сообщением отправленным лично мне. Тебе привести мнение профессионального юриста на этот счет?
Давай.
Sic luceat lux!
Re[5]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Kernan, Вы писали:
KP>>Я имею полное право делать что угодно с сообщением отправленным лично мне. Тебе привести мнение профессионального юриста на этот счет? K>Давай.
Правила форума не запрещают выкладывать личных сообщений, дисклеймера о конфиденциальности в личном сообщении не было, никакого NDA я не подписывал. Итого: мое сообщение – что хочу, то и делаю с ним. Все остальные сообщения от этого одаренного товарища, если они будут, я планирую выложить к первым двум.
Re[9]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, De-Bill, Вы писали:
DB>Сортировками занимаются потому что разные структуры данных невозможно сортировать одним и тем же способом. Т.е. сначала принимается решение на счёт использования структур данных, а только потом решение о способе упорядочивания. Например, если мы можем сортировать массив с помощью быстрой сортировки, то сортировать связанный список так невозможно.
Почему?
В классике все для массива. Вот краткая запись:
quicksort(A, lo, hi):
p = partition(A, lo, hi)//O(n)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)
Для связанного списка нужно немного модифицировать процедуры.
partition можно реализовать за O(n), соединение двух сортированных частей — O(1).
Асимптотика не поменяется:
quicksort(A):
Aleft, Aright = partition(A)//O(n)
quicksort(Aleft)
quicksort(Aright)
return Aleft.Add(Aright)//O(1)
Гугление даст результат.
Re[7]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Олег К., Вы писали:
ОК>Я не верю тебе но допустим ты хранишь столько хлама у себя в голове. Если ты такой вундеркинд, напиши еще и shell sort заодно. Для тебя это не должно составить труда.
Разделяй и властвуй — это весь хлам, который нужно помнить для решения задачи навроде квиксорта.
Что ты хочешь шеллом проверить, умение писать вложенные циклы на массиве? Это примерно первый месяц первого курса программирования.
