Comments 44
Небольшой лайфхак: если вам нужно отсортировать данные, вызовите функцию из стандартной библиотеки. Она там уже лет шестьдесят.
Это если данные помещаются в памяти
Если не помещаются, то вызовите стандартную функцию сортировки той системы где они у вас лежат. Она там есть с момента создания этой системы.
А если вам нужно что-то посчитать, воспользуйтесь калькулятором:) Зачем учить математику в школе 10 лет?
В общем, с практической точки зрения - конечно да, мы воспользуемся стандартной функцией сортировки, и посчитаем на калькуляторе. Но теория все равно интересна. Понимание того как это работает, понимание концепции вычислительной сложности очень важно даже для использования стандартных алгоритмов. И еще, это вроде простые вещи, но все гениальное просто, и имеет свое очарование.
Этой теории уже примерно 70 лет. Есть любые учебники и любые лекции в общем доступе. Они гораздо лучше всего что я или вы сможем написать. Больше не надо.
А математике наверное несколько тысяч лет:) Но я бы здесь, именно в формате таких вот легких статей, с удовольствием почитал бы про какой нибудь мат.анализ (как повторение давно пройденного и благополучно забытого). Пределы, производные, интегралы, первообразные и вот это всё. С картинками. Желательно с цветными и анимированными, чего точно нет в учебниках.
Если фактических искажений в подаче материала нет, и статья написана в приятном для чтения стиле, то такие статьи вполне имеют право на существование.
А чем вас не устраивает любой учебник или любые записанные лекции? Вы можете выбрать по вкусу, их достаточно прямо вообще любых. Они сделаны профессионалами в образовании и гораздо лучше любых любительских поделок.
Если фактических искажений в подаче материала нет, и статья написана в приятном для чтения стиле, то такие статьи вполне имеют право на существование.
Вы можете со мной не согласиться, но просто повторять то, что уже много десятилетий описано уйму раз и не внести что-нибудь нового - в материале или подачи материала - то тогда зачем вообще писать. Ведь если вам хочется про анализ почитать, вбейте в поиске "матанализ" и весь мир к вашим ногам. И в этой статье нет ни одного момента, который что-нибудь по другому показал в сортировках.
Скажу больше - пояснение очень непонятное. Если я не знал-бы все эти алгоритмы, то из рисунков я ничего-бы не понял.
...вплоть до видео сортировки в виде народных танцев
https://www.youtube.com/watch?v=5JMInXAtnQg&pp=ygUy0LDQu9Cz0L7RgNC40YLQvNGLINGB0L7RgNGC0LjRgNC-0LLQutC4INGC0LDQvdGG0Ys%3D
В стандартной библиотеке еще несколько десятков функций. Почему из них интересна только сортировка?
Большие данные очень часто лежат просто в файлах.И средствами файловой системы данные в них не отсортировать
Вы хотя бы раз реально видели такое? С ними же невозможно работать в таком виде. И значит они бесполезны в таком виде.
Большие данные лежат в БД. Как бы это удивительно для вас не было. И эти БД умеют их сортировать. Я вам точно говорю.
Вы хотя бы раз реально видели такое?
Каждый день вижу.
Большие данные лежат в БД. Как
Нет. Они лежать в виде файлов Parquet. И никакой "стандартной функции сортировки", которая была бы заведомо пригодна для данных размером теребайт 100, например в Hadop, не существует.
С ними же невозможно работать в таком виде.
Неправда. То что вы знаете про базы (и это в общем верно) — это далеко не все что бывает в жизни. Каждую конкретную партицию или таблицу просто сортируют каждый раз при записи. А при чтении пользуются тем, что она отсортирована. Кстати баз это тоже касается — если вы знаете, что у таблицы уже есть порядок, вы можете этим воспользоваться, чтобы не сортировать. И вы (или оптимизатор) этим реально пользуетесь, а не вызываете тупо некую "функцию" сортировки.
А что такое secondary sort в Хадупе тогда?
Сортировка просто существует. В любой бд, по чему угодно. Это же базовая фича. Для бигдаты любая операция не использующая первичный ключ занимает много времени. Это тоже базовое свойство бигдаты.
А зачем вы данные храните не в БД я не знаю. Это странно. Данные нужны чтобы к ним запросы делать, а не чтобы просто лежали.
Я много раз это видел, и много раз видел как в хорошие програмисты пассовали перед задачей, потому что ее нельзя было сделать средствами готовой библиотеки.
Ваша притензия актуальна к "Зачем на собеседовании спрашивать написать алгоритм сортировки, если в языке есть встроеная". Но в контестке чисто теории, ваша претензия мне кажется не уместной.
cat file | sort > sorted_file
может проканать))
Вопрос в понимании, что и как делает инструмент, которым ты пользуешься.
Где-то я это уже читал лет эдак 30-40 назад.
Д.Кнут. Том третий?
Какие все умные и злые )
Кнут это замечательно, но непонятно, как и многие академические материалы они прекрасны, но не всегда. Да-да, я знаю, если я не понимаю что написано в Кнуте, то программирование это не моё, но мне нравится программировать, я с этого не зарабатываю, но многие алгоритмы написаны так сложно и порой совершенно непонятно, что всегда ищешь что-то простое, например чтобы разобраться с LZW и Huffman мне потребовалось почти 20 лет, 15 из которых я искал нужную книжку, но так и не нашел. В Ютубе есть канал, там рассказывают о сложном простыми словами и я смотрю его, например о формате PNG было очень познавательно.
Вот например до сих пор не могу найти нормальное описание CCITT Group 4.
если кому-то интересно, канал о сложном простыми словами с картинками
PNG сложный? Когда мне надо было ручками в HEX-редакторе поправить png-картинку, я открыл официальную спецификацию и через пол часа сделал то, что мне было нужно. Да, я не разобрался до конца, и не смогу написать сходу (ен|де)кодер png, но я понимаю его структуру и заложенную в формат идею.
Тот же gzip мне показался сложнее.
PNG сложный? Когда мне надо было ручками в HEX-редакторе поправить png-картинку, я открыл официальную спецификацию и через пол часа сделал то, что мне было нужно
Вот эта спецификация для меня слишком сложна для освоения. И вы же понимаете что сравнивать вас и меня нет смысла, мы разные, с разными умениями и возможностями. Например я помню что-то не больше 2-3 дней если просто прочитал, если пользуюсь постоянно, то могу быстро вспомнить, но совсем не обязательно что вспомню. Например когда программирую то открытыми держу 4-5 старый своих проектов и подглядываю как и что я делал раньше, потому что я помню только основные наборы языка if, for, while, всё остальное не помню и читаю в гугле как оформляется та или иная команду, смотрю примеры.
Я лучше понимаю материал который идет от сложного к простому, спеки они же сухие и формализованные, я такую информацию понимаю плохо.
но я понимаю его структуру и заложенную в формат идею
В том то и дело что я по спекам этого не вижу. А переработанный материал и поданный иначе - понимаю. Поэтому я Хаффмана очень долго не могу понять пока не попал на какой-то текстовик, еще из FIDO, где псевдографикой было показано и рассказано, буквально на страничку. И теперь я бог хаффмана )
Тот же gzip мне показался сложнее
Читал спеки, такое не осилю. LZW тоже долго гайдов хороших не находил, были абстрактные примеры по которым картина не складывалась.
многие алгоритмы написаны так сложно
И поэтому вы прочитали эту статью, и теперь знаете, как сортировать пузырьком? Ну я рад за вас, правда. Только знаете что? Вам это все равно не пригодится, потому что пузырьковая сортировка на практике бесполезна. При чем автор честно написал, что ни один из рассмотренных алгоритмов на практике не применяется. Потому что все они плохие. Ну и в итоге, ему допустим было интересно описать свое понимание, а нам-то с чего быть добрыми, читая в сотый раз одно и тоже, да еще и неправильно описанное? Ну кстати, за этот пост автору поставили аж 12 плюсов, как по мне, это еще и много, но 12 добрых нашлось.
оценки мало кто может поставить, я вот не мог никогда и не могу и сейчас, поэтому просто читаю. В закладки 54 человека добавили, я например не стал. И я не сказал что статья хорошая, я о том что многие считают что 40-60 лет назад всё придумано и больше ничего писать не нужно. Об этом речь. Мне вон аж в карму минус влепили, за что? За личную неприязнь? У меня просто своё мнение на этот счёт.
Человек написал первую часть, учтёт критику, вторую напишет лучше, во всяком случае постарается.
Ну и Хабр не обязан быть только таким, каким вы себе его представляете, тут уже давно дети читают, которым до понимания Кнута как до Луны пешком.
И не всё должно просто пригождаться, я много вещей читаю для себя, а потом никак не применяю. Кто-то читает романы о любви, кто-то детективы, а я люблю про алгоритмы и программирование.
А зачем Кнута? Я кстати Кнута не советовал, и вам (как вы себя описываете) точно не посоветую. Есть много более простых книжек, с тех пор понаписали. Писать тексты для начинающих гораздо сложнее, чем для опытных. И я вот не верю, что у кого-то получится первую или даже вторую статью про давно изжеванную тему написать лучше, чем сто раз написано в одной из хороших книжек. Только мусора в поиске больше будет.
Чтобы найти простую книжку нужно знать ее название и что она простая, то есть по рекомендации, но рекомендация будет не факт что о простой для вас книжки, она будет простая для советующего. По факту её потом купить нужно (понятно что многое можно скачать за так). Мне периодически советуют книги или сам нахожу что-то, но пока ни разу ничего интересного для меня не встретил.
Вопрос не в том является конкретная статья хорошей, а в отношении других хабровчан к самой идее простых научпоповских статей. Почитайте внимательно комментарии.
(Так как я интересуюсь темой программирования для Atari XL/XE то имею около двух сотен книжек, читаю потихоньку, в 90% это просто хлам, а времени отнимает)
Ну да, все правда. И что это меняет, с учетом того факта, что данный текст бесполезен?
Собственно вот мой комментарий: "Какие все умные и злые ) Кнут это замечательно, но непонятно, как и многие академические материалы они прекрасны, но не всегда"
И он в первую очередь написан в противовес тем кто пишет, что всё написано 40-50-60 лет назад, то есть они априори не приемлют новые статьи. Я не обсуждаю качество этой, хотя и уже написал что она слаба. Читайте внимательнее впредь.
Чуть ниже упомянутый простой и понятый Кормен это 1989 год. 34 года книжке. Все на самом деле уже написано.
Я его читал немного, не считаю эту книгой удобной, можно иногда подглянуть, оценил бы на 3+ (оценка не качества материала, а доступность и понятность изложенного), простой пример (цитата из книги):
1) "сортировка карт" - возможно ошибка перевода, но я представил ГИС систему и какие-то алгоритмы их сортировок. Потом по тексту понял что речь про игральные карты.
2) "в левой руке карты уже упорядочены, правой картой берем из упорядоченных карт карту и вставляем её в "нужное" место" - Кто определяет нужность места? Если карты уже отсортированы, то зачем еще их сортировать. (я не дебил, я понимаю что речь про взятие карты из колоды, надеюсь это так, ведь по тексту написано не так, и вставка в левую руку в соответствии с мастью и значением, но я уже прожженный дед, я уже привык читать такую ахинею, а школьники - нет).
3) "запишем этот алгоритм в виде процедуры" - ладно, допустим слово "алгоритм" многие знают и его описание дано по тексту выше, но слово "процедура" я впервые узнал на втором курсе на занятиях по "Теории и технологии программирования". То есть задолго то прочтения этой книжки я должен уже чему-то сильно научиться, в этом и проблема таких книг.
4) "Массив A[1..n]" - это вообще кто должен понять? Человек должен знать что такое массивы, множества, иметь бэкграунд какой-то по языкам программирования (две точки вы думаете будет понятно что означают?). При этом сортировка и описание алгоритма вставками прекрасно описываются без таких вещей. Я ни разу не видел первокурсника, который понимал бы такое. Когда я учился мы с этим только начинали знакомиться на 2 курсе на высшей математике.
5) "сортируется без дополнительной памяти" - это весьма излишняя информация, тут вопросы сразу и по аппаратной части и по ограничениям памяти и по тому, как сравниваются разные виды сортировок и т.п.
И это я только открыл книгу, это первый алгоритм. Судя по введению всё же авторы рекомендуют его для преподавателей, студентов и программистов и уверен студентов не первого курса, ну или со второго семестра. То есть книжка Кормена не подходит (про псевдокод промолчу вообще, я вырос на книжках 60-70-х и там было страшнее, но всё же он морально устарел).
Претензии к непонимаю базовых cs терминов необоснованны. Сортировки всегда преподаются после них. Не надо пытаться учить дифуры, до обычной алгебры.
Перед словом карт стоит добавить слово игральных и все станет понятно сразу. Ну такое. В переиздание наверно стоит добавить и не более того. А пример отличный. Как обычный человек сам изобретает и использует алгоритм про который идет речь.
Ресурсы это важно. Без упоминания и рассмотрения что сколько стоит это всё не имеет смысла. Пузырек отлично работает.
Сортировки всегда преподаются после них
У вас профдеформация, вы уверены что всё и вся в мире имеет только одну сторону и никак иначе.
Я 6 лет работал в образовательном центре с детьми от 8 лет (по советски если, то вёл кружкИ). Они к концу года писали программы на Делфи без знания ООП, сортировали массивы и рисовали на канвасе и много чего еще. И это я работал с младшими, а такие же занятия были и со старшеклассниками и никто им не давал материал выше того что дают в школе, но при этом они сортировки и поиск подстроки писали сами.
Перед словом карт стоит добавить слово игральных
Это очевидно для нас, а неискушенный читатель напугается и читать перестанет - всё равно непонятно же.
Ресурсы это важно. Без упоминания и рассмотрения что сколько стоит это всё не имеет смысла. Пузырек отлично работает
Никто ТимСорт не преподает детям, там практически всё что O(N^2) изучается без упоминания ресурсов и сложностей, им это вообще не нужно. Задача начального образования - подготовить мозги мыслить определённым образом, а не сделать гуру кодинга и алгоритмов к 10 годам.
В книжках это обычно более системно все описано, и в определенном смысле проще, вводится аппарат построения различных алгоритмов и доказательства корректности . По моему вкусу, как по простоте изложению, так и обхвату тематики, Кормен просто отличный. Сам его читал в начале нулевых, когда только учился.
системный подход в голове формируется в ВУЗе годам к 20, то есть читать такие книжки например в 12-15 лет почти на 100% будет фиаско. Вы слишком оптимистично смотрите на возможности обучающихся, я работаю в ВУЗе почти 15 лет и у меня нет иллюзий по поводу умственных способностей среднестатистического студента. Несомненно есть ВУЗы где обучаются гении, но какой смысл писать книжки только для гениев? Основная масса людей совсем не гении и таковыми никогда не будут.
Посмотрите на статьи в википедии, она уж точно не для гениев написана, я её читаю регулярно, в большинстве своем мои запросы всегда выглядят так "comb sort wiki", читаю там и почти всегда этого достаточно, иногда изучаю ссылки на источники, углубленно могу потом поискать специализированную статью или сайт, часто в выдаче будет Хабр и часто не одна статья. Многие статьи на Хабре весьма хороши (я это знаю), но понять что-то из них мне невозможно. Ищу что-то другое.
И что я точно никогда не скажу - что если какой-то материал изложен и понятен мне, то он будет понятен всем. Люди разные настолько, что это даже иногда до мурашек пробирает. На одни и те же данные может быть абсолютно противоположная реакция и решения. Если вы не работали с детьми, то вы всегда будет опираться на ошибку выжившего.
CCITT Group 4
Это что-то из вселенной факсимиле?
Я в 1996 году нашел описание алгоритма LZW в виде текстового файла на какой-то файлопомойке. Настолько четкое, что сделал по нему свое сжатие.
del
При редактировании файла нет необходимости держать весь файл в оперативной памяти. Каждой строке присваивается порядковый номер, и после внесения изменений достаточно обновленные строки отсортировать и вставить в сам файл.
Замечу тут, что нельзя просто "вставить в файл" отредактированные строки зная их номера. В файл мы вставляем данные по смещению а не номеру строки, да и вообще вставка в файл затирает данные которые были в том месте куда мы вставляли данные. Придется перезаписывать весь файл целиком, а значит все равно придется весь файл загрузить в оперативную память ( хотя не обязательно сразу весь целиком, можно конечно читать/писать его частями ).
еще в эпоху DOS я писал файлы через прерывание, кажется 21h, и всегда занимало как обновление архива RAR на дискетке происходило куда быстрее чем перезапись всего файла, то есть формально 1.4 Мб диска (например файл целиком на весь диск) будут перезаписаны целиком что в варианте с копированием что с обновлением архива, но по факту обновление архива происходило быстрее. Мы тогда сошлись во мнении что RAR работает напрямую с FAT (но это лишь предположение).
Сортировку вставками можно ускорить, кэесли использовать бинарный поиск
[По полочкам] Алгоритмы сортировок. Часть 1