...

суббота, 14 ноября 2015 г.

Project Naptha — выделяй, копируй и переводи тексты с любых картинок

На hh/gt не нашел ни единого упоминания о этом замечательном расширении для Google Chrome. Хочу поделиться им с сообществом, потому как в последнее время оно помогает мне каждодневно экономить минут 10 — уж очень много скриншотов из социальных сетей на разных языках которые с помощью этого плагина переводятся в два клика.

Встречайте — Project Naptha (Chrome webstore).

image

Список возможностей:

  • копировать текст с картинки
  • выделить весь текст
  • гуглить выделенный текст
  • переводить выделенное (бета)
  • проговорить (TTS) выделенное

Проект был создан Kevin Kwok и представляет собой систему OCR (Optical character recognition), реализованную в JavaScript в виде браузерного расширения.

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

Прежде всего, перед тем как непосредственно распознавание текста началось, нужно определить где собственно находятся блоки с текстом на картинке. Довольно нетривиальная задача, учитывая то, что текст может располагаться поверх совершенно разных фонов и сам по себе иметь разные цвета. Для реализации этого механизма Naptha использует проект Майкрософта Stroke Width Transform (SWT) — эффективный алгоритм, который отталкивается от того, что шрифты обычно имеют примерно равномерную толщину линий (font-weight) и, следовательно, легко отделить блоки текста от остального шума на картинке.

Оригинал:
image

После SWT:
image

Naptha конечно же не распознает каждую картинку на открытой странице — это бы было крайне расточительно по отношению к ресурсам. Вместо этого начинает распознавание расположения блоков текста только после… нет, не наведения мыши на картинку (mouseover) как вы могли подумать, а предположения о том, что курсор будет над картинкой, основываясь на его движении. Дальше Web Workers (мультипоточность в фоне) работают над распознаванием расположения текста на картинке без какого-либо ощутимого торможения браузера.

Когда вы выбрали блок текста и клинкули “Copy Text” (Ctrl+C), он посылается на сервер с Ocrad OCR — движком с открытым кодом для распознавания текста. Ocrad попытается распознать кусок растровой картинки в текст, что может занять пару секунд, и после завершения вернет распознанный текст, который можно будет вставить обычным образом куда угодно (Ctrl+V).

Функция перевода пока что в бете, для того чтобы ее попробывать нужно отправить запрос на их электронный адрес. Предполагается что она будет работать схоже c уже работающим аналогом в Google Translate на мобильных устройствах:

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

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

SolutionCop

Привет хабр! Основная речь пойдет про разработку на .Net, то есть с использованием Microsoft Visual Studio, ReSharper, Nuget и пр.
Я думаю, многие из вас разрабатывали большие решения (в msdn — solution), со множеством подпроектов. И в этом случае нередко становилась проблема синхронизации Nuget пакетов, настроек сборки и т.д. Причем, ReSharper здесь поможет слабо, разве что он тоже начнет путаться во множестве используемых библиотек.
Чтобы проверять исходный код, было сделано Open Source решение — SolutionCop, которое бесплатно для использования.
Для начала приведу парочку примеров, когда не помешали бы проверки наших решений.

Пример 1: разные версии Nuget библиотек.


Например, есть три проекта: exe, dll1 и dll2. exe ссылается на обе библиотеки, каждая из них ссылается, например, на RX. Но dll1 использует RX 2.2.0, а dll2 — RX 2.2.5. На деле, далеко не сразу можно получить ошибку, так как сигнатуры функций более-менее совпадают, более того, MsBuild чаще всего собирает проекты в одном и то же порядке. Однако подобная конфигурация может привести к проблемам, которые появятся после deployment'а, когда все модульные тесты пройдут (т.к. они ссылаются только на свою библиотеку), и когда будет готовиться результирующий набор файлов.

Пример 2: проект ссылается на библиотеку напрямую, а не через Nuget.


Опять возьмем три наших проекта: exe, dll1 и dll2. Допустим, мы также используем еще Jetbrains.Annotations, чтобы размечать код NotNull/CanBeNull аттрибутами и получать симпатичный статический анализ. Но вот незадача: для dll1 мы честно скачали пакет версии 9.2.0, а в dll2 мы просто попросили ReSharper добавить ссылку, что он и сделал. В итоге, в packages.config файле dll2 нет пакета с аттрибутами, а значит, если проект будет собираться в порядке dll2 --> dll1 --> exe, то мы получим ошибку, ведь Nuget пакет скачается только при сборе dll1!
Можно привести еще ряд примеров, когда разные настройки в проектах могут привести к веселым проблемам. Например, проекты для .Net 4.0 и .Net 4.5 могут ссылаться на одинаковые пакеты, но на разные библиотеки в них (см. Nuget help), а значит мы опять будем получать спецэффекты при сборке проектов. Однако лучше перейдем к SolutionCop.

Установка


SolutionCop доступен на Nuget, устанавливается он на уровень всего решения. После установки пакета необходимо создать xml файл с правилами, настроить их и встроить проверяльщика в процедуру сборки на CI.
Пошагово:
  1. Создаем xml файл с правилами (будем проверять сам SolutionCop):

    SolutionCop.exe -s "C:\git\SolutionCop\src\SolutionCop.sln"

    После этой команды возле sln файла появится файл SolutionCop.xml. В нем перечислены все правила, но все они выключены. Рассмотрим их позже.

  2. Настраиваем CI сервер так, чтобы SolutionCop запускался при каждом билде (решение со 100 проектами проверяется 3-4 секунды). Для TeamCity можно даже публиковать статус с более удобном формате. Для всех остальных — придется читать Error Output. Приложение вернет 0, если все правила выполнились успешно. Итак, командная строка для TeamCity:

    SolutionCop.exe -s "C:\git\SolutionCop\src\SolutionCop.sln" -b TeamCity --suppress-success-status-message.

    Последний аргумент необходим в случае, если TeamCity не пишет статуса модульных тестов (несмотря на то, что они выполнялись позднее). Он отключит вывод SolutionCop для случая, если все правила выполнились.


Правила


Итак, SolutionCop настроен, он теперь заглядывает в решение, но ничего не проверяет. А потому перечислю правила, которые могут пригодиться. Детальное описание их использование есть на GitHub, я просто перечислю интересности. Для каждого правила, конечно же, можно задавать исключения и пр.
  • WarningLevel. Проверяет, что все проекты имеют Warning Level не ниже заданного.
  • TreatWarningsAsErrors. Смежное с предыдущим. Тоже синхронизует настройку компиляции.
  • TargetFrameworkVersion. Сихнронизует версию .Net для всех проектов
  • SuppressWarnings. Сихнронизует список предупреждений, на которые компилятор будет закрывать глаза.
  • FilesIncludedIntoProject. Проверяет, что все файлы, находящиеся в папке с проектом, включены в этот проект (дополнительно указыватся расширение). Невероятно полезное правило. Например, один раз при неправильном git merge у нас из проекта с модульными тестами выпало около трети файлов. Заметили это, конечно, не сразу, к тому времени мы упустили уже несколько багов. Также помогает с очисткой репозитороя, чтобы избежать кучи висящих файлов, которые никто не использует.
  • ReferenceNuGetPackagesOnly. Запрещает динамически линковаться на библиотеки, которые не добавлены как NuGet пакеты. По факту это исправление примера 2 выше.
  • NuGetPackagesUsage. Определяет Nuget пакеты, которые можно использовать. Эта настройка нужна для задач, когда в продукте есть несколько команд, у каждой свой репозиторий, они ссылаются друг на друга, а также на некоторые общие компоненты. И чтобы избежать проблем при объединении кода, можно определить общие правила для всех: какие версии пакетов кому можно использовать. В этом случае все правила хранятся отдельно от кода, в отдельном репозитории.
  • SameNuGetPackageVersions. Запрещает использование разных Nuget пакетов в решении. Исправление ошибки из примера 1.
  • NuGetAutomaticPackagesRestore. Проверяет, что все проекты восстанавливают Nuget пакеты в процессе сборки. Иначе разный порядок компиляции на CI сервере может привести к тому, что nuget пакеты не подгрузятся вовремя, так как какой-то проект пользовался тем, что его зависимости загружают другие проекты.

На деле, в SolutionCop есть и ряд других правил, которые помогут вычищать код. Я постарался перечислить те, которые могут понадобиться почти всем, кто разрабатывает на .Net.

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Прочь из моей головы. GTD в разработке

Если на вашем столе стоит чашка остывшего желанного кофе или чая, значит, что-то не так. Во всяком случае, так наверняка подумал бы Дэвид Аллен, автор знаменитого метода GTD (Getting Things Done). Мы хватаемся за тысячу дел, пытаясь попутно не забыть про бытовые мелочи, часто забываем о цели, но помним о неотвратимо приближающихся дедлайнах. Порой страх перед лавиной задач буквально парализует мозг и наступают апатия, прокрастинация, депрессия. Работа в такие моменты движется медленно, кажется, даже курсор мыши еле ползёт по монитору. Такая ситуация тем опаснее, чем больше человек работает в команде, особенно, если речь идёт о команде разработчиков.


Идея пригласить на нашу конференцию GeekWeek-2015 Дэвида Аллена была хоть и неожиданной, но неслучайной. Личностная, на первый взгляд, концепция GTD, даёт неплохие рекомендации для каждого разработчика в отдельности и процесса разработки в целом. Конечно, метод GTD не столь «заточен» под процесс разработки ПО, как agile, но тем не менее, способен его дополнить или стать первым шагом на пути перехода команды к гибкой методологии разработки. Какой же он, GTD для программиста?

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

Один в поле воин


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

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

Устанавливаем фильтры на список дел


Прежде всего, нужно установить ограничения, выбрав основное среди всех задач. Оставляя главное, вы высвобождаете время и силы и создаёте импульс для действий с гораздо меньшими трудозатратами, чем когда вы держите в голове все мелочи. Есть рутина, есть важные проекты, есть планы на будущее. При этом во всех перечисленных категориях есть главное. Чтобы его выделить, нужно выполнить несколько шагов:
  • выбрать начатые, но не завершённые задачи;
  • выбрать дела, вызывающие наибольшее беспокойство;
  • выбрать дела, которые не хочется выполнять и которые всё время откладываются;
  • выбрать рутинные дела, в том числе бытовые.

Как правило, основное находится первых трёх группах. Соответственно, первоочередное внимание следует уделить беспокоящим и незавершённым делам — ведь не даром точный перевод Getting Things Done — «довести дела до завершения».

Упорядочиваем коммуникацию


Неважно, фрилансер или программист, работает удалённо или в команде, он постоянно находится в поле коммуникации: звонки заказчиков, вопросы руководства, запросы пользователей и коллег, информационные сообщения от поставщиков SDK и проч… Эти коммуникации нельзя назвать малозначительными, но их нужно уметь грамотно обрабатывать.
  • Перестаньте проверять e-mail каждые 5 минут — установите всплывающие оповещения, на которые можно глянуть краем глаза. Разместите почту по папкам и прочитывайте по мере актуализации в конкретный момент.
  • Разделите все коммуникации по контексту: Skype, мобильные звонки, городской телефон, общение через почту и т.д… Отведите определённое время на коммуникацию внутри каждого канала.
  • Проверьте рабочие и личные чаты. Возможно, если вам без конца пишет ваш новый сотрудник или задаёт одни и те же рабочие вопросы старый коллега, стоит попросить их подготовить вопросы, выделить время на общение и разъяснить все сложные моменты.
  • Понаблюдайте за своим веб-браузером. Разработчики часто смотрят профильные темы на форумах или специализированных сайтах. Там их подстерегают интересные темы и обсуждения, не имеющие никакого отношения к текущей задаче. Лучше отложить чтение действительно интересной темы, воспользовавшись закладками в браузере или специальными утилитами для хранения ссылок (например, дополнение Pocket, которое можно также установить как приложение на мобильном устройстве и синхронизировать закладки).
  • Заведите записную книжку и/или приложение, где вы будете записывать все задачи с метками срочности и важности. GTD для управления делами вводит понятия времени, контекста (места), действия. Чтобы правильно расставить приоритеты задач, представьте себе простой фильтр, как в Excel, например. Присвойте каждой задаче параметр времени (по часам или времени суток), места (дом, работа, улица, спортзал, магазин и т.д.). А затем разделите задачи примерно таким образом: «запросить комментарии к ТЗ — работа — 14:00» или «позвонить в шиномонтаж — улица — вечер». Для подобных записей существует много приложений: от планировщика заданий в Windows, который можно использовать для своих целей до Evernote, Rainlendar и тщательно прописанных напоминаний на смартфоне.

Уверенность в том, что у вас есть такой список, гарантированно снизит уровень тревожности и поможет сосредоточиться на решении каждой из задач.

Есть и более глобальная проблема, которая также затрагивает разработчиков любого типа занятости. Сегодня почти каждую неделю выходят новые инструменты, гайды, утилиты для разработчиков, то и дело появляются сообщения о новых версиях фреймворков, новых библиотеках и даже новых языках программирования. Вся эта информация вызывает чрезвычайный интерес профессионалов, а иногда даже увлекает и заставляет попробовать что-то новое (создать простое мобильное приложение, написать «Hello, world!» на Brainfuck или собрать новый опенсорсный проект). Выход один: распределять интересы по мере их значимости по отношению к текущим проектам, краткосрочным и долгосрочным целям. Фокусировка на одной задаче даёт возможность повысить личную продуктивность, освободить время и приступить к изучению новой информации.

5 шагов оптимизации


Метод GTD выделяет пять стадий работы над списком дел.

Сбор информации. Нужно собрать все задачи— просто взять и записать ручкой или в текстовый файл все свои рутинные, незавершённые, глобальные дела. При этом важно помнить, что, например, за задачей «Написать отчёт в Fast Report для ООО «Снеговик» скрывается несколько важных и требующих внимания подзадач: собрать требования с клиента, составить и утвердить ТЗ, запросить массив данных для тестирования отчёта и т.д… Необходимо записывать абсолютно все задачи — чуть позже вы их сгруппируете.
Обратите внимание не только на те проекты, которые есть в памяти, но и на те, которые находятся в компьютере — зачастую там не меньше хаоса, чем в мыслях. Стоит разделить файлы по папкам, соответствующим каждому проекту, отделить личные документы от рабочих.

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


Классический алгоритм обработки по GTD

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

  • Отложить несрочные задачи, например, изучение непрофильных материалов, никак не связанных с текущей работой.
  • По возможности делегировать задачи, например, коллегам или фрилансерам. Если вы быстро и эффективно пишете код, но не очень хорошо справляетесь с задачами создания сайта, рекламы или дизайна, обратитесь к профессионалам. Даже, если это ваш собственный проект, вложение в чужую качественную работу быстро окупится.
  • Научиться говорить «нет». Это, пожалуй, один из самых сложных навыков: всегда найдутся десятки знакомых, у которых слетела Windows, закралась ошибка в код, требует прошивки Android и молит о джейлбрейке iPhone. Эти небольшие задачи отнимают массу времени. Если не хотите портить отношения, найдите несколько доступных мануалов в Сети и отправляйте страждущим ссылки.

Организация списка. После того, как пройдены два первых и самых сложных этапа, необходимо организовать работу с задачами. Тут можно воспользоваться простым правилом: разделить время на недели, в конце недели пересматривать список и создавать новый. Все задачи стоит разделять по срокам выполнения и приоритету. Для ведения задач можно использовать любое из понравившихся приложений: это и мобильные OneNote и Evernote, и Asana, и Redmine, и Google Календарь, и проч…

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

Часть 1

Часть 2

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

Ревизия сделанного. На этом этапе необходимо отметить сделанное, проанализировать причины провалов, создать план на следующий этап (например, неделю).

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

Вот несколько советов, как использовать принципы GTD, если вы разработчик в команде или работаете самостоятельно.

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

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

Один в поле не воин


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

Однако зачастую все труды по составлению диаграммы ресурсов и занятости оказываются напрасными. Увязывая GTD с разработкой ПО, о диаграмме Ганта отлично написал Роберт Пик, евангелист GTD и CTO консалтинговой компании Дэвида Аллена, который руководил техническими проектами и понимает тему едва ли хуже самого CEO:

«Я видел столько времени, энергии и денег, канувших в сложные диаграммы Ганта, которые были уничтожены по первому щелчку пальцев руководителя. Любую компанию, делающую ставку на АВС-коды приоритетов и жёсткие узды для программистов для того, чтобы остаться в арьергарде разработки ПО, ждёт горькое разочарование».


Он же раскрывает суть концепции. Дело в том, что она направлена не столько на планирование, сколько на умение вернуться к точке срыва. Поясним подробнее. В жизни любого человека и любой команды случаются моменты, когда они отходят от намеченных целей и вся деятельность погружается в хаос. Это может происходить как по внешним причинам, так и по причинам, связанным с отдельными внутренними воздействиями: временной сменой курса развития проекта, появлением нового инвестора с новым видением, перерывом на сверхсрочную работу (например, подготовку к выставке). Задача GTD в команде — легко вернуться к точке, в которой пришлось отойти от плана работы и продолжить действовать в прежнем режиме.

«Mind sweep (очистка памяти, очистка ума — прим. пер.) составляющая GTD, достаточно проста, Дэвид (Аллен — прим.пер.) зачастую упоминает её как своего рода дамп памяти для «психической оперативки». Это как будто вы периодически сверяетесь со своим собственным мозгом, чтобы увидеть то, что удерживает ваше внимание, вытащить и посмотреть на это. Это как будто вы собираете эти списки возможностей (проекты и следующие действия), которые служат вам подстраховкой для уверенности в том, что всё, что вы делаете, вы делаете правильно и в сочетании с правилом двух минут (если ты можешь что-то сделать менее, чем за 2 минуты, сделай это — прим. пер.) и мышлением, нацеленным на следующее действие, даёт вам статический слепок вашего рабочего состояния, с помощью которого вы сможете легко вернуться к тому моменту, когда вы прервались».


В команде разработчика есть четыре основных действия, которые сами по себе выступают как элементы командного GTD.
  1. Регрессионное тестирование — тестируются уже исправленные участки исходного кода, а также работоспособность функциональности, связанной с изменённым кодом. Как часть экстремального программирования, оно иллюстрирует GTD с точки зрения повторяемости, ревизии и однозначности действий.
  2. Работа с документацией — создание и тестирование документации позволяет как раз перенести важные знания и задачи на бумагу. Их не нужно держать в голове ни пользователям, ни тестировщикам, ни разработчикам — в случае необходимости можно обратиться к документации и уточнить неясный момент или найти ответ на вопрос о работе программы.
  3. Рефакторинг кода — процесс улучшения кода без изменения функциональности. Приверженцы экстремального программирования проводят периодический рефакторинг с целью улучшения производительности программы, её понимания и читабельности кода. Есть компании и команды, которые избегают рефакторинга. В большинстве случаев это связано с опасениями, что изменения в коде приведут к краху в в системе. Как правило, такой подход приводит к косности и устареванию программы.
  4. Мозговой штурм. Процесс, который в той или иной форме происходит в любой команде. Это как раз сбор информации и идей. В ходе мозгового штурма и по его итогам могут также создаваться ассоциативные карты mindmap.

В большинстве случаев программист на работе выполняет гораздо больше задач, чем обычное написание кода. Более того, чем больше у него опыта и квалификации, тем больше разнородных задач на него возлагается. В какой-то момент наступает кризис, когда обязанности и обязательства начинают тяготить работника и значительно снижают его продуктивность. Очевидно, что с этим можно и нужно бороться, причём не директивными методами и репрессивными мерами, а с помощью GTD, который нацелен на эволюционное изменение подхода к работе. Многочисленные отзывы тех, кто пробовал этот метод, рассказывают о значительных сложностях в начале и не менее значительных успехах в итоге процесса. В конце концов, говорят, что привычка формируется за 21 день. Почему бы не попробовать?

P.S.: Бесплатно послушать онлайн-выступление автора метода GTD Дэвида Аллена и задать ему вопросы можно будет в рамках конференции GeekWeek-2015 ​17 ноября (вторник) в 19:15​ МСК. Он расскажет о подходе GTD к решению проблемы информационной перегрузки и поделится результатами последних исследований в области человеческой продуктивности.

P. P. S.: Информация для тех, кто хочет познакомиться со спикером лично — в этом году Дэвид Аллен приезжает в Москву с мастер-классом.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Moscow Python Meetup №30

19-го ноября мы снова соберемся в уютном офисе компании Rambler&Co.

image

На встрече нас ждут целых 4 доклада.
Артём Малышев (F-Technology). Гексагональная архитектура в приложениях Django.

«Как не превратить свой проект в груду урлов? Как не потерять расширяемость с ростом кодовой базы? Как писать поддерживаемый код? Об этих проблемах и их возможных решениях на примере Django расскажет и покажет Малышев Артем.»

Сергей Жерновой (IBM) Платформа IBM Bluemix и зачем она питонистам.

«Облачная платформа IBM Bluemix для разработки и разработчиков. Зачем она нужна и как устроена. Как развернуть приложение на python за 5 минут.»

Лев Тонких (Rambler). Анализ дружеских связей VK с помощью Python.

«Все началось со статьи, в которой рассказывалось о построении социальных графов с помощью Wolfram Mathematica. Тогда не смог пройти мимо, и мой доклад будет о том, как все это сделать на любимом Python.»

Павел Петлинский (Rambler). asyncio в Python. Как устроено и зачем нужно?

«В python 3.4 появился asyncio. До сих пор многие разработчики не знают, что это такое, как реализуется асинхронность в Python и в чем её сильные и слабые места. Повторим пройденное и заглянем под капот.»

Ну и, конечно, по традиции в программе общение с единомышленниками и новые встречи!

Зарегистрироваться можно тут

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Пишем простую виртуальную машину на Python

Привет! Сейчас расскажу как написать простую виртуальную машину на Python. Надеюсь кто-то найдет эту статью интересной.

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

У нас будет стековая машина, и она будет использовать два стека:

  • стек значений, куда будут складываться/забираться временные значения вычислений и результаты вызова функций
  • стек вызовов, куда мы будем запоминать, в какое место кода нужно вернуться после завершения функции

Сам код будет представлять собой list из команд, которые тоже являются list'ами:
code = [
  ['val', 2], # положить 2 на стек
  ['val', 3], # положить 3 на стек
  ['get', '*'], # положить на стек значение переменной с названием * (функция умножения)
  ['call', 2], # взять с вершины стека функцию и вызвать ее с 2 аргументами со стека (они тоже вынимаются), результат функции кладется на стек
  ['get', 'puts'], # положить функцию печати
  ['call', 1], # напечатать
]


Реализуем машину в виде функции:
# ops - список команд
# env - окружение в котором исполняется код
def vm(ops, env={}): 
    # нам нужен класс замыкания, чтобы мы могли понять что на стеке действительно лежит функция
    class closure:
        # pc - "адрес" кода функции (индекс первой команды в ops)
        # env - окружение в котором было создано замыкание
        def __init__(self, pc, env): 
            self.pc, self.env = pc, env
    # pc - индекс следующей исполняемой команды
    # stack - стек значений
    # fstack (frame stack) - стек вызовов функций
    pc, stack, fstack = 0, [], []

Перед тем как запустить основной цикл интерпретатора, нам нужно вычислить индексы метод в коде. Меткой у нас будет специальная команда label: ['label', 'label-name']

labels = {op[1]: index for index, op in enumerate(ops) if op[0] == 'label'}

Основной цикл:

    while pc < len(ops):
        # берем текущую команду и ее аргументы, увеличиваем указатель
        op, args, pc = ops[pc][0], ops[pc][1:], pc + 1
        arg = args[0] if args else None
        # игнорировать команду label
        if op == 'label':
            pass
        # положить знаение аргумента на стек
        elif op == 'val':
            stack.append(arg)
        # присовить значение переменной либо положить значение переменной на стек
        elif op == 'set' or op == 'get':


Здесь нужно чуть рассказать об устройстве окружений. У нас они являются объектами dict, в ключах которого хранятся названия переменных, а в значениях значения + в ключе '' (пустая строка) хранится «указатель» на родительское окружение. Поэтму чтобы найти окружение в котором была определена нужная нам переменная, мы должны искать сначала в текущем окружении, и если не нашли, то искать в родительском и так далее:
            e = env
            while e is not None and arg not in e:
                e = e[''] if '' in e else None # ключа '' может и не быть, это значит что нет родительского окружения
            # изменить значение переменной, если таковая была была определена, либо определить ее в текущем окружении
            if op == 'set': (env if e is None else e)[arg] = stack.pop()
            # положить на стек значение, либо вывести предупреждение о неопределенной переменной
            elif op == 'get':
                if e: stack.append(e[arg])
                else: print('undefined variable %s' % arg)

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

make-person = fn(name, age) {
    return fn() { // запомнила значения name и age
        print name, age++;
    };
};
vasya = make-person("Vasily", 20);
petya = make-person("Peter", 24);
vasya(); // Vasily 20
vasya(); // Vasily 21
petya(); // Peter 24
petya(); // Peter 25

Созданием замыкания у нас будет заниматься команда fn. Все чт она делает: кладет на стек объект класса closure, у котором указаны адрес кода фукнции (на самом деле адрес метки с названием нужной фукнции) и текущее окружение.

        elif op == 'fn':
            stack.append(closure(labels[arg], env))


Теперь о вызовах функций.
Фукнции у нас могут быть двух типов:
  • встроенные функции, например +, -, sin, cos
  • определенные в коде

Обрабатываться они будут по-разному:
  • встроенная функция просто вызывается виртуальной машиной и результат фукнции кладется на стек.
  • чтобы вызвать определенную пользоватем фукнцию мы должны запомнить место, куда должно вернуться управление после того как фукнция закончит свое выполнение. Короче это означает мы должны сохранить значение pc и env на стеке вызовов, изменить pc на «адрес» кода функции, создать новое (локальное) окружение, в котором будет работать фукнция, родительским окружением укажем окружение, запомненное во время создания замыкания

Во время вызова функций мы будем указывать кол-во переданных аргументов n, а наш интерпретатор возьмет n элементов со стека, сделает из них массив и положит в стек, таким образом у нас функции могут принимать любое кол-во аргументов. Функции в своем коде сами будут должны разбирать массив аргументов и устанавливать соответствующие переменные.
Команда ret возвращает управление в место откуда она была вызвана.
        # простой вызов либо вызов в хвостовой позиции
        elif op == 'call' or op == 'tcall': 
            # берем функцию
            fn = stack.pop() 
            # если указано кол-во аргументов то мы должны сделать из них массив
            if args and arg: 
                stack.append(popn(arg))
            # определенная в коде функция
            if isinstance(fn, closure):
                # если это вызов фукнции в нехвостовой позиции, то запомнить куда вернуть управление
                if op == 'call':
                    fstack.append((pc, env))
                # перейти в код фукнции
                pc, env = fn.pc, {'': fn.env}
            # встроенная функция
            elif hasattr(fn, '__call__'):
                stack.append(fn(stack.pop()))
        # команда разбора аргументов
        elif op == 'args':
            vals = stack.pop()
            if len(args) != len(vals): print 'warning: wrong arguments count: %d expected, %d given' % (len(args), len(vals))
            env.update(dict(zip(args, vals)))
        # return
        elif op == 'ret':
            # если return встретился на верхнем уровне, это означает конец выполнения программы
            if not fstack: break
            # возвращаем управление куда надо
            pc, env = fstack.pop()

Полный код с лексером (для удобства) и тестовым примером: http://ift.tt/1j03obq

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Facebook помогает узнать все ли хорошо у ваших друзей в случае ЧП

сегодня в 04:21

В Париже сегодня(13-14 ноября) ночью произошло 7 террористических атак.
Читать можно тут
Если у вас есть друзья во Франции, Фэйсбук включил специальный интерфейс, позволяющий узнать все ли у них хорошо и не коснулась ли их трагедия.

http://ift.tt/1zjAE5h
Если вы сами находитесь в Париже сейчас(искренне надеюсь, что вас трагедия обошла стороной), по этой же ссылке, вы можете известить всех своих друзей, что у вас все хорошо. Извещения друзьям будут приходить в виде Push уведомлений.
Также, есть возможность отмечать друзей, с которыми вы уже успели связаться и знаете, что они в безопастности.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

[unable to retrieve full-text content]

Пример решения типичной ООП задачи на языке Go

Недавно попалась на глаза занимательная статья с аналогичным названием о языке Haskell. Автор предлагал читателю проследить за мыслью программиста, решающего типичную ООП задачу но в Хаскеле. Помимо очевидной пользы расширения представлений читателей о том, что ООП — это отнюдь не «классы» и «наследование», подобные статьи полезны для понимания того, как правильно пользоваться языком. Предлагаю читателю решить ту же самую задачу, но на языке Go, в котором ООП тоже реализован непривычно.

Задача


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

Формат вывода информации, на примере прямоугольника и круга, должен быть вот таким:

paint rectangle, Rect {left = 10, top = 20, right = 600, bottom = 400}
paint circle, radius=150 and centre=(50,300)


Кроме того, примитивы нужно уметь объединить в однородный список.

Решение


Структуры и свойства

Начнем с очевидного — с объявления примитивов и их свойств. За свойства в Go отвечают структуры, поэтому просто объявим нужные поля для примитивов Rectangle и Circle:
type Rectangle struct {
        Left, Right, Top, Bottom int64
}

type Circle struct {
        X, Y, Radius int64
}


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

Названия полей и методов будем писать с большой буквы, так как это не библиотека, а исполняемая программа, и видимость за пределами пакета нам не важна (в Go название с большой буквы — это аналог public, с маленькой — private).

Интерфейсы и поведение

Далее, по определению оригинальной задачи, примитивы должны уметь отдавать информацию о себе в определенном формате и отдавать значение площади примитива. Как же мы сделаем это в Go, если у нас нет классов и «нормального ООП»?

Тут в Go даже не приходится гадать, поскольку в языке очень четко разделено определение «свойств» и «поведения». Свойства — это структуры, поведение — это интерфейсы. Этот простой и мощный концепт сразу же дает нам ответ, что делать дальше. Определяем нужный интерфейс с нужными методами:

type Figure interface {
        Say() string
        Square() float64
}


Выбор имени интерфейса (Figure) тут продиктован оригинальным примером и задачей, но обычно в Go интерфейсы, особенно с одним методом, называют с суффиксом -er — Reader, Painter, Stringer и так далее. По идее, имя должно помогать понять назначение интерфейса и отражать его поведение. Но в данном случае Figure достаточно неплохо подходит и описывает сущность «фигуры» или «графического примитива».
Методы

Теперь, чтобы типы Rectangle и Circle стали «фигурами», они должны удовлетворять интерфейсу Figure, тоесть для них должны быть определены методы Say и Square. Давайте их напишем:
func (r Rectangle) Say() string {
        return fmt.Sprintf("rectangle, Rect {left=%d,top=%d,right=%d,bottom=%d)", r.Left, r.Top, r.Right, r.Bottom)
}

func (r Rectangle) Square() float64 {
        return math.Abs(float64((r.Right - r.Left) * (r.Top - r.Bottom)))
}

func (c Circle) Say() string {
        return fmt.Sprintf("circle, radius=%d and centre=(%d,%d)", c.Radius, c.X, c.Y)
}

func (c Circle) Square() float64 {
        return math.Pi * float64(c.Radius^2)
}


На что здесь стоит обратить внимание — на ресивер метода, который может быть значением (как сейчас — «c Circle»), а может быть указателем "(c *Circle)". Общее правило тут такое — если метод должен изменять значение c или если Circle — большущщая структура, занимающая много места в памяти — тогда использовать указатель. В остальных случаях, будет дешевле и эффективней передавать значение в качестве ресивера метода.

Более опытные гоферы заметят, что метод Say в точности похож на стандартный интерфейс Stringer, который используется в стандартной библиотеке, пакетом fmt в том числе. Поэтому можно переименовать Say в Stringer, убрать метод Say из интерфейса Figure и дальше просто передавать объект данного типа в функции fmt для вывода, но пока что оставим так, для большей ясности и схожести с оригинальным решением.

Конструкторы

Собственно, все — теперь можно создавать структуру Rectangle или Circle, инициализировать ее значения, сохранять в слайсе (динамический массив в Go) типа []Figure и передавать функции, принимающей Figure и вызывающей методы Say или Square для дальнейшей работы с нашими графическими примитивами. К примеру, вот так:
func main() {
        figures := []Figure{
                NewRectangle(10, 20, 600, 400),
                NewCircle(50, 300, 150),
        }
        for _, figure := range figures {
                fmt.Println(figure.Say())
        }
}

func NewRectangle(left, top, right, bottom int64) *Rectangle {
        return &Rectangle{
                Left:   left,
                Top:    top,
                Right:  right,
                Bottom: bottom,
        }
}

func NewCircle(x, y, radius int64) *Circle {
        return &Circle{
                X:      x,
                Y:      y,
                Radius: radius,
        }
}


Методы NewRectangle и NewCircle — просто функции-конструкторы, которые создают новые значения нужного типа, инициализируя их. Это обычная практика в Go, такие конструкторы нередко еще могут возвращать ошибку, если конструктор делает более сложные вещи, тогда сигнатура выглядит как-нибудь так:
func NewCircle(x, y, radius int64) (*Circle, error) {...}


Также вы можете встретить сигнатуры с приставкой Must вместо New — MustCircle(x, y, radius int64) *Circle — обычно это означает, что функция выбросит панику, в случае ошибки.
Углубляемся в тему

Наблюдательный читатель может заметить, что мы кладем в массив фигур ([]Figure) переменные типов *Rectangle и *Circle (то есть, указатель на Rectangle и указатель на Circle), хотя методы мы таки определили на значение, а не на указатель (func (c Circle) Say() string). Но это правильный код, так Go работает с ресиверами методов, упрощая программистам жизнь — если тип реализует интерфейс, то «указатель на этот тип» тоже его реализует. Ведь логично, не так ли? Но чтобы не заставлять программиста лишний раз разыменовывать указатель, чтобы сказать компилятору «вызови метод» — Go компилятор сделает это сам. А вот обратную сторону — что тоже очевидно — такое не сработает. Если интерфейсный метод реализован для «указателя на тип», то вызов метода от переменной не-указателя вернет ошибку компиляции.

Чтобы вызвать метод Say у каждого примитива, мы просто проходимся по слайсу с помощью ключевого слова range и печатаем вывод метода Say(). Важно понимать, что каждая переменная интерфейсного типа Figure содержит внутри информацию о «конкретном» типе. figure в цикле всегда является типом Figure, и, одновременно, либо Rectangle, либо Circle. Это справедливо для всех случаев, когда вы работает с интерфейсными типами, даже с пустыми интерфейсами (interface{}).

Усложняем код


Далее автор усложняет задачу, добавляя новый примитив «закругленный прямоугольник» — RoundRectangle. Это, по сути, тот же примитив Rectangle, но с дополнительным свойством «радиус закругления». При этом, чтобы избежать дубликации кода, мы должны как-то переиспользовать уже готовый код Rectangle.

Опять же, Go дает абсолютно четкий ответ, как это делать — никаких «множественных путей сделать это» тут нет. И этот ответ — embedding, или «встраивание» одного типа в другой. Вот так:

type RoundRectangle struct {
        Rectangle
        RoundRadius int64
}


Мы определяем новый тип-структуру, который уже содержит все свойства типа Rectangle плюс одно новое — RoundRadius. Более того, RoundRectangle уже автоматически удовлетворяет интерфейс Figure, так как его удовлетворяет встроенный Rectangle. Но мы можем переопределять функции, и вызывать функции встроенного типа напрямую, если нужно. Вот как это выглядит:
func NewRoundRectangle(left, top, right, bottom, round int64) *RoundRectangle {
        return &RoundRectangle{
                *NewRectangle(left, top, right, bottom),
                round,
        }
}

func (r RoundRectangle) Say() string {
        return fmt.Sprintf("round rectangle, %s and roundRadius=%d", r.Rectangle.Say(), r.RoundRadius)
}


Конструктор типа использует конструктор NewRectangle, при этом разыменовывая указатель (так как мы встраиваем Rectangle, а не указатель на Rectangle), а метод Say вызывает r.Rectangle.Say(), чтобы вывод был точно таким же как и для Rectangle, без дубликации кода.

Встраивание типов (embedding) в Go это очень мощный инструмент, можно даже встраивать интерфейсы в интерфейсы, но для нашей задачи это не нужно. Предлагаю читателю познакомиться с этим самостоятельно.

Теперь просто добавим в слайс новый примитив:

figures := []Figure{
                NewRectangle(10, 20, 600, 400),
                NewCircle(50, 300, 150),
                NewRoundRectangle(30, 40, 500, 200, 5),
}


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

Финальные правки


Хотя этот код и является синтетическим примером, но опишу пару моментов, которые я бы делал дальше. Первым делом — я напишу комментарии ко всем методам, даже к конструкторам. Последнее, конечно, не обязательно, но мне нравится идея того, что достаточно написать по одной строчке, чтобы получить документацию ко всему пакету с помощью go doc, даже если она пока не нужна, и вообще, это не библиотека, а запускаемая программа. Но, если в будущем подобный код будет выделен в отдельный пакет-библиотеку, то мы автоматом получим документированный пакет. Пусть даже пока что описания банальные, но мне не сложно потратить 5 секунд на написание одной строки текста, зато есть чувство «полноты» кода, да и линтеры (go vet) не будут ругаться, что тоже приятно.

Далее, логичным выглядит разнести код на несколько отдельных файлов — определение интерфейса и main() оставить в main.go, а для каждого примитива и его функций создать отдельные файлы — circle.go, rectangle.go и roundrectangle.go. Описание интерфейса, впрочем, тоже можно вынести в отдельный файл.

Финальным штрихом будет прогонка через GoMetaLinter — это пакет, запускающий параллельно все линтеры и статические анализаторы кода, которые умеют много чего ловить и подсказывать, позволяя делать код еще лучше, чище и читабельней. Если gometalinter не вывел сообщений — отлично, код достаточно чист.

Полный код тут
main.go:
package main

import "fmt"

// Figure describes graphical primitive, which can Say
// own information and return it's Square.
type Figure interface {
        Say() string
        Square() float64
}

func main() {
        figures := []Figure{
                NewRectangle(10, 20, 600, 400),
                NewCircle(50, 300, 150),
                NewRoundRectangle(30, 40, 500, 200, 5),
        }
        for _, figure := range figures {
                fmt.Println(figure.Say())
        }
}


rectangle.go:
package main

import (
        "fmt"
        "math"
)

// Rectangle defines graphical primitive for drawing rectangles.
type Rectangle struct {
        Left, Right, Top, Bottom int64
}

// NewRectangle inits new Rectangle.
func NewRectangle(left, top, right, bottom int64) *Rectangle {
        return &Rectangle{
                Left:   left,
                Top:    top,
                Right:  right,
                Bottom: bottom,
        }
}

// Say returns rectangle details in special format. Implements Figure.
func (r Rectangle) Say() string {
        return fmt.Sprintf("rectangle, Rect {left=%d,top=%d,right=%d,bottom=%d)", r.Left, r.Top, r.Right, r.Bottom)
}

// Square returns square of the rectangle. Implements Figure.
func (r Rectangle) Square() float64 {
        return math.Abs(float64((r.Right - r.Left) * (r.Top - r.Bottom)))
}


circle.go:
package main

import (
        "fmt"
        "math"
)

// Circle defines graphical primitive for drawing circles.
type Circle struct {
        X, Y, Radius int64
}

// NewCircle inits new Circle.
func NewCircle(x, y, radius int64) *Circle {
        return &Circle{
                X:      x,
                Y:      y,
                Radius: radius,
        }
}

// Say returns circle details in special format. Implements Figure.
func (c Circle) Say() string {
        return fmt.Sprintf("circle, radius=%d and centre=(%d,%d)", c.Radius, c.X, c.Y)
}

// Square returns square of the circle. Implements Figure.
func (c Circle) Square() float64 {
        return math.Pi * float64(c.Radius^2)
}


roundrectangle.go:
package main

import "fmt"

// RoundRectangle defines graphical primitive for drawing rounded rectangles.
type RoundRectangle struct {
        Rectangle
        RoundRadius int64
}

// NewRoundRectangle inits new Round Rectangle and underlying Rectangle.
func NewRoundRectangle(left, top, right, bottom, round int64) *RoundRectangle {
        return &RoundRectangle{
                *NewRectangle(left, top, right, bottom),
                round,
        }
}

// Say returns round rectangle details in special format. Implements Figure.
func (r RoundRectangle) Say() string {
        return fmt.Sprintf("round rectangle, %s and roundRadius=%d", r.Rectangle.Say(), r.RoundRadius)
}



Выводы


Надеюсь, статья помогла проследить за ходом мысли, обратить внимание на некоторые аспекты Go. Go именно такой — прямолинейный и не способствующий трате времени на размышления, какими бы фичами решить ту или иную задачу. Его простота и минимализм заключается в том, чтобы предоставлять как раз только то, что необходимо для решения практических задач. Никаких ЭкзистенциальныхКвантизаций, только тщательно отобранный набор строительных блоков в духе философии Unix.

Кроме того, надеюсь, новичкам стало более понятно, как можно реализовывать ООП без классов и наследования. На эту тему есть на Хабре пара статей, в которых более подробно рассматривается ООП в Go, и даже небольшой исторический экскурс в то, что такое ООП на самом деле.

И, конечно, было бы интересно увидеть ответы-продолжения на оригинальную статью на других новых и не очень языках. Мне, например, было жутко интересно «подсмотреть» за ходом мысли в оригинальной статье, и, я более чем уверен, что это из лучших способов учиться и осваивать новые вещи. Отдельное спасибо автору оригинального материала (@KolodeznyDiver).

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

пятница, 13 ноября 2015 г.

«Черная» пятница: выделенные серверы в Нидерландах по специальным ценам, дополнительная 10% скидка на все услуги для читателей habrahabr

Приветствую! Вчера я рассказал о нас в статье «ua-hosting.company» или как стать хостинг-провайдером с нуля, сегодня хотел бы позволить себе немного маркетинга и в тоже время предоставить дополнительные скидки для всей IT-аудитории Habrahabr, в знак благодарности, ведь мы улучшаем свои познания, в частности благодаря Вам, так как постоянно работаем над тематическими статьями для corp-блога.

Спасибо огромное, что Вы с нами и читаете нас, будем стараться радовать Вас и в будущем! А если чем-то расстроили — простите, никто не идеален, мы не исключение, будем работать над своими недостатками в дальнейшем.

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

А так как сегодня «черная» пятница (в смысле 13-е ноября, пятница), мы решили сделать день чуть более удачным и снизили все цены на веб-сайте до минимума, добавив особо интересные предложения на выделенные серверы с ежемесячной и долгосрочной оплатой:




Скидки действительны даже на серверы с моментальной активацией:





Веб-мастера, которым ресурсов выделенного сервера слишком много, рекомендую обратить внимание на наши виртуальные серверы на облачной платформе в Нидерландах и США. Вы можете получить от 1-го ядра процессора, 1 ГБ оперативной памяти, 60 ГБ SSD накопителя и от 4 ТБ трафика на скорости 1 Гбит / с менее, чем за $4 в месяц, что согласитесь — даром!

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

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Конкурс по программированию на JS: Почтовые фильтры

Компания Hola снова объявляет конкурс по программированию на JS с солидным призовым фондом:
  1. Первое место: 1500 USD
  2. Второе место: 1000 USD
  3. Третье место: 500 USD
  4. Возможно, мы решим отметить чьё-то чрезвычайно оригинальное решение специальным призом в 350 USD.
  5. Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите такую же сумму, как и он.

Мы ищем талантливых программистов, поэтому авторы интересных решений будут приглашены на собеседования.

Правила


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

Условия конкурса на английском языке размещены на нашем сайте. Ниже — перевод на русский язык.

  • Отправляйте решения на challengejs@hola.org.
  • Решения принимаются до 25 декабря 2015, 23:59:59 UTC.
  • Победители будут объявлены 8 января 2015.
  • Можно отправлять решения многократно, но от каждого участника будет рассмотрено только самое последнее решение, отправленное до окончания срока приёма работ.
  • Для тестирования мы будем использовать Node.js v5.0.0 (стабильная версия на момент публикации).
  • Ваше решение должно состоять из единственного файла на JS.
  • Решение должно быть на чистом JS. Если Вы предпочитаете CoffeeScript или подобные языки, необходимо оттранслировать решение в JS перед отправкой. Мы приветствуем (но не требуем) отправку оригинала вместе с результатом трансляции (но не вместо).
  • Нельзя загружать никаких модулей, даже тех, что входят в стандартный комплект Node.js.
  • Мы будем тестировать решения на корректность и производительность. Только решения, прошедшие тестирование на корректность, будут допущены к тестированию на производительность. Победит самое быстрое из корректных решений.
  • Все работы участников, а также наши тесты на корректность и производительность, будут опубликованы при подведении итогов.
  • Подводя итоги, мы опубликуем Ваше полное имя (или псевдоним, если Вы подпишетесь им), но не адрес электронной почты.
  • Запрещается публикация участниками своих решений до окончания конкурса. Нарушители будут дисквалифицированы.
  • Если условие задачи кажется Вам неоднозначным, проверьте своё понимание условия с помощью нашей эталонной реализации (см. ниже), вместо того, чтобы задавать вопросы по условию. Если Вы обнаружите, что поведение эталонной реализации противоречит условию, пожалуйста, сообщите нам.

Постановка задачи


Вы разрабатываете систему применения фильтров для почтовой системы. Вам нужно написать модуль для Node.js, экспортирующий одну функцию:
filter(messages, rules)


  • messages — это объект, ставящий в соответствие уникальным идентификаторам сообщений объекты с двумя свойствами: from и to. Каждый такой объект описывает одно электронное письмо.
  • rules — это массив объектов с тремя свойствами: from (необязательно), to (необязательно) и action (обязательно). Каждый из этих объектов описывает одно правило фильтрования.

Все строковые значения во входных данных непустые и содержат только символы ASCII в диапазоне от 0x20 до 0x7F включительно.

Считается, что письмо удовлетворяет правилу фильтрования, если оба его свойства from и to удовлетворяют маскам, заданным в соответствующих свойствах правила. Маски регистрозависимые; символу * в маске удовлетворяет любое число (0 или более) любых символов, а символу ? — один любой символ. Если свойства from или to отсутствуют в правиле фильтрования, то в качестве значения по умолчанию используется *. Как следствие, если в правиле отсутствуют оба свойства from и to, то ему удовлетворяют все письма.

К каждому письму необходимо применить все правила, которым оно удовлетворяет, в правильном порядке. Функция filter должна вернуть объект, ставящий в соответствие идентификаторам сообщений массивы действий. Для каждого письма такой массив должен содержать значения свойств action всех правил, которым это письмо удовлетворяет, в порядке перечисления правил в массиве rules. Если письмо не удовлетворяет ни одному из правил, пустой массив для этого письма всё равно должен присутствовать в результате.

Пример


Ниже приведён типичный пример корректного вызова функции filter:
filter({
    msg1: {from: 'jack@example.com', to: 'jill@example.org'},
    msg2: {from: 'noreply@spam.com', to: 'jill@example.org'},
    msg3: {from: 'boss@work.com', to: 'jack@example.com'}
}, [
    {from: '*@work.com', action: 'tag work'},
    {from: '*@spam.com', action: 'tag spam'},
    {from: 'jack@example.com', to: 'jill@example.org', action: 'folder jack'},
    {to: 'jill@example.org', action: 'forward to jill@elsewhere.com'}
])

Правильная реализация filter в этом случае вернёт следующее:

{
    msg1: ['folder jack', 'forward to jill@elsewhere.com'],
    msg2: ['tag spam', 'forward to jill@elsewhere.com'],
    msg3: ['tag work']
}

Эталонная реализация


Мы подготовили эталонную реализацию функции filter по адресу http://ift.tt/1kSBMGz. Для заданных значений аргументов она выдаёт корректный результат. Эта реализация также строго проверяет корректность входных значений (от Вашего решения проверки входных данных не требуется). В спорных случаях вместо того, чтобы задавать нам вопросы по условию задачи, пользуйтесь эталонной реализацией. Если Вы подозреваете, что эталонная реализация выдаёт неверный ответ для тех или иных входных данных, пожалуйста, сообщите нам.

Чтобы не допустить перегрузки нашего сервера, мы ограничили объёмы входных данных 10 правилами и 10 письмами. Ваше решение не должно иметь таких ограничений.

К эталонной реализации по упомянутому выше адресу можно делать HTTP-запросы методом POST с телом запроса типа application/json. Тело должно представлять собой объект с двумя свойствами: messages и rules, — содержащими значения соответствующих аргументов функции filter. Тело ответа, также в формате JSON, будет содержать значение, которое функция должна вернуть. При недопустимых входных данных Вы получите ответ HTTP 400 с описанием ошибки в формате text/plain.

Желаем удачи всем участникам!

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

[recovery mode] Как сделать из мухи слона

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

Известный автор книг по занимательной математике Е. Я. Гик в своей книге "Занимательные математические игры" опубликовал такое 16-ходовое решение, как из мухи сделать слона: муха-мура-тура-тара-кара-каре-кафе-кафр-каюр-каюк-крюк-упюк-урок-срок-сток-стон-слон.

муха и слон

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

Из мухи слона, первая версия


Честно признаться, слона из мухи получилось сделать довольно быстро.

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

Итак…

1) Словарь существительных


Оказалось, даже с первым пунктом есть проблемы, — найти стоящий словарь существительных оказалось уже отдельной подзадачей. Не помню где именно, но нашёл сносный готовый словарь. Формат по одному слову на строку, utf8, разделители \r\n — так и оставил в дальнейшем.

2) Алгоритм


Естественно, походя поинтересовался решали ли эту проблему мух и слонов, и как. Хороший вариант решения нашёл тут planetcalc.ru/544. Для только 4 буквенных слов, под яваскрипт (что на самом деле идея правильная для этого приложения — нет смысла гонять серверные мощности, когда поиском может заняться клиентское железо в браузере). Впрочем, исходники не смотрел, а смотрел на здравые рассуждения ниже в статье.

Действительно, если в качестве алгоритма использовать построение дерева со всеми вариантами, пока при прокладке очередного уровня не попадётся искомое слово, то никаких ресурсов не хватит.

Например, у слова КОРА есть 19 переходов только из распространённых слов, пришедших на ум, от «гора» до «корт».

Даже если дать очень оптимистичную оценку на среднее число вариантов модификаций в 5 (всего!), то если к какому-то слову минимальный путь составит 10 шагов, то в памяти должно уместиться дерево в 510 ~= 10 млн нодов. Учитывая накладные расходы на содержание структуры дерева (как минимум, 2 указателя на потомков из предка каждый по 4/8 байт) и на собственно хранение данных нод (языковая/структурная обёртка переменной + сами данные: символы строки в utf8 ещё более 10 байт) получим требование по ОЗУ для таких условий минимум порядка 200-300 Мб. А условия могут быть гораздо хуже.

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

Функция генетического поиска цепочки переходов слов
  /**
        * Поиск цепочки побуквенных преобразований от первого слова ко второму
        *
        * Возвращает список слов или пустой массив если цепочки преобразований не существует
        *
        * @param string $wordFrom - Начальное слово
        * @param string $wordTo - Конечное слово
        * @return array Список слов от начального к конечному
        * @throws WordWizardException
        */
        public function FindMutationChain($wordFrom, $wordTo, $maxSteps = 1000, $maxPopulation = 100)
        {
                $resultKeysChain = [];
                $resultChain = [];
                
                // Принудительно приводим к нижнему регистру входные слова
                $wordFrom = mb_convert_case($wordFrom, MB_CASE_LOWER);
                $wordTo   = mb_convert_case($wordTo, MB_CASE_LOWER);
                
                $fromLen = mb_strlen($wordFrom);
                $toLen   = mb_strlen($wordTo);
                
                // Слова должны быть одной длины
                if ($fromLen != $toLen) {
                        throw new WordWizardException("Слова должны быть одинаковой длины.");
                }
                
                // Существование первого слова в словаре для алгоритма не обязательно
                $wordFromKey = binary_search($this->_dictionary, $wordFrom);
                // Но для второго слова, для простоты, будем это требовать
                $wordToKey = binary_search($this->_dictionary, $wordTo);
                if ($wordToKey < 0) {
                        throw new WordWizardException("Конечное слово \"$wordTo\" не обнаружено в словаре.");
                }
                
                // Инициализируем цепочку слов
                $mutationChains = [ [ 'keys' => [$wordFromKey], 'mutatedPositions' => [-1] ] ];
                $population = 1;
                
                // Главный цикл генетического алгоритма поиска
                for ($step = 0; $step < $maxSteps; $step++) {
                        
                        // Не дошли ли до искомого слова?
                        foreach ($mutationChains as $mutationChain) {
                                if (end($mutationChain['keys']) == $wordToKey) {
                                        // Найдена одна из кратчайших (для этого забега) цепочек
                                        $resultKeysChain = $mutationChain['keys'];
                                        break 2;
                                }
                        }
                        
                        // Выращиваем следующее поколение
                        $newMutationChains = [];
                        
                        foreach ($mutationChains as $mutationChain) {
                                $lastKey        = end($mutationChain['keys']);
                                $lastMutatedPos = end($mutationChain['mutatedPositions']);
                                $lastWord       = $this->_dictionary[$lastKey];
                                
                                $nextMutations = $this->FindMutationVariants($lastWord, $wordTo, $fromLen, $lastMutatedPos, $mutationChain['keys']);
                                
                                foreach ($nextMutations as $mutation) {
                                        list($nextKey, $nextMutatedPos) = $mutation;
                                        $nextWord = $this->_dictionary[$nextKey];
                                        $score = $this->GetWordScore($nextWord, $wordTo);
                                        
                                        // Новый потомок
                                        $newMutationChain = $mutationChain;
                                        $newMutationChain['keys'][] = $nextKey;
                                        $newMutationChain['mutatedPositions'][] = $nextMutatedPos;
                                        $newMutationChain['score'] = $score;
                                        
                                        $newMutationChains[] = $newMutationChain;
                                }
                        }
                        
                        // Предыдущее поколение больше не требуется
                        $mutationChains = $newMutationChains;
                        
                        // А если нового не появилось..
                        if (empty($mutationChains)) {
                                throw new WordWizardException("На шаге $step (из максимально $maxSteps) закончились варианты. Поиск не увенчался успехом.");
                        }
                        
                        // Сортируем новое поколение по "степени приспособленности" (похожести последнего слова цепочки на искомое)
                        usort($mutationChains, function($a, $b) {
                                return $b['score'] - $a['score'];
                        });
                        
                        // Естественный отбор - оставляем самых лучших
                        array_splice($mutationChains, $maxPopulation);
                        
                }
                
                // слишком глубокий поиск?
                if ($step == $maxSteps) {
                        throw new WordWizardException("Пройдено максимально разрешённое число шагов ($maxSteps), но поиск не увенчался успехом.");
                }
                
                // Формируем итоговую цепочку из слов
                if ($resultKeysChain) {
                        foreach ($resultKeysChain as $key) {
                                $resultChain[] = $this->_dictionary[$key];
                        }
                }
                
                return $resultChain;
        }




Весовую функцию честно взял с описания на том же planetcalc.ru/544. Обмыслил почему оно такое, для себя понял так:
— идентичность букв на верных позициях 3 балла: Без комментариев, максимальный балл тут логичен
— гласная, пусть и другая, в нужной позиции 2 балла: Гласную в нужное место гораздо труднее подтащить, зато она потом с помощью мутаций согласных, а таких вариантов больше, легче смутирует уже в нужную гласную. К тому же гласная «задаёт тон» — около неё легче крутятся согласные, в том числе нужные под искомое слово.
— наличие гласной вообще 1 балл: Схожие рассуждения с приведёнными выше, гласную мутировать значительно труднее чем согласные.

Отдельно замечу, что на всём этапе поиска эталонное слово, которое должно получиться и с которым идёт постоянное сравнение, одно и то же. Например тот же слон. Потому «разобранного на куски для сравнения слона» (бедная зверушка) логично в таком анатомическом виде и закэшировать.

Для простоты и недолго думая, соорудил простейший кэш прямо в функции оценки.

Функция оценки похожести пары слов
   /**
        * Функция оценки похожести слова
        *
        * @param string $word - Оцениваемое слово
        * @param string $comparationWord - Эталонное слово
        * @return int 
        */
        public function GetWordScore($word, $comparationWord)
        {
                // Частый случай поиска - с одним и тем же эталонным словом, - используем кэширование
                static $cachedComparationWord = '';
                static $wordLen = 0;
                static $cwLetters = [];
                if ($cachedComparationWord != $comparationWord) {
                        $cachedComparationWord = $comparationWord;
                        $wordLen = mb_strlen($comparationWord);
                        $cwLetters = [];
                        for ($i = 0; $i < $wordLen; $i++) {
                                $letter = mb_substr($comparationWord, $i, 1);
                                $cwLetters[$i] = [
                                        'letter' => $letter,
                                        'isVovel' => false === mb_strpos($this->_vovels, $letter) ? false : true,
                                ];
                        }
                }
                
                $score = 0;
                for ($i = 0; $i < $wordLen; $i++) {
                        
                        $letter = mb_substr($word, $i, 1);
                        
                        // Полностью совпадающим символам максимальная оценка = 3
                        if ($letter == $cwLetters[$i]['letter']) {
                                $score += 3;

                                continue;
                        }
                        
                        $isVovel = (false === mb_strpos($this->_vovels, $letter) ? false : true);
                        
                        if ($isVovel) {
                                if ($cwLetters[$i]['isVovel']) {
                                        // Совпадение позиции гласной буквы = 2
                                        $score += 2;
                                }
                                else {
                                        // Наличие гласной буквы = 1
                                        $score += 1;
                                }
                        }
                }
                return $score;
        }




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

Первое ограничение — это допустимые позиции букв для мутации. В самом деле, если на прошлом шаге мы, например, поменяли 3-ю буквы, сделав ход «муХа» — «муЗа», то на следующем шаге мутация «муЗа» — «муРа» лишена смысла. Ведь нам интересна максимально короткая цепочка. А так мы получается делаем заведомо лишний шаг, ведь можно было сразу сделать ход «муХа» — «муРа». Поэтому одним из параметров функции является позиция прошлой мутации.

Второе ограничение — это уникальность слов в цепочке. Объясняется тоже просто. Допустим, есть цепочка «муха» — "мука" — «бука» — «бура» — «мура» — "мука" — «рука». Очевидно, что кусок "мука" — «бука» — «бура» — «мура» был лишним в цепочке. И даже если она дойдёт до финального искомого «слона», то ровно такая же, но цепочка из уникальных слов с выкинутыми повторами будет короче. А значит лучше. Так что такие циклы из-за повторов нам не нужны. Поэтому ещё одним из параметров функции поиска вариантов мутаций делаем массив слов (в данном случае id слов), которые уже были использованы в цепочке.

Параметр длины слова — это я на спичках mb_strlen поэкономил. Так-то метод задумывался приватным, но для проб и тестов был опубличен. Не пускайте такие штуки в продакшн :) Во всяком случае, без охватывающих проверок.

А конечное слово… может человеческая рефлексия какая-то, а может и интуиция, — оставил возможность использования на потом. Всё же логично ожидать от функции получения набора потомков какой-то зависимости от того, на кого похожими они должны получаться. Ничто не мешает делать первичный отсев прямо тут. Но пока — не используется.

Функция получения возможных мутаций
  /**
        * Получение списка пар {id слова, позиция мутации символа} для возможных вариантов мутаций
        *
        * Для поиска используется рабочий словарь плюс общие вспомогательные словари
        *
        * @param string $wordFrom - Начальное слово
        * @param string $wordTo - Конечное слово
        * @param int $wordLen - Длина обоих слов
        * @param int $disabledMutationPos - Индекс в слове буквы, которую не нужно менять (была изменена на предыдущем шаге)
        * @param array $excludedWordKeys - Уже использованные слова
        * @return array 
        */
        public function FindMutationVariants($wordFrom, $wordTo, $wordLen, $disabledMutationPos, $excludedWordKeys)
        {
                $variants = [];
                
                for ($mutPos = 0; $mutPos < $wordLen; $mutPos++) {
                        // Пропускаем исключённую букву (нет смысла менять ту же, что на пред. шаге)
                        if ($mutPos == $disabledMutationPos) continue;
                        
                        // Получаем обгрызенное слово без $mutPos-й буквы
                        $wordBeginning = mb_substr($wordFrom, 0, $mutPos);
                        $wordEnding = mb_substr($wordFrom, $mutPos + 1);
                        
                        // Ищем такие псевдослова
                        if ($mutPos < self::SUB_DICTIONARIES_MAX) {
                                // Ура, мы можем воспользоваться соответствующим вспомогательным словарём
                                $subDictionary  = $this->_subDictionaries[$mutPos + 1];
                                $pseudoWord = $wordBeginning . $wordEnding;
                                $pseudoWordKey = binary_search($subDictionary, $pseudoWord, 0, NULL, [$this, 'SubDictionaryWordsCmp']);
                                
                                if ($pseudoWordKey >= 0) {
                                        // В PHP так и не реализовали установку итератора в массиве по ключу,
                                        // поэтому обходим проблему через хранение связанных ключей в словаре
                                        $row = $subDictionary[$pseudoWordKey];
                                        
                                        foreach ($row[self::_SDW_WORDS_KEYS] as $key) {
                                                // Не повторяемся - пропускаем ранее использованные слова
                                                if (in_array($key, $excludedWordKeys)) continue;
                                                
                                                $variants[$key] = [$key, $mutPos];
                                        }
                                }
                        }
                        else {
                                // Вспомогательного словаря нет - берём основной, ищем начало слова и перебираем всё подходящее
                                
                                if ($mutPos == 0) {
                                        // Когда совсем нет вспомогательных словарей, и рассматривается мутация 
                                        // первой буквы слова, это совсем не круто - нужно использовать полный перебор
                                        // (здесь тоже можно пойти на оптимизацию группировки слов по длине)
                                        $key = 0;
                                }
                                else {
                                        // Определяем с какой позиции в словаре начинать перебор
                                        $key = binary_search($this->_dictionary, $wordBeginning);
                                        if ($key < 0) {
                                                $key = -$key;
                                        }
                                }
                                
                                // Перебираем
                                for ($key; isset($this->_dictionary[$key]); $key++) {
                                        $word = $this->_dictionary[$key];
                                        // Можно выходить, если слово уже начинается не так
                                        if (mb_substr($word, 0, $mutPos) != $wordBeginning) {
                                                break;
                                        }
                                        // Пропускаем по критерию длины слова (простор для дальнейшей оптимизации)
                                        if (mb_strlen($word) != $wordLen) {
                                                continue;
                                        }
                                        // Наконец, проверяем соответствие конца слова
                                        if (mb_substr($word, $mutPos + 1) != $wordEnding) {
                                                continue;
                                        }
                                        
                                        // Не повторяемся - пропускаем ранее использованные слова
                                        if (in_array($key, $excludedWordKeys)) continue;
                                        
                                        // Слово подходит, добавляем как вариант
                                        $variants[$key] = [$key, $mutPos];
                                }
                        }
                }
                return $variants;
        }




3) Работа со словарём


Алгоритм хорошо, но у нас есть источник данных (слов) ввиде файла, с которым надо эффективно и много работать из алгоритма поиска.
Да, этот файл-словарь отсортирован по алфавиту по возрастанию. И он не такой уж гигантский, всего около 1 Мб, так что мы можем его смело загрузить для работы в оперативку целиком.

При этом, конечно, следует понимать, что в «загруженном и разложенном» в структуру данных ввиде массива, в зависимости от языка словарь будет занимать больше памяти. Для PHP 5.4 получилось что словарь в загруженном виде весит около 6 Мб.

Сюда же.

Забегая вперёд, подсловари весят ещё больше.

[Здесь же первая мысль о логичности использования БД. Но решил попробовать сделать сначала без неё.]

Однако:
— в PHP array_search тупой перебиратор, сказать ему «эй, массив же сортирован, ищи бинарно» возможности нет, других подходящих функций из коробки нет, играть костылём flip-keyexists не хотелось да и сложно было применить
— даже если б была функция быстрого бинарного поиска в сортированном массиве, имеется проблема поиска по маске с выбитым символом.

3.1) Быстрый поиск по сортированному массиву первого из неуникальных значений


Первое решается велосипедом бинарного поиска для PHP. Одолжил у товарища покататься, http://ift.tt/1ktZo4I.

Следует заметить, что эта версия бинарного поиска самая обычная, арифметическая, пригодная для работы в сортированном массиве с последовательной целочисленной нумерацией (ключи от 0 до N-1 например).

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

Пример: ищем МУА, есть массив (см. ниже) [… 99-МС(т)ИТЕЛЬ, 100-МУ(з)А, 101-МУ(к)А, 102-МУ(р)А, 103-МУ(т)А, 104-МУ(х)А, 105-МУ(р)АВЕЙ, 106-МУ(р)АВЕЙНИК… ] Обычный бинарный поиск попадает очередной итерацией допустим попадает в ключ 102. Значение элемента (МУА, получилось из слова МУРА) равно искомому (МУА, ищем потомков для МУХА) и этот ключ нам и пришёл бы. И потом загромождай логику перебором и вверх и вниз. Модифицированный алгоритм находит именно самый первый, ключ 100, и далее можно идти последовательно вниз по массиву, пока элемент == искомое.

Модифицированный бинарный поиск
/**
* Двоичный поиск в сортированном массиве
*
* @param array $a - Отсортированный массив (по возрастанию)
* @param mixed $needle - Значение, которое ищем
* @param int $first - Первый индекс массива для поиска (включая)
* @param int $last - Последний индекс массива для поиска (не включая)
* @param string $compare - Функция сравнения. Аналогичного вида как для usort
*
* @return int
*   Возвращает индекс в массиве искомого значения.
*   Иначе возвращает -(insert_index + 1).
*   insert_index является индексом наименьшего элемента массива, 
*   который больше чем искомое значение, либо равен sizeof($a) если искомое
*   больше всех элементов массива.
*/
function binary_search(array $a, $needle, $first = 0, $last = NULL, $compare = 'default_cmp')
{
        if ($last === NULL) {
                $last = count($a);
        }
        
        $lo = $first; 
        $hi = $last - 1;
        
        while ($lo <= $hi) {
                $mid = (int)(($hi - $lo) / 2) + $lo;
                $cmp = call_user_func($compare, $a[$mid], $needle);

                if ($cmp < 0) {
                        $lo = $mid + 1;
                } elseif ($cmp > 0) {
                        $hi = $mid - 1;
                } else {
                        $hi = $mid - 1;
                        // В случае массива с уникальными элементами можно сразу возвращать первый попавшийся индекс $mid
                        // Но мы проходим всю глубину до конца, чтобы получить бинарно именно самое первое вхождение искомого.
                        //return $mid;
                }
        }
        
        $cmp = call_user_func($compare, $a[$lo], $needle);
        return $cmp == 0 ? $lo : -($lo + 1);
}

/**
* Стандартная функция сравнения
*
* @param mixed $a - Левое сравниваемое
* @param mixed $b - Правое сравниваемое
* @return int Результат сравнения: -1 меньше, 0 равно, 1 больше
*/
function default_cmp($a, $b) {
        return ($a < $b) ? -1 : (($a > $b) ? 1 : 0);
}




3.2) Вспомогательные словари псевдослов


Второе — прикинул что «оперативка вполне выдержит» и решил сделать через подсловари. Где i-й подсловарь построен из основного словаря с вырезанием i-й буквы из слова. Типа МАШИНА => (i=2) МШИНА. По таким подсловарям можно применять тот же бинарный поиск для случаев выбитых букв на позициях, по которым есть подсловари.

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

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

Приемлемым компромиссом по память/скорость вышло использование 3-4 подсловарей.

Цифры для трансформации «муха»-«слон»:

Конфигурация T загрузки словарей T поиска T итого Потребление ОЗУ
Только основной словарь 0,02 сек 137 сек 137 сек 6 Мб
1 подсловарь 0,61 сек 16,40 сек 17,01 сек 25 Мб
2 подсловаря 1,20 сек 4,73 сек 5,93 сек 44 Мб
3 подсловаря 1,85 сек 2,72 сек 4,57 сек 62 Мб
4 подсловаря 2,42 сек 0,82 сек 3,24 сек 79 Мб
5 подсловарей 2,98 сек 0,77 сек 3,75 сек 97 Мб

Цепочка: «муха» — «мура» — «фура» — «фора» — «кора» — «корн» — «коан» — «клан» — «клон» — «слон» (9 переходов)

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

Для сравнения, превращение из «сосна» в «белка»:
— для 4 подсловарей: загрузка 2,41 сек, поиск 1,07 сек, итого 3,48 сек
— для 5 подсловарей: загрузка 3,01 сек, поиск 0,36 сек, итого 3,37 сек

Т.е. 5-й подсловарь можно добавлять разве что после оптимизации хранения словарей, кэширования, алгоритма. А сейчас он только лишнее потребление оперативки.

Но… Но «просто как-то сносно работающий вариант на коленке» меня не устроил. И я продолжил совершенствовать превращение мух в слонов.

1-я версия (PHP 5.4)

*
* Здесь хорошо бы сделать паузу для отдыха глаз, чашка кофе, и в этом духе
*



слон муха

Слону помадой выкрасила ухо,
Второе, хобот, хвостик и теперь
Летает в спальне розовая муха,
Жужжит и бьется головой о дверь.
kekc @hohmodrom.ru


Версия вторая


Причесал многое.
Добавил проверок.
Добавил бросание исключений вместо тихо-непонятного умирания.
Выделил конфиг.
Приготовился к переключению на БД — вынес дата-логику в отдельный маппер.
И т.п. по архитектуре.

Но интересно не это. Самые интересные изменения тут это парсер, фактор случайности и функция оценки, основанная на частотных характеристиках букв.

1) Парсер


Я заметил что исходный словарь хоть и достаточно большой, но там почему-то нет даже некоторых общеупотребительных слов. И внимание ))) там не было слона! Слоненок был, слониха была, а слона упс. Дискриминация.

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

[И да, в этом словаре я наткнулся в первый раз (из последующих шишек php sort, несмотря на верную локаль для setlocale и mb_string) что слова на Ё, внезапно, были в конце словаря.]

Решил исправить этот момент, взяв дополнительные слова пусть и не из готового для тех.использования словаря, но хоть откуда.
Немало ссылок вело на http://ift.tt/1kSnWUD, но он внезапно оказался уже который год предан забвению злым Яндексом, купившим в своё время Народ.ру и сломавшим его в погоне за фертингами.

Но тут помог великий вебархив, за что ему спасибо.

Выкачал всё что было, весь сохранившийся «словарь кросвордиста», сохранил в data/psrc/, написал parse.php на регулярке (которую потом несколько раз поправлял, т.к. сайт был у человека, похоже, на MS Word написан, и странички были не совсем идентичны по вёрстке), — расширил словарь процентов на 50%.

2) Фактор случайности


Цепочка получалась всегда одна и та же, что, в общем, очевидно. Чтобы иметь возможность «игры» и «вдруг найти лучше», ввёл фактор случайности на mt_rand в функцию оценки. Стало получаться интереснее. Иногда действительно стали видны новые, более короткие цепочки, о которых раньше и не догадывался.

Есть конечно и обратная сторона — для неудобных пар бывает поиск и не находит цепочки. Или находит несколько длиннее обычной. Но всё же основной случай достаточно стабилен.

Более конкретно, случайность введена «очень слегка» — в функцию сравнения при упорядочивании по приспособленности нового поколения — слова, имеющие одинаковую оценку приспособленности стали располагаться в случайном порядке.

Элементы рандома
                     // Сортируем новое поколение по "степени приспособленности" (похожести последнего слова цепочки на искомое)
                        usort($mutationChains, function($a, $b) {
                                $diff = $b['score'] - $a['score'];
                                return $diff ? $diff : mt_rand(-1, 1);
                        });



3) Функция оценки


Из МУХА СЛОН получался довольно живенько и симпатично, в пределах 10 переходов.
Но (!)
из МУХА слово СЛОГ получалось… упрямо переходов в 60-70 (!).
А ведь очевидно, что должно бы быть всего на 1 длиннее чем в СЛОНа. Человеку очевидно. Машине нет, она по алгоритму. Ошибка алгоритма. Ошибка функции оценки.

Экспирементировал немало, не скрою.

Получалось ну на 5 позиций укоротить цепочку при сомнительных изменениях в разбалловке. Но это же не тот результат который нужен.
Очевидно, с лёту с корректировки проблема не решалась, думал. В чём дело. В чём разница. Разница в последней букве, да, факт. Там слоН, а тут слоГ. Чем же эти буквы так отличаются, что всё так плохо…

Правильно. Частотой употребления! И соответственно числом связанных вариантов мутаций. То есть, «полный хит по Г=Г» может быть хуже, или по крайней мере не намного лучше для оценки «приспособленности», чем «не хит Н, М, К,… != Г». Но, конечно, гораздо лучше чем «не хиты Ы, Ъ, Щ,… != Г».

Взял таблицу частот употребления букв из вики. (На самом деле это не совсем корректно, надо по имеющемуся словарю существительных частоты считать, но вряд ли бы были кардинальные различия). Вбил как есть в код. Это не очень красиво, да, но это пока и пусть. Раскроил частоты букв на нормированные массивы по гласным и по согласным, с нормировкой по максимально употребительной гласной/согласной. Переписал функцию оценки. ЕСТЬ! СЛОН + 1!

Да и сам СЛОН стал получаться ещё на шаг-другой быстрее.

Работа с частотами букв
При инициализации:
 public function __construct()
        {
                //$this->_mprDictionary = null;
                $this->_mprDictionary = new DictionaryFileMapper();
                
                $this->_vovels = "аоуыэяёюие";
                $this->LoadLetterFrequencies();
        }
        
        private function LoadLetterFrequencies()
        {
                $this->_lettersFrequences = [
                        'о' => 0.10983,
                        'е' => 0.08483,
                        'а' => 0.07998,
                        'и' => 0.07367,
                        'н' => 0.06700,
                        'т' => 0.06318,
                        'с' => 0.05473,
                        'р' => 0.04746,
                        'в' => 0.04533,
                        'л' => 0.04343,
                        'к' => 0.03486,
                        'м' => 0.03203,
                        'д' => 0.02977,
                        'п' => 0.02804,
                        'у' => 0.02615,
                        'я' => 0.02001,
                        'ы' => 0.01898,
                        'ь' => 0.01735,
                        'г' => 0.01687,
                        'з' => 0.01641,
                        'б' => 0.01592,
                        'ч' => 0.01450,
                        'й' => 0.01208,
                        'х' => 0.00966,
                        'ж' => 0.00940,
                        'ш' => 0.00718,
                        'ю' => 0.00639,
                        'ц' => 0.00486,
                        'щ' => 0.00361,
                        'э' => 0.00331,
                        'ф' => 0.00267,
                        'ъ' => 0.00037,
                        'ё' => 0.00013,
                ];
                
                // Раскладываем общую таблицу на подтаблицы гласных и согласных
                $this->_lettersFrequencesVovel = [];
                $this->_lettersFrequencesConsonant = [];
                
                foreach ($this->_lettersFrequences as $letter => $frequency) {
                        if ($this->IsVovel($letter)) {
                                $this->_lettersFrequencesVovel[$letter] = $frequency;
                        }
                        else {
                                $this->_lettersFrequencesConsonant[$letter] = $frequency;
                        }
                }
                
                // Нормируем.
                // Массивы частот упорядочены, потому поиск не требуется
                
                $maxFrequency = reset($this->_lettersFrequencesVovel);
                foreach ($this->_lettersFrequencesVovel as $letter => &$frequency) {
                        $frequency /= $maxFrequency;
                }
                
                $maxFrequency = reset($this->_lettersFrequencesConsonant);
                foreach ($this->_lettersFrequencesConsonant as $letter => &$frequency) {
                        $frequency /= $maxFrequency;
                }
                
        }

        /**
        * Является ли буква гласной
        *
        * @param string $letter - Буква
        * @return bool 
        */
        public function IsVovel($letter)
        {
                return false === mb_strpos($this->_vovels, $letter) ? false : true;
        }


Функция оценки:
 /**
        * Функция оценки похожести слова
        *
        * @param string $word - Оцениваемое слово
        * @param string $comparationWord - Эталонное слово
        * @return int 
        */
        public function GetWordScore($word, $comparationWord)
        {
                // Частый случай поиска - с одним и тем же эталонным словом, - используем кэширование
                static $cachedComparationWord = '';
                static $wordLen = 0;
                static $cwLetters = [];
                if ($cachedComparationWord != $comparationWord) {
                        $cachedComparationWord = $comparationWord;
                        $wordLen = mb_strlen($comparationWord);
                        $cwLetters = [];
                        for ($i = 0; $i < $wordLen; $i++) {
                                $letter = mb_substr($comparationWord, $i, 1);
                                $cwLetters[$i] = [
                                        'letter' => $letter,
                                        'isVovel' => false === mb_strpos($this->_vovels, $letter) ? false : true,
                                ];
                        }
                }
                
                $score = 0;
                for ($i = 0; $i < $wordLen; $i++) {
                        
                        $letter = mb_substr($word, $i, 1);
                        
                        $isVovel = $this->IsVovel($letter);
                        
                        // Полностью совпадающим символам максимальная оценка = 3
                        if ($letter == $cwLetters[$i]['letter']) {
                                $score += 1;
                                
                                if ($isVovel) {
                                        $score += 2 + 1 * $this->_lettersFrequencesVovel[$letter];
                                }
                                else {
                                        $score += 0 + 3 * $this->_lettersFrequencesConsonant[$letter];
                                }
                                continue;
                        }
                        
                        if ($isVovel) {
                                if ($cwLetters[$i]['isVovel']) {
                                        // Совпадение позиции гласной буквы = 2
                                        $score += 2 + 2 * $this->_lettersFrequencesVovel[$letter];
                                }
                                else {
                                        // Наличие гласной буквы = 1
                                        $score += 2 * $this->_lettersFrequencesVovel[$letter];
                                }
                        }
                        else {
                                if (isset($this->_lettersFrequencesConsonant[$letter])) {
                                        $score += 3 * $this->_lettersFrequencesConsonant[$letter];
                                }
                        }
                }
                
                return round($score);
        }




Новые цифры для трансформации «муха»-«слон»:
Конфигурация T загрузки словарей T поиска T итого Потребление ОЗУ
Только основной словарь 0,04 сек 210 сек 210 сек 9 Мб
1 подсловарь 0,98 сек 26,16 сек 27,14 сек 42 Мб
2 подсловаря 1,97 сек 9,97 сек 11,94 сек 72 Мб
3 подсловаря 2,98 сек 4,72 сек 7,70 сек 102 Мб
4 подсловаря 3,97 сек 1,37 сек 5,34 сек 130 Мб
5 подсловарей 4,96 сек 1,30 сек 6,26 сек 158 Мб

Цепочка: «муха» — «муна» — «мина» — «лина» — «линн» — «лион» — «сион» — «слон» (7 переходов).

Как видим, потяжелел словарь (с 0,68 Мб до 1,03 Мб, +51%), а с ним подсловари и итоговый жор оперативки. Комбинаторика улучшилась, и хоть и на каждом шаге мутаций стало рассыпаться больше, а значит шагать стали медленнее, — конечная цель, при достижимости, стала получаться по результату быстрее, за меньшее число шагов.

Однако, по времени поиск получился совсем не быстрее, даже для 4 подсловарей. Один фактор другой не компенсировал. Тем не менее, по сути расширить словарь абсолютно корректный и необходимый ход для приближения к реальным боевым условиям. И есть ещё множество справочников кроссвордиста и словарей, в том числе онлайновых, с которыми можно поработать для расширения нашего словаря.

2-я версия (тот же PHP 5.4).

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



Некий деятель науки
ДЕЛАТЬ стал СЛОНА из МУХИ:
Надувал, надувал,
Поглядеть народ позвал.

Удивить он всех хотел…
Ну а слон-то улетел!


Версия третья


Честно признаться, ожидал от версии большего. Всё-таки база (была под рукой MySQL 5.5) должна, ну должна же была обеспечить взлёт хотя бы в разы, если не на порядки.

1) База и скорость?


Судя по всему, в версии с файлами я фактически добился эффекта memcache — куча словарей в памяти, а алгоритм, в общем, един и для файл- и для mysql-версий. В построении базы вроде соображаю, все нужные индексы для работы были проставлены.

Сами файлы меня тормозили только на этапе их загрузки в оперативку — порядка 4 сек. А поиск из мухи слона происходил порядка 0,8 сек. Так что в общем зачёте на доступность побеждает версия MySQL, с «загрузкой» порядка 0,002 сек и поиском порядка 0.95 сек. Понятное дело, загружать ей ничего не требуется, после одного-двух прошлых обращений скрипта, кэш прогрет и всё уже загружено и ждёт.

Структура базы
--
-- База данных: `metagram`
--

-- --------------------------------------------------------

--
-- Структура таблицы `dictionary`
--

CREATE TABLE IF NOT EXISTS `dictionary` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `lang` varchar(30) NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `name` (`name`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 AUTO_INCREMENT=1 ;

-- --------------------------------------------------------

--
-- Структура таблицы `word`
--

CREATE TABLE IF NOT EXISTS `word` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `value` varchar(50) NOT NULL,
  `description` varchar(255) DEFAULT NULL,
  `dictionary_id` int(11) NOT NULL,
  `length` smallint(6) NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `value` (`value`),
  KEY `dictionary_id` (`dictionary_id`),
  KEY `lenght` (`length`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 AUTO_INCREMENT=1 ;

-- --------------------------------------------------------

--
-- Структура таблицы `word_pseudo`
--

CREATE TABLE IF NOT EXISTS `word_pseudo` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `value` varchar(50) NOT NULL,
  `word_id` int(11) NOT NULL,
  `deleted_symbol_pos` smallint(6) NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `value_word_id` (`deleted_symbol_pos`,`value`,`word_id`),
  KEY `word_id` (`word_id`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 AUTO_INCREMENT= 1 ;



Так или иначе, ответ за 1 сек лучше чем за 5 сек.

2) Кэширование очевидного узкого места


Изначально, правда, было под 2 сек, из-за обильных запросов SELECT слово ПО ид. Агрессивное кэширование в MySQL-маппере устранило эту проблему. Тоже конечно не оптимальным образом, но и это ещё далеко не хайлоад продакшн, а эксперимент. Вполне терпимо на данном этапе.
Где то в классе DictionaryMysqlMapper
        ...

        private $_cachedWords;
        private $_cachedWordKeys;

        ...

        /**
        * Получить слово из словаря по указанному ключу
        *
        * @param string $key Ключ (идентификатор) слова
        * @return string|false|null
        */
        public function GetWord($key)
        {
                if (isset($this->_cachedWords[$key])) {
                        return $this->_cachedWords[$key];
                }
                
                $wordRow = $this->_db->FetchOne("SELECT * FROM `word` WHERE `id` = " . $this->_db->QuoteValue($key));
                $this->_cachedWords[$key] = $wordRow['value'];
                return $wordRow['value'];
        }



3) Тюнинг размера популяции


И кстати, в результате отлично себя показавшей функции оценки с учётом частот букв, удалось снизить число популяции в поколении со 100 до 50 без ущерба для результата. К слову, даже популяция в 20 показала себя не намного хуже, но оставил 50.

Это позволило заметно снизить время поиска. На примере тех же мухи и слона с примерно 1 сек до 0,5-0,6 секунд.

Итак,

3-я версия (Вновь PHP 5.4, но уже с MySQL 5.5)

*
* Тут уже и сама статья, по поднятой задачке и объёму, стала «из мухи слоном» )
* Пора подводить итоги.
*



Вежливый слон, Р.Муха

Вышел слон на лесную дорожку,
Наступил муравью на ножку
И вежливо
Очень
Сказал муравью:
— Можешь и ты
                         наступить на мою!
(с) Рината Муха, «Вежливый слон»

Итоги


На третьем шаге мы имеем решение задачи на PHP 5.4 + MySQL 5.5, требующее порядка 0,5 сек. на превращение мухи в слона за 9 итераций:
    'from' => "муха"
    'to' => "слон"
    'runMode' => "MySQL"
    'list' ...
        '0' => "муха"
        '1' => "маха"
        '2' => "мана"
        '3' => "манн"
        '4' => "ланн"
        '5' => "линн"
        '6' => "лион"
        '7' => "сион"
        '8' => "слон"
    'timeLoad' => "Инициализация, загрузка словарей: 0,008000 сек."
    'time' => "Поиск перехода между словами: 0,551032 сек."
    'status' => "готово."


Скрипт при этом не потребляет так конски оперативку, как в версии с чисто PHP и файлами словарей (под 100 Мб), потребление самое обычное. Те же данные, хранящиеся в СУБД, ведут себя более пристойно по аппетитам к памяти.

Что дальше?


Безусловно, решение не идеально, я знаю. Многое ещё можно сделать:
  • Вместо одного процесса поиска от начального к искомому, сделать агоритм на двух параллельных процессах поиска: от начального к искомому и от искомого к начальному, с выходом и построением цепочки по первой коллизии пары слов из двух процессов. Насколько я знаю алгоритмы заливки, таклй ход помогает улучшить скорость получения результата в 2-4 раза. Да, генетический алгоритм другой случай, но есть ощущение что вот такое встречное движение и тут даст результат.
  • Сделать горизонтальное масштабирование словаря? Раскидать слова разной длины по разным подтаблицам. Для этой задачи это допустимый ход. Ввиде дополнительного поля длины слова и индекса по нему пробовал, — ничего. Значит только партиционирование. Будет ли от этого толк, впрочем, пока затрудняюсь сказать.
  • Redis? Memcached?
  • Распараллеливание процессов обсчёта поколений генетических мутаций до N штук параллельных процессов, в зависимости от числа ядер на сервере
  • Добавить юзер френдли? В цепочках попадаются такие слова, о которых и не слыхивал. Интересно бы в цепочке на клиенте показывать и значение этих слов.
  • CP1251? Utf-8 это безусловно прекрасно. Но если работать заведомо только с русскими словарями, или же в сущности словаря указывать кодировку, в которой на самом деле хранятся слова, то почему бы и нет. Строгий 1 байт сильно упрощает работу со строкой для железок, и в 2 раза меньше будет кушать памяти. Это явно неплохо.
  • JavaScript версия? В случае массового количества запросов, например хабраэффекта, это неплохая идея — зачем сервер такими вычислениями нагружать, пусть железо на клиенте пыль стряхнёт, кулеры погоняет.
  • Серверная версия на C++?
  • И наверняка другие ходы, которые пока ещё не приходили в голову.

Тема затягивающая… Может быть, у истории будет продолжение. Во всяком случае, меня зацепило сильно, не меньше чем Diamond-Square.

PS:
Конечно, в этой статье нельзя не оставить ссылку на то, как делают из мухи слона художники.

Комментарии и замечания приветствуются! Может упустил какие-то простые и важные вещи. Благодарю за внимание.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.