Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 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 назад.
Д.Кнут. Том третий?
PNG сложный? Когда мне надо было ручками в HEX-редакторе поправить png-картинку, я открыл официальную спецификацию и через пол часа сделал то, что мне было нужно. Да, я не разобрался до конца, и не смогу написать сходу (ен|де)кодер png, но я понимаю его структуру и заложенную в формат идею.
Тот же gzip мне показался сложнее.
многие алгоритмы написаны так сложно
И поэтому вы прочитали эту статью, и теперь знаете, как сортировать пузырьком? Ну я рад за вас, правда. Только знаете что? Вам это все равно не пригодится, потому что пузырьковая сортировка на практике бесполезна. При чем автор честно написал, что ни один из рассмотренных алгоритмов на практике не применяется. Потому что все они плохие. Ну и в итоге, ему допустим было интересно описать свое понимание, а нам-то с чего быть добрыми, читая в сотый раз одно и тоже, да еще и неправильно описанное? Ну кстати, за этот пост автору поставили аж 12 плюсов, как по мне, это еще и много, но 12 добрых нашлось.
А зачем Кнута? Я кстати Кнута не советовал, и вам (как вы себя описываете) точно не посоветую. Есть много более простых книжек, с тех пор понаписали. Писать тексты для начинающих гораздо сложнее, чем для опытных. И я вот не верю, что у кого-то получится первую или даже вторую статью про давно изжеванную тему написать лучше, чем сто раз написано в одной из хороших книжек. Только мусора в поиске больше будет.
Ну да, все правда. И что это меняет, с учетом того факта, что данный текст бесполезен?
Чуть ниже упомянутый простой и понятый Кормен это 1989 год. 34 года книжке. Все на самом деле уже написано.
Претензии к непонимаю базовых cs терминов необоснованны. Сортировки всегда преподаются после них. Не надо пытаться учить дифуры, до обычной алгебры.
Перед словом карт стоит добавить слово игральных и все станет понятно сразу. Ну такое. В переиздание наверно стоит добавить и не более того. А пример отличный. Как обычный человек сам изобретает и использует алгоритм про который идет речь.
Ресурсы это важно. Без упоминания и рассмотрения что сколько стоит это всё не имеет смысла. Пузырек отлично работает.
В книжках это обычно более системно все описано, и в определенном смысле проще, вводится аппарат построения различных алгоритмов и доказательства корректности . По моему вкусу, как по простоте изложению, так и обхвату тематики, Кормен просто отличный. Сам его читал в начале нулевых, когда только учился.
CCITT Group 4
Это что-то из вселенной факсимиле?
Я в 1996 году нашел описание алгоритма LZW в виде текстового файла на какой-то файлопомойке. Настолько четкое, что сделал по нему свое сжатие.
del
При редактировании файла нет необходимости держать весь файл в оперативной памяти. Каждой строке присваивается порядковый номер, и после внесения изменений достаточно обновленные строки отсортировать и вставить в сам файл.
Замечу тут, что нельзя просто "вставить в файл" отредактированные строки зная их номера. В файл мы вставляем данные по смещению а не номеру строки, да и вообще вставка в файл затирает данные которые были в том месте куда мы вставляли данные. Придется перезаписывать весь файл целиком, а значит все равно придется весь файл загрузить в оперативную память ( хотя не обязательно сразу весь целиком, можно конечно читать/писать его частями ).
Сортировку вставками можно ускорить, кэесли использовать бинарный поиск
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
[По полочкам] Алгоритмы сортировок. Часть 1