Часть первая – историческая.

Введение

Существующие алгоритмы сжатия данных можно разделить на два больших класса – с потерями, и без. Алгоритмы с потерями обычно применяются для сжатия изображений и аудио. Эти алгоритмы позволяют достичь больших степеней сжатия благодаря избирательной потере качества. Однако, по определению, восстановить первоначальные данные из сжатого результата невозможно.
Алгоритмы сжатия без потерь применяются для уменьшения размера данных, и работают таким образом, что возможно восстановить данные в точности такими, какие они были до сжатия. Они применяются в коммуникациях, архиваторах и некоторых алгоритмах сжатии аудио и графической информации. Далее мы рассмотрим только алгоритмы сжатия без потерь.
Основной принцип алгоритмов сжатия базируется на том, что в любом файле, содержащем неслучайные данные, информация частично повторяется. Используя статистические математические модели можно определить вероятность повторения определённой комбинации символов. После этого можно создать коды, обозначающие выбранные фразы, и назначить самым часто повторяющимся фразам самые короткие коды. Для этого используются разные техники, например: энтропийное кодирование, кодирование повторов, и сжатие при помощи словаря. С их помощью 8-битный символ, или целая строка, могут быть заменены всего лишь несколькими битами, устраняя таким образом излишнюю информацию.

Превью

Здравствуй, Хабр! 25-го апреля 2016 года закончилось 3-х месячное напряженное соревнование Home Depot Product Search Relevance в котором нашей команде Turing Test (Igor Buinyi, Kostiantyn Omelianchuk, Chenglong Chen) удалось не только неплохо разобраться с Natural Language Processing и ML, но и занять 3-е место из 2125 команд. Полное описание нашего решения и код доступны тут, краткое интервью тут, а цель этой публикации не только рассказать о решении, которое принесло нам такой результат, но и о тех трудностях и переживаниях, через которые нам довелось пройти во время соревнования.

Добро пожаловать, или Посторонним вход воспрещён
(С) Э.Г.Климов 1964

Написанный на языке Go роутер (или как его ещё иногда называют — маршрутизатор), который оказался достаточно быстрым для того, чтобы его не стыдно было сравнить с лидерами go-роутинга: Bone, Httprouter, Gorilla, Zeus. Название роутеру дало простое русское слово «Вход», набранное английскими буквами в кодировке волапюк en.wikipedia.org/wiki/Volapuk_encoding

Зачитался я последнее время про Tarantool, интересно стало. Идея хорошая — код рядом с базой данных, хранимка в такой быстрой Redis-подобной среде.

И что-то задумался — мы вот сейчас используем активно на работе Golang, собственно, мысль пришла что на Go написано много всего, в т.ч. и встраиваемых баз. А что если сравнить, например, Go+LevelDB (собственно, можно было бы и любую другую) против Tarantool. Тестировал еще Go+RocksDB, но там оказалось все немного сложнее, а результат примерно тот же на небольших данных.

Тестировал простую задачу — HTTP сервер, при запросе — записать ключик в базу, достать его же по имени (без всяких проверок на race), отправить назад простенький JSON из этого value.

Сравнил: go+leveldb, tarantool, go+go-tarantool, nginx upstream tnt_pass

Как известно, в современных архитектурах x86(_64) и ARM виртуальная память процесса линейна и непрерывна, ибо, к счастью, прошли времена char near* и int huge*. Виртуальная память поделена на страницы, типичный размер которых 4 KiB, и по умолчанию они не отображены на физическую память (mapping), так что работать с ними не получится. Чтобы посмотреть текущие отображённые интервалы адресов у процесса, в Linux смотрим /proc/<pid>/maps, в OS X vmmap <pid>. У каждого интервала адресов есть три вида защиты: от исполнения, от записи и от чтения. Как видно, самый первый интервал, начинающийся с load address (соответствующий сегменту .text у ELF в Linux, __TEXT у Mach-O в OS X), доступен на чтение и исполнение — очень логично. Ещё можно увидеть, что стек по сути ничем не отличается от других интервалов, и можно быстро вычислить его размер, вычтя из конечного адреса начальный. Отображение страниц выполняется с помощью mmap/munmap, а защита меняется с помощью mprotect. Ещё существуют brk/sbrk, deprecated древние пережитки прошлого, которые изменяют размер одного-единственного интервала «данных» и в современных системах эмулируются mmap’ом.

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

• оптимально управляет уже выделенной памятью;
• значительно уменьшает количество обращений к ядру (ведь mmap / sbrk — это syscall);
• вообще абстрагирует программиста от виртуальной памяти, так что многие пользуются malloc’ом, вообще не подозревая о существовании страниц, таблиц трансляции и т. п.

Довольно теории! Будем щупать malloc на практике. Проведём три эксперимента. Работа будет возможна на POSIX-совместимых операционках, в частности была проверена работа на Linux и на OS X.

Когда я задумался о написании Web приложения с использованием Go, я преследовал лишь желание попробовать нечто новое для себя. В последствии я понял, что Web оболочку можно использовать как кросплатформенную GUI библиотеку, чем и воспользовался в своем проекте[1].

В этой статье я рассмотрю разработку веб-приложения на Go. Материал не содержит принципиально новых знаний и рассчитан скорее для таких же новоиспеченных исследователей языка как и я. Хотя, надеюсь, какие-то свежие идеи вы все-таки для себя найдете.

У некоторых читателей могут возникнуть вопросы о «велосипедостроении» — это всё плоды любопытства и живого интереса при ознакомлении с языком Golang.

В игре Go очень простые правила, но стать мастером в ней непросто, нужно научиться думать паттернами, территориями и прочими стратегическими концепциями. Язык Go не совсем случайно назван аналогично названию этой игры. В своем выступлении на недавнем митапе в Сан-Франциско, Роб Пайк упомянул книгу «Постулаты Go» (Go Proverbs), которые описывают сложные стратегии простыми поэтичными фразами. Эти постулаты несут глубинный смысл для тех, кто знаком с игрой Go, и могут казаться пустыми фразами тем, кто не знаком. И в этом нетехническом докладе он предложил придумать аналогичным способом «постулаты» и для языка Go.

Вот некоторые из них:

• Don't communicate by sharing memory, share memory by communicating.
• Concurrency is not parallelism.
• Channels orchestrate; mutexes serialize.
• The bigger the interface, the weaker the abstraction.
• interface{} says nothing.
• Gofmt's style is no one's favorite, yet gofmt is everyone's favorite.
• A little copying is better than a little dependency.
• Cgo is not Go.
• Clear is better than clever.
• Reflection is never clear.
• Errors are values.

Это чем-то похоже на Zen of Python. Вы можете не соглашаться с ними, но эти постулаты отражают идиоматичность и подход в Go. Давайте разберем подробнее каждый из них по мотивам доклада (видео в конце поста).

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

В этой статье вы узнаете:

• в чем отличие от интерфейсов в Java
• важные и неочевидные последствия этих отличий
• как устроены интерфейсы под капотом
• вспомним про пустой интерфейс (interface{})
• затронем сакральную тему про дженерики
• разберемся, кто и зачем должен создавать интерфейс
• и постараемся научиться не абьюзить интерфейсы и начать жить

(artwork by Svitlana Agudova)

Привет, Хабр! Мы в компании PayOnline, которая занимается организацией платежей на сайтах и в мобильных приложениях, решили сделать перевод интересного аналитического материала – глобального опроса среди разработчиков за 2016 год, проведенного сайтом Stack Overflow. Чтобы не утомлять вас чтением действительно объемного исследования, мы выбрали самые интересные, на наш взгляд, слайды.


Общая информация

Каждые 8 секунд (или около того) кто-то из разработчиков публикует свой вопрос на Stack Overflow. В этом же году настал черед Stack Overflow: более 56 тысяч разработчиков из 173 стран ответили на задаваемые вопросы.

Всего им было задано 45 вопросов. Если вкратце, то получилась следующая картина:

Разработчики обожают Rust. Даже разработчики бэкенда знают JavaScript. Только 7% разработчиков считают себя «настоящими рок-звездами». Большинство разработчиков предпочитает собак кошкам (за исключением программистов из Германии).

Лучше маленькая рыбка, чем большой таракан.
Русская поговорка

Lua нравится всем, он простой, но не примитивный. Нет, скорее — продуманный, выверенный, оптимальный. Р.Иерузалимски (автор языка), в своей книге «Программирование на языке Lua» пишет: «Lua — это крошечный и простой язык». Это так. И ещё он скриптовый, переносимый, эффективный, расширяемый, склеивающий (glue). Как же такой не попробовать?

Как и многие другие, я поддался искушению заглянуть, что же из себя представляет Lua. Ну а поскольку самый лучший способ изучить язык, это написать на нём программу, я решил набросать простой веб-микрофреймворк под сервер Apache (версии 2.3+). Апач выбран потому, что он есть на каждом хостинге, и вся настройка под Lua заключается во включении модуля mod_lua.so в конфигурации сервера. Это решение конечно, будет медленнее, чем на Nginx, но возможно, нам больше и не надо?

Достопочтенное Ретро! Благо ты или зло?
Вздохом какого ветра к нам тебя занесло?
© Роберт Рождественский

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