Данная статься продолжает серию публикаций о технологиях, которые мы используем для разработки сервиса проверки доступности веб сайтов HostTracker.
Сегодня речь пойдет о…

MailboxProcessor

Вышла недавно статья на Хабре о том, как можно самому создать на функциональном языке такие структуры как Очередь (первый зашёл, первый вышел) и Дек (напоминает двусторонний стек — первый зашёл, первый вышел с обоих концов). Посмотрел я на этот код и понял, что он жутко неэффективен — сложность порядка O(n). Быстро сообразить, как создать структуры с O(1) у меня не вышло, поэтому я открыл код библиотечной реализации. Но там была не лёгкая и понятная реализация, а <много кода>. Это было описание пальчиковых деревьев, необходимость и элегантность которых для этой структуры данных хорошо раскрывается текущей статьёй.

Пальчиковые деревья

В этой статье мы рассмотрим пальчиковые деревья. Это функциональные неизменяемые структуры данных общего назначения, разработанные в работе Гинце и Паттерсона. Пальчиковые деревья обеспечивают функциональную структуру данных Последовательность (sequence), которая обеспечивает амортизированной доступ постоянный во времени для добавления как в начало, так и в конец последовательности, а также логарифмическое время для конкатенации и для произвольного доступа. В дополнение к хорошему времени асимптотических исполнения, структура данных оказывается невероятно гибкой: в сочетании с моноидальными тегами на элементах, пальчиковые деревья могут быть использованы для реализации эффективных последовательностей с произвольным доступом, упорядоченных последовательностей, интервальных деревьев и очередей приоритетов.

Статья будет состоять из 3-х частей:

Пальчиковые деревья (Часть 1. Представление)
Пальчиковые деревья (часть 2. Операции)
Пальчиковые деревья (Часть 3. Применение)

Разрабатывая структуру данных

Основа и мотивация пальчиковых деревьев пришла от 2-3 деревьев. 2-3 деревья — это деревья, которые могут иметь две или три ветви в каждой внутренней вершине и которые имеют все свои листья на одном и том же уровне. В то время, как бинарное дерево одинаковой глубины d должны быть 2^d листьев, 2-3 деревья гораздо более гибкие, и могут быть использованы для хранения любого числа элементов (количество не должно быть степенью двойки).
Рассмотрим следующее 2-3 дерево:



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

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

(из личного архива Даниэля Алиевского: «Второй слева — Илья Жильцов, светлая ему память. Я стою за ним, моя голова третья слева»)

(про саму олимпиаду Первая Всероссийская олимпиада школьников по программированию (информатике) 1989 года)

По моей просьбе Даниэль (http://algart.net) поделился воспоминаниями:

«Мы, т.е. свердловская „команда“ из 2 человек — первые два места с областной олимпиады, Максим Стацюк и я — вылетели в Красноярск ночью с 18 на 19 марта 1989 года. Рано утром мы наконец добрались до гостиницы. В гостиницах до той поры я никогда не был, только читал про них в книжках, и впечатление от советской гостиницы получилось довольно тяжелое. Но жить можно было. Даже был туалет и душ в номере, а вообще номер был рассчитан на двоих. Не так плохо, по советским временам! (Позже, на Всесоюзной, я понял, что бывает и хуже.)

Первый день был потрачен на сон (4 часа) и, конечно же, на карты, в которые мы резались со Стацюком и ребятами из других городов до полтретьего ночи. 3.40 — все же отбой.

Выспаться, впрочем, не получилось, поскольку с 9 утра, после завтрака, следовало снова заняться делом, а именно картами. Ну а после 3 дня мы все пошли по магазинам. Красноярск — большой город, интересный для новичков. С семи вечера и до 0.30 — снова карты, пока нас не разогнала наша руководительница, которая и привезла нас с Максимом из Свердловска. Кстати, очень милая девушка, звали, если не ошибаюсь, Виктория Викторовна.

Статья про то, как с помощью расширенных генераторов Python сделать собственную реализацию сопрограмм, переключающихся по получению событий. Простота кода получившегося модуля вас приятно удивит и прояснит новые и мало используемые возможности языка, которые можно получить, используя такие генераторы. Статья поможет разобраться и с тем, как это устроено в серьезных реализациях: asyncio, tornado, etc.

Добрый день!

Меня зовут Алексей Брагин, я приветствую всех гостей на открытии блога компании «Фонд ReactOS», которое стало возможным благодаря программе поддержи стартапов от «Тематических Медиа».

От лица всей команды разработчиков проекта ReactOS представляю вашему вниманию новый релиз нашей операционной системы под номером 0.3.17

Это Денис с эндоскопом в автосервисе

Буквально на днях я получил, наверное, лучший урок по управлению проектами в жизни. Есть обычный русский мужик, который раньше сидел в офисе и работал в рекламном бизнесе, мой бывший коллега (я сам IT-спец в агентстве).

Представим типичный пользовательский интерфейс. Есть несколько элементов управления, которые запускают некоторые повторяемые (за время жизни приложения) действия разной сложности. Чтобы сложные действия, такие как обращение к различным носителям, обращение к сети или сложное вычисление, не снижали отзывчивость интерфейса, они должны быть асинхронными. Дополнительно могут быть элементы управления, отменяющие асинхронно запущенное действие. Действие имеет свойство состояния (неактивно, запущено, завершено успешно, завершено с ошибкой, отменено), которое тем или иным образом отображается пользователю. Принятый в WPF, Silverlight и WinPhone шаблон проектирования MVVM диктует, чтобы такое «действие» было частью модели представления, давая возможность вызывать сервисы модели из пользовательского интерфейса без создания между ними жёсткой связи. К сожалению, такое «действие» в базовой библиотеке классов не реализовано. Ближайшие имеющиеся в библиотеке сущности, такие как задачи System.Threading.Tasks.Task, команды System.Windows.Input.ICommand и делегаты System.Delegate, не подходят: задачи всегда одноразовые и не могут представлять повторяемое действие, делегаты и команды не поддерживают отмену и не содержат свойств состояния, а команды вообще не могут быть асинхронными. Далее я предлагаю решение в виде небольшой библиотеки классов, дающей возможность легко использовать описанные «действия» в ваших приложениях.

Дело в том, что все (или почти все) поисковые запросы в Яндексе, пусть и в анонимизированном виде, в реальном времени доступны по адресу export.yandex.ru/last/last20x.xml

На основе этого API я сделал маленький проект на Openresty (nginx + Lua + imagemagick), предоставляющий высокопроизводительную реализацию CAPTCHA.



Предусмотрена возможность встраивания в виде iframe.

GitHub, demo

С каждым днём кроссплатформенная разработка под .NET становится всё более реальной. А после недавнего анонса официальной поддержки Linux/MacOS счастливое будущее стало ещё немножечко ближе. Вышеприведённая картинка утратила свою былую актуальность, ведь исходники теперь будут под MIT. Впрочем, писать кроссплатформенные .NET-приложения можно достаточно давно — в этом нам помогает Mono. Но вот отношение к нему в сообществе довольно неоднозначное. Мне зачастую приходится слышать изречения вроде «Mono тупит, под него всё в три раза медленнее работает» или «Под Mono вообще нормально ничего не запускается». Причём очень редко доводится слышать от этих людей конкретные факты. Вопросы «А что конкретно тупит?» или «А что конкретно не работает?» повергают их в ступор. Не всех (некоторые способны на конструктивную дискуссию), но большинство. Чаще всего начинаются возмущённые ответы в духе «Да вообще ничего не работает! А если и работает, то очень медленно!». В конце беседы создаётся впечатление, что каждая конечная машинная команда под Mono работает в несколько раз медленнее, а в половине исходников стоят throw new Exception().

В этом посте мне хотелось бы немножко поделиться опытом. Не так давно мы портировали наш продукт PassportVision (анонс на Хабре) под Linux. Могу заявить, что работает он вполне нормально. Да, чутка медленнее, чем под Windows на классическом .NET от Microsoft (далее — MS.NET). Но работает вполне стабильно, а падение производительности не принципиальное. При этом продукт у нас достаточно большой и вполне попадает под категорию enterprise, а возможности C#/.NET мы используем на полную катушку. Так что завести большое серверное приложение под .NET реально — было бы желание. Также мне довелось беседовать с разными разработчиками, которые пишут что-то под Mono — истории в большинстве своём успешные.

Но почему же тогда встречается столько негатива в сторону Mono? Я считаю, что проблема в том, что люди не особо хотят разбираться в разнице между рантаймами. Запустили разок какое-нибудь .NET-приложение под Linux на Mono 2.4, а оно с ходу не запустилось — всё, Mono целиком плохой, не будем его использовать. А в итоге виноват оказывается один-единственный метод, у которого реализация немного отличается от MS.NET. Новые версии Mono выходят раз в пару месяцев, реализацию уже давно поправили, но люди всё равно продолжают ходить и хаять бедный Mono, не желая разбираться в деталях.

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

Сам Unity Engine (далее Unity), как и многие другие игровые движки, наиболее приспособлен к компонентно-ориентированному программированию (далее КОП), так как Behavioral Pattern — один из базовых паттернов архитектуры движков, наряду с паттерном «Component» из классификации Decoupling Patterns. Потому именно компонент является базовой единицей для реализации бизнес-логики в Unity. В этой статье я расскажу о том, как применять КОП в Unity.

После многих слухов Samsung сегодня представил смартфон с металлическим корпусом Galaxy Alpha, пишет The Verge. Это ультратонкий (6,7 мм) Android-телефон с 4,7-дюймовым 720p-дисплеем, 12-мегапиксельной камерой, небольшой батареей на 1,860 мАч и (в зависимости от региона) четырёх- или восьмиядерным процессором. Появится в продаже он в сентябре, цена пока что неизвестна. Традиционно новый телефон будет доступен в чёрных, белых, золотых и синих цветах.

Сегодня вернулся в Москву после прохождения акселерационной программы в одном из самых известных бизнес-инкубаторов. Решил поделиться опытом и впечатлениями с читателями Хабра. Под катом статья на тему — «как я провел этим летом в Кремниевой долине».

Disclaimer

Текст не претендует на истину в последней инстанции, описанное ниже основано на собственном опыте и рекомендациях людей с больше чем двадцати годами опыта в IT в США и Канаде.

Анализ резюме рекрутером

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

У вас есть 3-5 минут чтобы заинтересовать своим резюме. Это то, сколько будет уделено времени на него в начале, в лучшем случае. Часто резюме могут отсеяться спустя 10 секунд. Вас никто не знает, вы это лист бумаги с текстом, и это единственное, что вас может отличить от других. Представьте, что вы хотите купить новый телевизор, вас вряд ли будут интересовать длинные мануалы или 5 страничные описания. Выбирая из десятков и сотен аналогов, нужно за 5-10 секунд сделать предварительный отсев по определенным параметрам. Оставшимся 5-10 устройствам вы выделите чуть больше времени, а потом еще помешкаете выбираю между двух. Как то так и происходит отбор кандидатов.

В списке самых популярных репозиториев Github за неделю на первое место вышел набор иконок Material Design, разработанный в компании Google.

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

Привет, username!

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

Когда мы подавались на участие в программе акселерации, нас мучил вопрос, как стартапы сосуществуют друг с другом в коворкингах и инкубаторах? Мы привыкли работать в маленьком офисе или вовсе из дома, общаясь по Skype. Конечно, часть команды и до этого работала в опенспейсах, но все же, когда в офисе сидит одна компания, или даже один отдел (только продажники, например), все намного понятнее и проще. А как это происходит, если компаний огромное множество? Не падает ли продуктивность каждого из проектов?

По прошествии почти двух месяцев акселерации мы, Анна Чащина и Аида Легранд, сооснователи Witget, решили рассказать о том, как здесь живется проектам. Офис акселератора настолько запал нам в душу, что вылезти с работы часто бывает довольно сложно, хоть мы пока и не ночуем здесь, как некоторые проекты.

Много-много фотографий акселераторских будней – под катом.

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



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

Landing page важны потому, что именно при взгляде на них потенциальный клиент за секунды решает, хочет ли он купить ваш продукт. А значит, лендинги — ключевой элемент маркетинговой стратегии, который нужно улучшать для повышения конверсии. Продолжаем делиться советами по созданию лендингов, на этот раз — вторая часть статьи Peep Laja, написанной от первого лица. Из нее можно узнать, как выбрать копирайтера для лендинга, и почему стоит избегать использования шаблонов при написании текста и при выборе его дизайна.

Текст на продающей странице – это самое главное

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

Не знаю, как вы, уважаемый читатель, а я всегда поражался контрасту между изяществом базовой идеи, заложенной в концепцию двоичных деревьев поиска, и сложностью реализации сбалансированных двоичных деревьев поиска (красно-черные деревья, АВЛ-деревья, декартовы деревья). Недавно, перелистывая в очередной раз Седжвика [1], нашел описание рандомизированных деревьев поиска (нашлась и оригинальная работа [2]) — настолько простое, что занимает оно всего треть страницы (вставка узлов, еще страница — удаление узлов). Кроме того, при ближайшем рассмотрении обнаружился дополнительный бонус в виде очень красивой реализации операции удаления узлов из дерева поиска. Далее вы найдете описание (с цветными картинками) рандомизированных деревьев поиска, реализация на С++, а также результаты небольшого авторского исследования сбалансированности описываемых деревьев.

^{Длинный материал. Время чтения – около 40 минут.}



Доктор Ричард Хэмминг, профессор морской школы Монтерея в штате Калифорния и отставной учёный Bell Labs, прочёл 7 марта 1986 года очень интересную и стимулирующую лекцию «Вы и ваши исследования» переполненной аудитории примерно из 200 сотрудников и гостей Bellcore на семинаре в серии коллоквиумов в Bell Communications Research. Эта лекция описывает наблюдения Хэмминга в части вопроса «Почему так мало учёных делают значительный вклад в науку и так многие оказываются в долгосрочной перспективе забыты?». В течение своей более чем сорокалетней карьеры, тридцать лет которой прошли в Bell Laboratories, он сделал ряд прямых наблюдений, задавал учёным очень острые вопросы о том, что, как, откуда, почему они делали и что они делали, изучал жизни великих учёных и великие достижения, и вёл интроспекцию и изучал теории креативности. Эта лекция о том, что он узнал о свойствах отдельных учёных, их способностях, чертах, привычках работы, мироощущении и философии.