Программист из Индии наглядно показывает Zig-Zag, Zig-Zig и Zig, используемые в алгоритме SplaySort:

В этом сезоне мы изучаем разнообразные кучи и как их можно использовать для сортировки. Однако на сей раз мы сделаем шаг в сторону от магистральной темы. Сегодняшняя структура — splay tree — кучей не является. Но оно нам нужно, чтобы морально подготовиться к изучению очередной кучи — на следующей неделе будет лекция про сортировку декартовым деревом.

Всем доброго времени суток, и сегодня (о боже, как же давно я ничего не писал, тем более полезного) мне бы хотелось ответить на этот пост.

Для несведущих краткий пересказ:
Чувак заставил себя посмотреть фильм Дудя про Кремниевую долину и переживает из за того, что мамкины программисты на пыхе и джаваскрипте приложений для пука по клику посчитают себя разработчиками и поедут в Кремниевую долину искать инвестора.

Введение

Всё началось с короткого скрипта, который должен был объединить информацию об адресах e-mail сотрудников, полученных из списка пользователей почтовой рассылки, с должностями сотрудников, полученными из базы отдела кадров. Оба списка были экспортированы в текстовые файлы в кодировке Юникод UTF-8 и сохранены с юниксовскими концами строк.

Содержимое mail.txt

Иванов Андрей;ia@example.com

Содержимое buhg.txt

Иванова Алла;маляр
Ёлкина Элла;крановщица
Иванов Андрей;слесарь
Абаканов Михаил;маляр

Для объединения файлы были отсортированы юниксовской командой sort и поданы на вход юниксовской программе join, которая неожиданно завершилась с ошибкой:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: is not sorted: Иванов Андрей;слесарь

Просмотр результата сортировки глазами показал, что в целом сортировка правильная, но в случае совпадений мужских и женских фамилий, женские идут перед мужскими:

$> sort buhg.txt
Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванова Алла;маляр
Иванов Андрей;слесарь

Выглядит как глюк сортировки в Юникоде или как проявление феминизма в алгоритме сортировки. Первое, конечно, правдоподобнее.

Еще в декабре мне попалась одна совершенно замечательная статья на английском, посвящённая использованию системы типов языка для более широкого класса задач, для повышения надежности приложений и простоты рефакторинга. К сожалению, в тот момент я был слишком занят написанием статей по ФП, которые крайне важно было написать, пока свежи воспоминания. Но теперь, когда с этой задачей я справился, наконец дошли руки перевести эту замечательную заметку. Оригинальный язык примеров — Хаскель, но я решил переписать их на раст, для более широкого охвата аудитории. Однако язык тут совершенно неважен, советы этой статьи я применяю в ежедневной разработке на вполне себе "приземлённых" C# и TypeScript, так что если вы просто стараетесь писать надёжный и поддерживаемый код, то, вне зависимости от языка, статья вам будет в тему.

Благодарю за вычитку и помощь в переводе Hirrolot, funkill и andreevlex

Привет, Хабр!

Я уже около года изучаю и, в свободное время, пишу на расте. Мне нравится как его авторы решили проблему управления памятью и обошлись без сборщика мусора — через концепцию заимствования. В этой статье подойду к этой идее через итераторы.

Последнее время scala является моим основным языком, так что сравнения будут с ней, но их не много и все интуитивно понятные, без магии :)

Статья рассчитана на тех кто что-то слышал о rust'e, но в детали не вдавался.


фотографии взяты отсюда и отсюда

В преддверии старта курса «Разработчик Golang» подготовили перевод интересного материала. А каким было ваше первое впечатление от Go?

---

На протяжении последних нескольких недель мне довелось использовать Go в работе. Я впервые использовал Go на более-менее крупном и серьезном проекте. До этого я достаточно много читал про Go и практиковался на примерах и небольших программах при изучении возможностей Rust, но реальное программирование — это совсем другое дело.

Я подумал, что вам может быть интересно услышать о моих впечатлениях. Я постараюсь не зацикливаться на сравнениях с Rust, но так как это мой основной язык, их не избежать. Я должен заранее вас предупредить о сильном уклоне в сторону Rust, но я сделаю все возможное, чтобы быть объективным.

Пару недель назад я играл в A Plague Tale студии Asobo Studio (и прошёл её). Меня очень захватила эта игра, благодаря не только красивой графике, но и сюжету с локациями. Я решил немного изучить технологии, использовавшиеся при её разработке, и был удивлён, обнаружив, что игра создавалась на собственном движке относительно небольшой студии. Я знаю, что некоторые компании используют собственные движки, но очень сложно найти подробное маркетинговое исследование с подобной информацией. Поэтому я написал эту статью.

Сегодня многие компании выбирают для разработки игр такие движки, как Unreal или Unity (или, по крайней мере, так думают многие люди), потому что для разработки собственного движка AAA-уровня требуется множество ресурсов. Поэтому я решил составить список некоторых из самых популярных самописных движков с указанием размеров студий и значимых игр, выпущенных на этих движках.

Большинство представленных здесь движков разрабатывалось на протяжении многих лет, множества итераций и для множества видеоигр, эти движки имели несколько версий или даже полностью (частично) переписывались с нуля с последующей сменой названия. Кроме того, важно заметить, что большинство этих движков для реализации определённой функциональности (совместимость с платформами, физика, сеть, растительность, UI, рендеринг, звук...) использует всевозможное промежуточное ПО.

В этом бардаке, который сейчас происходит в мире, легко забыть, что прошло уже пять лет с выпуска 1.0 в 2015 году! Rust за эти пять лет сильно изменился, так что мы хотели бы вспомнить о работе всех участников сообщества, начиная с момента стабилизации языка.

Напомним, если кто забыл: Rust — это язык программирования общего назначения, который обладает средствами, позволяющими строить надёжное и эффективное программное обеспечение. Rust может быть использован в любой области: от ядра вашей операционной системы до вашего следующего web-приложения. Этот язык полностью построен участниками открытого многоликого сообщества, в основном волонтёрами, кто щедро делился своим временем и знаниями для того, чтобы помочь сделать Rust таким, какой он есть сейчас.

Этот пост — о программе на Rust…

$ cargo install conway-nes

…выводящей двоичный файл NES…

$ conway-nes > life.nes

…в котором выполняется конвеевская игра «Жизнь»!

$ fceux life.nes    # fceux is a NES emulator

Запустив игру на эмуляторе, нажмите любую кнопку контроллера, чтобы начать заново с рандомизированного состояния.

Свежий взгляд на традиционные концепции. Сегодня будет такой «декарт» которого в школе не проходили.

Суть алгоритма в том, что на основании массива строится так называемое декартово дерево. А из построенного декартового дерева очень легко получить все элементы в порядке возрастания или убывания.

Сложно найти человека, не знакомого с игрой "Жизнь", придуманной английским математиком Джоном Конвеем еще в 1970 году, и до сих пор не теряющей своей популярности. Многие программисты писали свою реализацию этой игры, и еще одна вряд ли кого-то удивит. Однако эта игра является отличным примером, показывающим, насколько полезной может оказаться оптимизация вычислений, даже не меняющая асимтотическую сложность алгоритма. Мы начнем с простейшей реализации на c# и будем последовательно применять различные оптимизации, ускоряя работу программы.

Мы также улучшим алгоритм на JavaScript, ускорив его в 10 раз по сравнению с неоптимизированной версией.

В конце статьи дана ссылка на код, а также на online-реализацию игры с оптимизированным алгоритмом на JavaScript, выполняющим до двухсот итераций в секунду на поле размера 1920x1080 (Full HD), где вы можете убить время поиграть в эту замечательную игру.

Солнце восходит над древнем Египтом, солнечный бог Ра послал править людьми фараона. А у фараона есть помощники по связи с начальством, жрецы, которые вполне могли бы задавать новобранцем какую-нибудь хитрую задачку, на отбор. Я точно не знаю, так ли это всё было, но пример задачки существует, и в моём пересказе звучит так.

В «колодце лотоса», круглом, с ровным дном и вертикальными стенками, должен быть уровень воды ровно один древнеегипетский метр. Определяют сколько наливать просто: бросают две жерди, длиной два и три метра, они нижними концами встают напротив друг друга, и пересекаются ровно на нужной высоте. Каков диаметр колодца?

Системы типов — это настоящее безумие.

Некоторое время назад я уже отметился здесь со статьёй, в которой пытался разобрать, какие гарантии в compile-time может дать система типов Rust. Кое-какие интересные моменты удалось выловить уже тогда, однако больше всего меня зацепил весьма развёрнутый комментарий, описывающий некоторые вещи, доступные в зависимо-типизированном Idris.
Разумеется, я не мог остаться в стороне. Результат исследований доступен на github, а детальный разбор — под катом.

Всем привет! Не так давно, после очень плотного изучения аллокаторов и алгоритмов распределения памяти, а также в последующем применении их на практике мне в голову пришла идея написать статью, в которой будет максимально подробно рассказано о них. Считаю, что данная тема будет достаточно востребованной, так как в сети, особенно в русскоязычной части, на данный момент существует очень мало источников, посвященных этому вопросу.

Google будет снова редизайнить редизайн результатов поиска. Недавно на компанию обрушился шквал критики в связи с обновлением, после которого органические результаты стали практически неотличимы от рекламы.

Google зарабатывает деньги на кликах по рекламе в поиске и не зарабатывает, когда пользователи кликают на один из обычных результатов. И, соответственно, начинает зарабатывать больше, уменьшая различия между первым и вторым.

Это можно назвать довольно злостным решением (или, как минимум, неэтичным) со стороны компании, чьей мантрой в прошлом было «не быть злом» (которую они выбросили из своего Code of conduct в 2018)

Начнём со сладкого и приведём примеры из практики тестирования.

Представьте себе готовый к запуску интернет-магазин. Ничего не предвещает беды. Маркетологи разработали стратегию продвижения, были написаны статьи в профильные интернет-ресурсы, оплачена реклама. Руководство ожидало до 300 покупок еженедельно. Проходит первая неделя, менеджеры фиксируют 53 оплаты. Руководство магазина в ярости…

К написанию данной статьи меня побудил вопрос на Тостере, связанный с WSL. Я, после нескольких лет использования систем на ядре Linux, около полугода назад перешел к использованию Windows 10 на домашнем ПК. Зависимость от терминала и Linux окружения в моей работе практически сразу привели меня к вопросу: или ставить виртуалку или попробовать WSL. Я выбрал второе, и остался вполне доволен.

Под катом я расскажу как установить и настроить WSL, на какие я наткнулся проблемы и ограничения, как запускать Linux приложения из Windows и наоборот, а так же как интегрировать элементы окружения Xfce в окружение рабочего стола Windows.

Когда мы 19 сентября разбирали iPhone 6, предоставленный одним смелым интернет-магазином, его владелец Игорь рассказывал нам удивительные истории о мошенничествах, связанных с этим популярным гаджетом. Истории были насколько увлекательными, настолько и печальными. После того, как эпопея с разбором и сбором закончилась, я попросил Игоря рассказать все известные ему способы жульничества, коих набралось аж двадцать штук. Большинство из них касается покупателей iPhone, но некоторые относятся и к продавцам, которых тоже пытаются обмануть с нерадующей регулярностью.



По итогам получился пост, который, надеюсь, поможет вам избежать многих неприятностей при покупке гаджетов. Тем более, что уловки мошенников универсальны, и могут быть применены не только при операциях с продукцией Apple.

Недавно на хабре появилась неплохая статья про вычисление N-ного числа фибоначи за O(log N) арифметических операций. Разумный вопрос, всплывший в комментариях, был: «зачем это может пригодиться на практике». Само по себе вычисление N-ого числа фибоначи может и не очень интересно, однако подход с матрицами, использованный в статье, на практике может применяться для гораздо более широкого круга задач.

В ходе этой статьи мы разберем как написать интерпретатор, который может выполнять простые операции (присвоение, сложение, вычитание и урезанное умножение) над ограниченным количеством переменных с вложенными циклами с произвольным количеством итераций за доли секунды (конечно, если промежуточные значения при вычислениях будут оставаться в разумных пределах). Например, вот такой код, поданный на вход интерпретатору:

loop 1000000000
  loop 1000000000
    loop 1000000000
      a += 1
      b += a
    end
  end
end
end

Незамедлительно выведет a = 1000000000000000000000000000, b = 500000000000000000000000000500000000000000000000000000, несмотря на то, что если бы программа выполнялась наивно, интерпретатору необходимо было бы выполнить октиллион операций.

Некоторые из вас, вероятно, видали на просторах сети эту задачку: какое число продолжает следующий ряд?

Предлагался такой очевидный правильный ответ:

Для тех, кому неочевидно, как он получен, предлагалось объяснение. Пусть (ну и 1 при x = 0, хотя неважно). Тогда каждый член ряда — это значение следующего интеграла в цепочке:

Пока всё идёт хорошо, но тут внезапно:

В принципе, этого достаточно, чтобы повеселить друзей-математиков, но мне захотелось узнать, как вообще считаются такие интегралы и почему получается такой смешной результат. Если кому-то ещё охота тряхнуть стариной и вспомнить матан с функаном, прошу читать дальше.