— Ты знаешь как выглядит Идеальный Интерфейс? Это одна кнопка с надписью: «Сделай мне хорошо!»
— Никаких кнопок! Одна надпись: «Тебе уже хорошо!»
На Хабре есть старая традиция: в любой ситуации всегда ругать Хабр. Часто — за дело.
— Ты знаешь как выглядит Идеальный Интерфейс? Это одна кнопка с надписью: «Сделай мне хорошо!»
— Никаких кнопок! Одна надпись: «Тебе уже хорошо!»
На Хабре есть старая традиция: в любой ситуации всегда ругать Хабр. Часто — за дело.
И это не пузырьковая, а нечто гораздо более тупое.
Как-то после обеда, стоя в коридоре с чашечкой кофе, мне пришла в голову мысль. Что ведь для того, чтобы убедиться, что массив отсортирован, надо сделать всего n-1
сравнение. Например, для массива длины 4 таких сравнения будет 3:
if (a0 < a1 < a2 < a3)
А получив утвердительный ответ на этот вопрос, мы можем сразу вернуть готовый массив:
if (a0 < a1 && a1 < a2 && a2 < a3) return [a0, a1, a2, a3];
В прошлый раз мы рассмотрели использование рекурсии на примере возведения в степень. В этот раз мы применим рекурсию для создания алгоритма сортировки слиянием.
В сети легко найти множество вариаций решения данной задачи. Код, который мы рассмотрим в этой статье, будет написан так, чтобы быть максимально простым для понимания начинающих разработчиков.
Освежим в памяти суть сортировки слиянием:
Изначальный массив делится пополам до тех пор, пока длина "половинок" не станет равна 1Читать полностью »
Там около 800 человек круглосуточно занимаются тем, что за 4 секунды должны перевести нечитаемый адрес в странный код, разработанный Siemens в 1990-х годах (надо ли добавлять, что он не интуитивен и сложен?). Поскольку работники используют сотни быстрых сочетаний клавиш, у них даже клавиатуры специальные.
Если меня когда-нибудь спросят о странной организации работ или о плохом UX/UI-дизайне, пожалуй, я покажу им вот этот пост. Посмотрите, как может выглядеть такая деятельность.
Читать полностью »
Представляем вашему вниманию чрезвычайно простой алгоритм сортировки. Может показаться, что он очевидно ошибочен, но мы докажем, что на самом деле он корректен. Мы сравним его с другими простыми алгоритмами сортировки и проанализируем некоторые его любопытные свойства.
Большинству из нас хорошо известны такие простые алгоритмы сортировки, как сортировка пузырьком. По крайней мере, нам так кажется. Оказывались ли вы когда-нибудь в ситуации, когда вам нужно записать псевдокод сортировки пузырьком, и вы осознавали, что он не так прост, как кажется, и с первого раза правильно написать его не удаётся? Нужно внимательно следить за тем, чтобы индексы циклов начинались и заканчивались нужными значениями и не выходили за границы, а также правильно обрабатывать флаговые переменные. Разве не было бы здорово иметь простой алгоритм без всей этой возни? Ниже представлен такой алгоритм, сортирующий массив A из n элементов в неубывающем порядке. Для простоты доказательства массив начинается с 1, то есть имеет элементы A[1],..., A[n].
Алгоритм 1 ICan’tBelieveItCanSort(A[1..n]):
for i = 1 to n do
for j = 1 to n do
if A[i] < A[j] then
swap A[i] and A[j]
Вот, собственно, и всё. Он просто обходит в цикле каждую пару значений (i, j) стандартным способом из двойного цикла for, выполняет сравнение и обмен значениями. Разве можно придумать что-то ещё более простое? Возможно первой реакцией увидевшего этот алгоритм будет что-то типа «это не может быть верно» или «знак неравенства направлен в другую сторону, да и индексы цикла указаны неверно». Но нет, он действительно правильно сортирует в возрастающем порядке.Читать полностью »
Прим. Wunder Fund: не спешите минусовать эту публикацию — её перевода на Хабре ещё не было :)
Это — продолжение моей предыдущей публикации (вот — первая, вторая и третья части перевода), посвящённой тому, как я создал алгоритм сортировки, который быстрее std::sort
Читать полностью »
За 20 лет у меня скопилось несколько тысяч фотографий: праздники, свадьбы, рождение детей, и прочее, прочее... Понятно что снималось всё это на разные цифровики, присылалось почтой, сливалось через ICloud и GDrive, FTP, самба и т.п. По итогу всё это превратилось в дикий хаос папок и что-то найти в архиве можно было только с большим трудом.
В какой-то момент мне нечем было заняться это надоело и я за пару дней накидал скрипт, который всё это безумие раскидал по годам->месяцам->Читать полностью »
Прим. перев.: это не совсем обычный перевод, потому что в его основе не отдельно взятая статья, а недавний случай со Stack Exchange, ставший главным хитом ресурса в этом месяце. Его автор задает вопрос, ответ на который оказался настоящим откровением для некоторых посетителей сайта.
Сжимая каталоги по ~1,3 ГБ, в каждом из которых по 1440 файлов JSON, я обнаружил 15-кратную разницу между размером архивов, сжатых с помощью tar
на macOS или Raspbian 10 (Buster), и архивов, полученных при использовании библиотеки tarfile, встроенной в Python.
Всем привет. Сегодня продолжаем серию статей, которые я написал специально к запуску курса «Алгоритмы и структуры данных» от OTUS. По ссылке вы сможете подробно узнать о курсе, а также бесплатно посмотреть запись Demo-урока по теме: «Три алгоритма поиска шаблона в тексте».
Сортировка массива является одной из первых серьезных задач, изучаемых в классическом курсе «Алгоритмы и структуры данных» дисциплины computer science. В связи с этим задачи на написание сортировок и соответствующие вопросы часто встречаются на собеседованиях на позиции стажера или junior разработчика.
Читать полностью »
«Просто так» результат SQL-запроса возвращает записи в том порядке, который наиболее удобен серверу СУБД. Но человек гораздо лучше воспринимает хоть как-то упорядоченные данные — это помогает быстро сравнивать соответствие различных датасетов.
Поэтому со временем у разработчика может выработаться рефлекс «Дай-ка я на всякий случай это вот отсортирую!» Конечно, иногда подобная сортировка бывает оправдана прикладными задачами, но обычно такой случай выглядит как в старом анекдоте:
Программист ставит себе на тумбочку перед сном два стакана. Один с водой — на случай, если захочет ночью пить. А второй пустой — на случай, если не захочет.
Давайте разбираться — когда сортировка в запросе точно не нужна и несет с собой потерю производительности, когда от нее можно относительно дешево избавиться, а когда сделать из нескольких — одну.