Странно, что это пришло мне в голову — я просто смотрел на Common Lisp и объяснение принципов его работы, ну еще немного на инструментарий Haskell.

И да придет Haskell…

Haskell — она как «та девчонка», ну вы знаете…

Вооруженные жидким азотом оверклокеры неоднократно показывали, что современные чипы могут стабильно работать на частотах в разы выше номинальных, обеспечивая соответствующий рост производительности. Тем не менее, прогресс в области «гонки гигагерц» остановился давно и надежно. Первый «Pentium 4» с частотой больше 3 ГГц появился в далеком 2002 году, почти 10 лет назад. За прошедшие годы нормы техпроцессов уменьшились со 180 до 32 нм, но даже это не позволило существенно поднять штатные рабочие частоты. Все упирается в огромное тепловыделение элементов цифровой логики.

В основе «проблемы тепловыделения» лежит глубокая связь между информационной и термодинамической энтропией, а также второе начало термодинамики, запрещающее уменьшение общей энтропии замкнутой системы. Любое вычисление, уменьшающее энтропию информационную, обязано приводить к увеличению энтропии термодинамической, то есть к выделению тепла. Рольф Ландауэр в 1961 году показал [pdf], что уничтожение одного бита информации должно приводить к выделению не менее k∙T∙ln 2 джоулей энергии, где k – постоянная Больцмана и T – температура системы. Само по себе эта энергия невелика: для T=300K она составляет всего 0.017 эВ на бит, но в пересчете на процессор в целом суммарная энергия вырастает уже до величин порядка одного Джоуля за каждую секунду работы, то есть порядка одного Ватта [Компьютерра №538]. На практике этот теоретический минимум умножается на ненулевое сопротивление и прочие неидеальности реальных полупроводников. В результате мы получаем процессоры, которые по тепловыделению обгоняют утюги.

Тут живут драконы и нет ментейнеров (вместо эпиграфа)

Очень сжатое боевое описание «что есть псевдо-терминал» и «консоль».

Итак, во-первых, определимся с тем, что такое консоль: консоль это программа, которая принимает от пользователя кнопки, а от соединения с компьютером — буквы на экран и спец. команды по рисованию картинки на экране.

Терминал — обобщённое название как программы, так и специальной железки (таких больше нет в природе). Особое исключение — когда вы запускаете путти или ещё кого-то для подключения к последовательному порту коммутатора/рутера/модема (или даже сервера), то вы выступаете (точнее компьютер с путти выступает) в роли терминала (название «терминал» — потому что терминирует кабель (то есть висит на самом конце) ).

Как легко понять по кабелю, есть два конца: терминал и то, что ему посылает байтики в кабель.

Когда запускается шелл, то он получает в своё распоряжение виртуальное устройство /dev/tty, которое у каждого процесса своё — это «обратная» часть терминала. Передняя часть в случае кабеля реализуется путти+компьютер, в случае консоли компьютера, специализированным ядерным драйвером (виртуальными консолями). Важно: драйвер эмулирует наличие терминала.

О чём эта статья

Долгое время я считал, что криптографические алгоритмы шифрования и хеширования, вроде AES и MD5, устроены очень сложно и написать их совсем не просто, даже имея под рукой полную документацию. Запутанные реализации этих алгоритмов на разных языках программирования только укрепляли это мнение. Но недавно у меня появилось много свободного времени и я решил разобраться в этих алгоритмах и написать их. Оказалось, что они очень просто устроены и для их реализации нужно совсем немного времени.

В этой статье я напишу как устроен алгоритм шифрования AES (которого иногда называют Rijndael) и напишу его на JavaScript. Почему на JavaScript? Чтобы запустить программу на этом языке, нужен только браузер в котором вы читаете эту статью. Чтобы запустить программу, скажем, на C, нужен компилятор и найдётся совсем мало желающих, готовых потратить время на компиляцию кода из какой то статьи. В конце есть ссылка по которой можно скачать архив с html страницей и несколькими js файлами — это пример реализации AES на JavaScript.

На написание данной статьи меня подтолкнул топик HTML в PDF, правда по причине того, что он посвящен языку php, лично мне он был мало полезен, т.к. весь опыт работы с php у меня сводился в переводе нескольких скриптов на C#, поэтому я решил сделать небольшой обзор того, что доступно для работы с pdf по средствам языка C#.

Ко мне в список попало 7 библиотек, о которых я скажу несколько слов, а для самой популярной (судя по ответам на stackoverflow), я напишу, как с помощью неё сделать простейший документ. Сразу скажу, что это iTextSharp и работа с ней будет описана в конце статьи.

Еще в прошлом году на просторах Интернета у забугорных собратьев (а именно у Алекса Галузина) по геймдеву увидел замечательную книгу «How to Create a Map in 11 Days». Сразу появилась мысль о ее прочтении и переводе на русский язык.

Хоть в книге и идет речь о UDK и Maya она не привязана ни к каким движкам, а больше рассказывает о организации рабочего процесса и постановке задач при разработке игрового уровня.

Позвольте мне начать своё повествование с рассказа про свободное время, семью и тягу к прекрасному. Свободного времени, которое я могу провести с женой, обычно очень мало. То я занят, то жена. То мы оба. Но иногда высвобождается час-другой, который можно провести вместе. А что можно сделать вместе? Ну, кроме того что вы подумали, можно ещё посмотреть вместе фильм. Сходить в кино, например, выбрав один из пяти унылых фильмов в кинотеатре. Или достать с полки DVD и в 5й раз посмотреть «Новинки 2006 года, 8 в 1». Но кому нужны новинки 2006 года в качестве для мобильного телефона или платить деньги за билеты в кино, если всё что нужно для удовольствия можно сделать у себя дома практически бесплатно? Если есть трекер на котором постоянно выкладываются сотни интересных фильмов? Если есть хороший телевизор и диван, на котором смотреть фильмы намного приятнее? Нет, иногда, конечно, приятно сходить в кино, или пересмотреть новинки 2006, но в большинстве случаев мы хотим (1) дома, (2) бесплатно посмотреть (3) новый фильм (4) в хорошем качестве (5) не дожидаясь пока он скачается.

Приветствую, Хабрахабр. Сегодня я хочу, в своём обычном стиле, устроить сообществу небольшой ликбез по структурам данных. Только на этот раз он будет гораздо более всеобъемлющ, а его применения и практичность — простираться далеко в самые разнообразные области программирования. Самые красивые применения, я, конечно же, покажу и опишу непосредственно в статье.

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

Итак, на повестке сегодняшнего дня — моноиды и их основное применение для кеширования вычислений в деревьях.

Моноид как концепция

Представьте себе множество чего угодно, множество, состоящее из объектов, которыми мы собираемся манипулировать. Назовём его M. На этом множестве мы вводим бинарную операцию, то есть функцию, которая паре элементов множества ставит в соответствие новый элемент. Здесь и далее эту абстрактную операцию мы будем обозначать "⊗", и записывать выражения в инфиксной форме: если a и b — элементы множества, то c = a ⊗ b — тоже какой-то элемент этого множества.

Например, рассмотрим все строки, существующие на свете. И рассмотрим операцию конкатенации строк, традиционно обозначаемую в математике "◦", а в большинстве языков программирования "+": "John" ◦ "Doe" = "JohnDoe". Здесь множество M — строки, а "◦" выступает в качестве операции "⊗".
Или другой пример — функция fst, известная в функциональных языках при манипуляции с кортежами. Из двух своих аргументов она возвращает в качестве результата первый по порядку. Так, fst(5, 2) = 5; fst("foo", "bar") = "foo". Безразлично, на каком множестве рассматривать эту бинарную операцию, так что в вашей воле выбрать любое.

Далее мы на нашу операцию "⊗" накладываем ограничение ассоциативности. Это значит, что от неё требуется следующее: если с помощью "⊗" комбинируют последовательность объектов, то результат должен оставаться одинаковым вне зависимости от порядка применения "⊗". Более строго, для любых трёх объектов a, b и c должно иметь место:
(a ⊗ b) ⊗ c = a ⊗ (b ⊗ c)
Легко увидеть, что конкатенация строк ассоциативна: не важно, какое склеивание в последовательности строк выполнять раньше, а какое позже, в итоге все равно получится общая склейка всех строк в последовательности. То же касается и функции fst, ибо:
fst(fst(a, b), c) = a
fst(a, fst(b, c)) = a
Цепочка применений fst к последовательности в любом порядке всё равно выдаст её головной элемент.

И последнее, что мы потребуем: в множестве M по отношению к операции должен существовать нейтральный элемент, или единица операции. Это такой объект, который можно комбинировать с любым элементом множества, и это не изменит последний. Формально выражаясь, если e — нейтральный элемент, то для любого a из множества имеет место:
a ⊗ e = e ⊗ a = a
В примере со строками нейтральным элементом выступает пустая строка "": с какой стороны к какой строке её ни приклеивай, строка не поменяется. А вот fst в этом отношении нам устроит подлянку: нейтральный элемент для неё придумать невозможно. Ведь fst(e, a) = e всегда, и если a ≠ e, то свойство нейтральности мы теряем. Можно, конечно, рассмотреть fst на множестве из одного элемента, но кому такая скука нужна? :)

Каждую такую тройку <M, ⊗, e> мы и будем торжественно называть моноидом. Зафиксируем это знание в коде:

public interface IMonoid<T> {
    T Zero { get; }
    T Append(T a, T b);
}

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

(вторая часть перевода статьи Разоблачение алгоритмов растеризации шрифтов)

Linux

Наследуя худшее

Windows растеризует шрифты плохо, Linux ещё хуже. Во всех Linux-системах, которые я видел, используется FreeType [10] Дэвида Тёрнера, Роберта Вильгельма и Вернера Лемберга. Это отличная библиотека, но способ её использования, к сожалению, нельзя назвать удачным. Типичный скриншот Linux выглядит так:



Вот полный скриншот:
ссылка

Сразу заметна проблема — чёрные пятна в скругленных углах, образовавшиеся в результате сглаживания. Вцелом, можно сказать, что косые штрихи выглядят тяжелее чем вертикальные, что в регультате производит впечатление «грязи». Вы можете возразить, что FreeType и Linux могли бы использовать схожую с ClearType субпиксельную растеризацию, но по мне это не даёт заметных преимуществ.

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

От переводчика

В первый раз я столкнулся с этой статьей в 2008 году. С тех пор я неоднократно задумывался о переводе (так как лучшего материала по теме не найти), и вдруг ссылка на оригинал всплыла на Хабре в обсуждении топика «Сглаживание шрифтов, анти-алиасинг, и субпиксельный рендеринг». Это стало решающим фактором (раз на материал ссылаются, значит, он кому-то нужен), и работа была, наконец, закончена.

Импорт фактов в базу пролога из файла в формате CSV

Для того чтобы работать с фактами базы данных в прологе их (факты) необходимо импортировать из внешнего источника.


На схеме условно показаны три области активностей:
Желтая — подготовка промежуточного файла. Для простого импорта это может быть просто сохранение документа в формате CSV. Для работы по регламенту возможна настройка компонентов БД (например MS SQL Server Integration Services) для периодической выгрузки. Данная активность в статье не рассматривается.
Красная — импорт данных из CSV файла в базу фактов.
Зеленая — работа с базой фактов в Прологе.
Примечание. Стрелками показаны потоки данных.

И снова здравствуйте! Сегодня я поведаю о фильтре Блума — структуре данных гениальной в своей простоте. По сути, этот фильтр реализует вероятностное множество всего с двумя операциями: добавление элемента к множеству и проверка принадлежности элемента множеству. Множество вероятностное потому, что последняя операция на вопрос «принадлежит ли этот элемент множеству?» даёт ответ не в форме «да/нет», а в форме «возможно/нет».

По просьбам трудящихся выкладываю описание и доказательство алгоритма Укконена.

Описание задачи

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

Бор для произвольного набора строк строится за O (суммы длин этих строк). Очевидно, что сумма длин всех суффиксов строки пропорциональна квадрату длины самой строки. Таким образом, построение суффиксного дерева тривиальным алгоритмом работает за O(N²). И тут возникает резонный вопрос, можно ли построить суффиксное дерево быстрее?

На самом деле можно.

Здравствуй, Хабрахабр. Сегодня я хочу рассказать о такой замечательной структуре данных как словарь на нагруженном дереве, известной также как префиксное дерево, или trie.

Что это ?

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

Привет! Бывает, хочется забыть о «скучной» консоли, разбавить ее хоть капелькой интерактива, особенно если часто приходиться делать одни и теже операции и тем более если вы пишите для облегчения своей участи скрипты. Итак, псевдографика. За мной читатель, я покажу тебе такую консоль!

G.E.C.K. (Генератор Эдемских Кущ Компактный, Группа Эдемских Конструкционных Компонентов, КОмплект СОздания ГОрода Рая). Немало игровых часов потрачено в Fallout 2 чтобы найти этот заветный чемоданчик. Еще больше часов потрачено в обдумывании реализации подобного проекта в реальности.
И подобный проект в реальности есть, хотя по габаритам и несколько крупнее чемоданчика. Цели у проекта под названием Комплект Создания Всемирной Деревни (The Global Village Construction Set) разработать набор недорогих и открытых инструментов для построения поселений.

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

К счастью, решить большинство этих проблем в Linux может технология LVM. Она создаёт дополнительную абстракцию — логические тома, которые видны в системе, как обычные разделы, однако реально ими не являются. Эта технология очень полезна для серверов, однако и на домашних компьютерах она приходится очень к месту. Я больше не думаю, какого размера диск выделить под систему, чтобы какой-нибудь texlive не забил бы всё место, но и чтобы лишние 5 — 10 гигабайт не пропадали просто так. LVM имеет ряд существенных преимуществ, значительно упрощающих жизнь:

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

Системные администраторы сервиса Netflix нашли интересное решение, которое позволило улучшить архитектуру сервиса, и уменьшить влияние технических проблем на конечных пользователей.

В компании был написан и запущен внутренний сервис под названием «Chaos Monkey» (Обезьянка Хаоса (не путать с Хаусом!)), который случайным образом убивает инстансы AWS или процессы на серверах, обслуживающих сервис. Как ни странно, такой подход не вредит, а помогает технарям улучшать качество сервиса и повышать аптайм, убивая несколько обезьян зайцев — системы Netflix проходят круглосуточную проверку на то, что:

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

Этот оригинальный (если не сказать парадоксальный) подход сэкономил огромное количество денег и времени компании. А что об этом думают хабрагуру?

Preface

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

1. Систематизировать материал по данному направлению, обсудить некоторые несостыковки в терминологии
2. Полностью разобрать фундамент, на котором строятся приложения для обслуживания множество клиентов
3. Выработать стратегию для будущего приложения на python которое должно обслуживать множество клиентов
4. Создать четкую картину в голове (недаром говорят понимаешь — когда можешь объяснить)

Недавно на хабре появилось сразу два материала, посвященных языкам из «большой четверки тьюринговых трясин»: про алгоритм Маркова и Brainfuck. Думаю, для полноты картины будет интересно сравнить эти эзотерические системы с еще одним важным алгоритмическим примитивом — машиной Поста, которой я как раз занимаюсь.

Машина Поста (wiki; для простоты оттуда же взят вариант синтаксиса) похожа на всем известную машину Тьюринга, однако обладает интересными особенностями. Она содержит лишь 6 команд, кроме того, в ячейки-биты памяти могут записываться лишь 2 символа (двоичное кодирование информации). «Естественно», никакой дополнительной памяти, не зря же эзотерикой зовется!

Таким образом, при программировании на машине Поста помимо необходимости совладать с оккамовским синтаксисом надо думать о том, как записать на ленте все промежуточные результаты, не потеряв по пути обратную тропинку к остаткам входных данных. Почему «остаткам»? Зачастую ввиду отсутствия дополнительной памяти приходится обрабатывать входные данные итеративно (а иногда и рекурсивно). Надеюсь, вышеизложенное убедительно доказывает, что написание привычных алгоритмов на машине Поста — неплохая разминка для мозгов и весьма увлекательное занятие.