поэтому правильное утверждение «существует много алгоритмов с худшим случаем NlogN» и более того поразрядные сортировки работают стабильно на любых данных с O(N).
Я был неправ, а Вы правы в отношении худшей сложности. Например, вот — сортировка интросорт, имеет среднюю и наихудшую производительность N log N.
Только мне совершенно непонятно, почему Вы упоминаете сортировку Шелла в своей рекомедации — далеко не самый лучший алгоритм с точки зрения вычислительной сложности.
Давайте я еще раз повторю свою мысль — лучшее время сортировки Шелла по вычислительной сложности уступает среднему времени быстрой сортировки. Это математически достоверный результат, а не «как показывают мои тесты». Вот Вам пруф о том, что средний результат сортировки Шела хуже N log N.
И стандартом С++ прямо запрещено использовать быструю сортировку, так как std::sort всегда должна быть по порядку NlogN.
Гм. Тут, как мне кажется, Вы неверно выразились. Позвольте сделать утверждение: «Не существует алгоритма сортировки, который имеет худшую сложность NlogN». Наверное, в стандартах C++ прописано что-то иное.
Что касается сортировки Шелла, то там лучшее время N log2 N (где двоечка — это квадрат логарифма), в то время как у быстрой среднее время N log N. Худшее время у них одинаковое N2 (квадрат). Источники — раз и два.
Поэтому можно сколько угодно написать «как показывают тесты ...», но математику никто не отменял и сути проистекающих процессов это не изменит.
Теперь что касается сортировки миллионов и миллиардов чисел. Можно ли привести пример прикладной области, в которой регулярно приходится сортировать такие большие наборы чисел и причем каждые раз разные? Конечно, мы можем пробовать конкретные реализации алгоритмов на прочность, как японскую бензопилу, из спортивного интереса. Но в реальной жизни это скорее всего означает большую ошибку проектирования.
Продакшен — учетные ментовские задачи уровня райотдела и города (люди, оружие, прописка, загранпаспорта и т.д.). Написано, как Вы понимаете, очень давно по современным меркам. Реализация алгоритма изначально — классическая рекурсивная, по Кнуту. Потом добавили вариацию нерекурсивную. В таком виде эта штука 30 лет и работает :) Естественно, без зависаний :)
30 лет (в 1989 году) назад написал на турбопаскале свой первый профессиональный код — библиотеку сортировок. Алгоритмы черпал из третьего тома Кнута — быстрая, двойными включениями, прямым выбором, пузырьковая, шейкер, пирамидальная.
В 1991 году в рамках диплома пытался создать адаптивную (с точки зрения выбора алгоритма сортировки) систему для прикладных задач. Но все это так и осталось дипломом — в продакте используется исключительно быстрая сортировка. Кстати и по сей день — что является предметом моей гордости :)
Увы, Вы правы. Поэтому работа на удаленке (а ведь про нее говорим, правда?) имеет свои неоспоримые преимущества. Если мне придет в голову менять квартиру в Краснодаре, то я обязательно буду рассматривать варианты возле парка Галицкого. И количество полос меня не остановит — от парка до Северной 900м — неплохая прогулка.
Гм. Когда меня «приглашают» поучаствовать в спасении мира, я начинаю искать подвох и деньги.
С деньгами все понятно — некакая американская фермерша, имея земли низкого качества для растениеводства, приспособила их для животноводства.
Далее фермерша вступила в войну «остроконечников» и «тупоконечников», создав информационную шумиху вокруг своей фермы. В результате фермерша получила рекламу и новое направления бизнеса — экотуризм в свою ферму. «Посмотрите, какие прекрасные жучки в какашках наших коров! В конце экскурсии можно будет приобрести мясо в нашей эколавке!»
Я не просто так пример Москвы привёл, ограничения позволяют заткнуть проблему плохой связности, но временно, без улучшения связности и пропускной способности не выходит, по крайней мере для всех, если у города транспортная сеть на 0.5 миллиона а живёт 1.5, то при любых ограничениях будут проблемы
Я все прекрасно понимаю — дороги нужно строить, связность повышать, пропускную способность увеличивать. Все это декларации, которые в принципе нереализуемы в текущих политико-экономических условиях.
А вот задача снизить трафик за счет драконовских ограничений — реализуема, так как денег и сложных усилий не требует. Мы, будучи ИТ-шниками, это прекрасно понимаем (Mikrotik Queue Trees — Rulez Forever!).
Конечно, у нас везде особый путь. Как я уже писал выше — особенность национального менталитета.
Всё, о чем Вы пишете сейчас — первый раз было успешно решено в Чикаго в 40-х годах прошлого века. Но нам очень сложно изучать зарубежный опыт — очевидные (непопулярные) решения режут слух, как само слово «азы».
Я бы понял, если бы попытались применить эти методы на практике, что-то там не пошло и вот тогда можно говорить про краснодарскую специфику и выдумывать что-то особенное.
Наоборот, применяли и вполне успешно. Помните, например, на Северной делали выделенку год или два назад? У меня резко сократилось время в пути — с 60-70 минут до 40-50 минут. Автомобилисты с персональными автомобилями два часа стояли в пробках. Еще чуть-чуть — и они бы пересели на общественный траснпорт. Город бы вздохнул спокойно.
Дальше пошла цепочка событий — отмена выделенки, нарастание проблем, приглашение за многие миллионы специалистов из Москвы, спецы долго изучают ситуацию и «Здрасте Вам снова!» — рекомендуют выделенку, еще более масштабную, чем была раньше. Самый важный участок Северной пока не при делах, но это временно. Выделенка там будет, только позже и мы заплатили за это большие деньги.
На мой взгляд, комментарии к статье позволяют получить представление о Краснодаре для удаленщика.
И Вы правы — на открытом пространстве вполне можно посидеть с ноутбуком без риска запылиться.
Я правда не понимаю — зачем? Работа — это большой стол, два монитора, кондей, кружка кофе и холодильник неподалеку. Поработал — пошел на это самое открытое пространство. Там девушки ходют. Красивые. А ноутбук будет только мешать :)
Гм. Я ИТ-шник, работающий на удаленке в Краснодаре. Мне абсолютно до лампочки вопросы «подъезда к концам этой улицы» и широко обсуждаемая «проблема Лосево на м4», про которую я ничего не слышал. Уверен, что и любому другому удаленщику тоже.
Сегодня пасмурно. На термометре дома +25. В десять утра.
Мне пофиг, сколько там показывает термометр в автомобиле, установленный под жарким капотом. Я живу в квартире на 5-ом этаже 14-этажного кирпичного дома. Где толстые стены, кондей и комфорт.
Я — ИТ-шник, большую часть работы делающий через удаленку. Я выбрал путь комфорта, а не путь терзаний в пробках. Мне так удобно. Несмотря на Краснодар, пробки и все такое.
PS
В офис я все-таки езжу. Вот сейчас, когда основная волна схлынула, пойду, сяду на автобус №2. Если повезет, то с кондеем. И вполне себе нормально поеду в центр.
Совершенно верно. Это очень плохо. Построить еще мосты — это очень дорого, сложно и деньги украдут по пути. Гораздо проще уменьшить трафик по мостам в два раза, «подрезая» автолюбителей финансово. Так и деньги постоянные «текут куда надо» и общественному транспорту полегче.
Но мы скатываемся из проблематики статьи «Краснодар — город для ИТ-удаленки» к проблематике города. Полагаю, не стоит комментарии к статьн превращать в форум для обсуждения проблем города?
Вот это особенность нашего менталитета — и трафик у нас особенный и автомобилисты особенные и проблема пробок такая, что нигде подобной в мире нет. Никто не посмотрит на то, как (успешно) решаются проблемы в других местах. Мы будем искать свое собственное, оригинальное решение проблемы.
Вся надежда на жадность властей — если люди у нас «вторая нефть», то в мегаполисах автолюбителей можно сделать «третьей» — задирать цены на парковках, штрафовать за неправильную парковку и проезд по выделенке и т.д.
Ошибаетесь: с одной полосой все очень просто — запрещаем там проезд для всех, кроме общественного и спецтранспорта (то есть пропускаем только важный трафик). Это было придумано 70 лет назад и доказало свою эффективность. Главное — создать для простых автолюбителей массу неудоств для поездки в центр города, включая финансовые.
Я был неправ, а Вы правы в отношении худшей сложности. Например, вот — сортировка интросорт, имеет среднюю и наихудшую производительность N log N.
Только мне совершенно непонятно, почему Вы упоминаете сортировку Шелла в своей рекомедации — далеко не самый лучший алгоритм с точки зрения вычислительной сложности.
То есть реальных примеров привести не можете? Обсуждаем сферического коня в вакууме?
Давайте я еще раз повторю свою мысль — лучшее время сортировки Шелла по вычислительной сложности уступает среднему времени быстрой сортировки. Это математически достоверный результат, а не «как показывают мои тесты». Вот Вам пруф о том, что средний результат сортировки Шела хуже N log N.
Гм. Тут, как мне кажется, Вы неверно выразились. Позвольте сделать утверждение: «Не существует алгоритма сортировки, который имеет худшую сложность NlogN». Наверное, в стандартах C++ прописано что-то иное.
Что касается сортировки Шелла, то там лучшее время N log2 N (где двоечка — это квадрат логарифма), в то время как у быстрой среднее время N log N. Худшее время у них одинаковое N2 (квадрат). Источники — раз и два.
Поэтому можно сколько угодно написать «как показывают тесты ...», но математику никто не отменял и сути проистекающих процессов это не изменит.
Теперь что касается сортировки миллионов и миллиардов чисел. Можно ли привести пример прикладной области, в которой регулярно приходится сортировать такие большие наборы чисел и причем каждые раз разные? Конечно, мы можем пробовать конкретные реализации алгоритмов на прочность, как японскую бензопилу, из спортивного интереса. Но в реальной жизни это скорее всего означает большую ошибку проектирования.
В 1991 году в рамках диплома пытался создать адаптивную (с точки зрения выбора алгоритма сортировки) систему для прикладных задач. Но все это так и осталось дипломом — в продакте используется исключительно быстрая сортировка. Кстати и по сей день — что является предметом моей гордости :)
С деньгами все понятно — некакая американская фермерша, имея земли низкого качества для растениеводства, приспособила их для животноводства.
Далее фермерша вступила в войну «остроконечников» и «тупоконечников», создав информационную шумиху вокруг своей фермы. В результате фермерша получила рекламу и новое направления бизнеса — экотуризм в свою ферму. «Посмотрите, какие прекрасные жучки в какашках наших коров! В конце экскурсии можно будет приобрести мясо в нашей эколавке!»
Нам-то зачем эта война?
Я все прекрасно понимаю — дороги нужно строить, связность повышать, пропускную способность увеличивать. Все это декларации, которые в принципе нереализуемы в текущих политико-экономических условиях.
А вот задача снизить трафик за счет драконовских ограничений — реализуема, так как денег и сложных усилий не требует. Мы, будучи ИТ-шниками, это прекрасно понимаем (Mikrotik Queue Trees — Rulez Forever!).
Всё, о чем Вы пишете сейчас — первый раз было успешно решено в Чикаго в 40-х годах прошлого века. Но нам очень сложно изучать зарубежный опыт — очевидные (непопулярные) решения режут слух, как само слово «азы».
Я бы понял, если бы попытались применить эти методы на практике, что-то там не пошло и вот тогда можно говорить про краснодарскую специфику и выдумывать что-то особенное.
Наоборот, применяли и вполне успешно. Помните, например, на Северной делали выделенку год или два назад? У меня резко сократилось время в пути — с 60-70 минут до 40-50 минут. Автомобилисты с персональными автомобилями два часа стояли в пробках. Еще чуть-чуть — и они бы пересели на общественный траснпорт. Город бы вздохнул спокойно.
Дальше пошла цепочка событий — отмена выделенки, нарастание проблем, приглашение за многие миллионы специалистов из Москвы, спецы долго изучают ситуацию и «Здрасте Вам снова!» — рекомендуют выделенку, еще более масштабную, чем была раньше. Самый важный участок Северной пока не при делах, но это временно. Выделенка там будет, только позже и мы заплатили за это большие деньги.
И Вы правы — на открытом пространстве вполне можно посидеть с ноутбуком без риска запылиться.
Я правда не понимаю — зачем? Работа — это большой стол, два монитора, кондей, кружка кофе и холодильник неподалеку. Поработал — пошел на это самое открытое пространство. Там девушки ходют. Красивые. А ноутбук будет только мешать :)
Тема это статьи немного другая.
Мне пофиг, сколько там показывает термометр в автомобиле, установленный под жарким капотом. Я живу в квартире на 5-ом этаже 14-этажного кирпичного дома. Где толстые стены, кондей и комфорт.
Я — ИТ-шник, большую часть работы делающий через удаленку. Я выбрал путь комфорта, а не путь терзаний в пробках. Мне так удобно. Несмотря на Краснодар, пробки и все такое.
PS
В офис я все-таки езжу. Вот сейчас, когда основная волна схлынула, пойду, сяду на автобус №2. Если повезет, то с кондеем. И вполне себе нормально поеду в центр.
Но мы скатываемся из проблематики статьи «Краснодар — город для ИТ-удаленки» к проблематике города. Полагаю, не стоит комментарии к статьн превращать в форум для обсуждения проблем города?
Проблема не только в узких улицах — наш город на первом месте по количеству автомобилей на душу населения (437), опережая Москву (417).
Вся надежда на жадность властей — если люди у нас «вторая нефть», то в мегаполисах автолюбителей можно сделать «третьей» — задирать цены на парковках, штрафовать за неправильную парковку и проезд по выделенке и т.д.
Это азы урбанистики и городологии.