Уроки PaintShop Photo Pro: восстановление старой фотографии I.

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

На данный момент сделаны хеш-таблицы 6 типов: множества примитивов, объектов и все 4 варианта мапов: примитив — примитив, примитив — объект, объект — примитив и объект — объект, над которыми нависает туча обобщающих интерфейсов.

Меня всегда удивляло, почему все подобные библиотеки создают еще одну иерархию типов, а не встраиваются в давно уже зарекомендовавший себя стандартный каркас коллекций Явы. Никаких принципиальных проблем с этим я не видел и не вижу. Поэтому над моей тучей интерфейсов, как на пантеоне, возвышаются java.lang.Iterable, java.util.Collection и java.util.Map. Я не зря дал ссылки на документацию по Java 8. Реализованы почти все методы из будущих интерфейсов, кроме spliterator(). Можно начинать привыкать.

Предисловие

Как-то в гостях мне в руки попалась головоломка, в которой из 25 одинаковых фигурок требовалось собрать куб. Я провозился с ней почти весь вечер, и как можно догадаться, абсолютно безрезультатно. Тем не менее, я не мог сдаться просто так.

Не можешь сам — заставь компьютер. Сказано — сделано. В результате написанному по наитию алгоритму пришлось работать всю ночь, чтобы найти все 4 уникальных решения. В процессе гугления решений для сравнения, я нашёл программу Burr Tools, которая справилась с этой задачей за 3 минуты на моём ноутбуке.

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

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы покажутся чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он будет полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Введение

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

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

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1

Сложность

Из предыдущей части можно сделать вывод, что если мы сможем отбросить все эти декоративные константы, то говорить об асимптотике функции подсчёта инструкций программы будет очень просто. Фактически, любая программа, не содержащая циклы, имеет f( n ) = 1, потому что в этом случае требуется константное число инструкций (конечно, при отсутствии рекурсии — см. далее). Одиночный цикл от 1 до n, даёт асимптотику f( n ) = n, поскольку до и после цикла выполняет неизменное число команд, а постоянное же количество инструкций внутри цикла выполняется n раз.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1
Часть 2

Логарифмы

Если вы знаете, что такое логарифмы, то можете спокойно пропустить этот раздел. Глава предназначается тем, кто незнаком с данным понятием или пользуется им настолько редко, что уже забыл что там к чему. Логарифмы важны, поскольку они очень часто встречаются при анализе сложности. Логарифм — это операция, которая при применении её к числу делает его гораздо меньше (подобно взятию квадратного корня). Итак, первая вещь, которую вы должны запомнить: логарифм возвращает число, меньшее, чем оригинал. На рисунке справа зелёный график — линейная функция f(n) = n, красный — f(n) = sqrt(n), а наименее быстро возрастающий — f(n) = log(n). Далее: подобно тому, как взятие квадратного корня является операцией, обратной возведению в квадрат, логарифм — обратная операция возведению чего-либо в степень.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1
Часть 2
Часть 3

Оптимальная сортировка

Поздравляю! Теперь вы знаете о том, как анализировать сложность алгоритмов, что такое асимптотическая оценка и нотация «большое-О». Вы также в курсе, как интуитивно выяснить является ли сложностью алгоритма O( 1 ), O( log( n ) ), O( n ), O( n² ) и так далее. Вы знакомы с символами o, O, ω, Ω, Θ и понятием «наихудшего случая». Если вы добрались до этого места, то моя статья уже выполнила свою задачу.

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

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

Вступление

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

Начальное описание

Алгоритм Ахо-Корасик реализует эффективный поиск всех вхождений всех строк-образцов в заданную строку. Был разработан в 1975 году Альфредом Ахо и Маргарет Корасик.
Опишем формально условие задачи. На вход поступают несколько строк pattern[i] и строка s. Наша задача — найти все возможные вхождения строк pattern[i] в s.

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

В данной статье будет показан математический подход к составлению алгоритмов на примере следующих вопросов и задач:

• Двоичные коды Грея. Их существование. Перебор подмножеств данного множества в порядке минимального изменения.
• Существование и реализация перебора подмножеств из k элементов в порядке минимального изменения.

Итак, приступим.

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

«Усложнённость (Simplexity) — процесс, которым природа достигает простых результатов сложными путями.» — Bruce Schiff

1. Введение

Представьте себе следующую задачу: у нас есть таблица из n целочисленных ключей A₁, A₂, …, A_n, и целочисленное значение X. Нам нужно найти индекс числа X в этой таблице, но при этом мы особо никуда не торопимся. На самом деле, мы бы хотели делать это как можно дольше.

Для этой задачи мы могли бы остановиться на самом тривиальном алгоритме, а именно, перебирать все A_n по порядку и сравнивать их с X. Но, может так случиться, что X = A₁, и алгоритм остановится на самом первом шаге. Таким образом, мы видим, что наивный алгоритм в наилучшем случае имеет временную сложность O(1). Возникает вопрос — можем ли мы улучшить (то есть, ухудшить) этот результат?

Разумеется, мы можем сильно замедлить этот алгоритм, добавив в него пустых циклов перед первой проверкой равенства X и A₁. Но, к сожалению, этот способ нам не годится, потому что любой дурак заметит, что алгоритм просто-напросто впустую тратит время. Таким образом, нам нужно найти такой алгоритм, который бы всё-таки продвигался к цели, не смотря на отсутствие энтузиазма, или вовсе желания до неё в конечном итоге дойти.

Все началось с того, что на глаза случайно попался конкурс от NextCastle Party, где предлагалось в строго ограниченные сроки (тема была объявлена за неделю) создать игру.

Условием была обязательная возможность играть с живыми игроками за одним компьютером (не важно, pvp или кооператив, синхрон или асинхрон). А так же были ограничения по платформам — необходимо, чтобы игра шла в браузере.

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

Внедрение веб-сокетов позволяет веб-приложения обрабатывать данные в режиме реального времени, не прибегая к «хакам», таким как long-polling.
Одним из примеров применения, является отображение результатов спортивного матча. Даже сейчас, много сайтов, которые показывают эти данные используют Flash-приложения, т.к. Action Script позволяет общаться с сервером через сокет-соединения. Тем не менее, вев-сокеты позволяют сделать тоже самое используя только HTML и JavaScript. Это, мы постараемся сделать в данном руководстве, используя php-сервер.

Все мы ходили/ходим на собеседования. Каждый раз при подготовке к очередному собеседованию просматриваем основные темы, вспоминаем вопросы, которые нам задавали в предыдущие разы, или вопросы, которые сами задавали. Ниже хочу представить основные вопросы, которые часто (основано на личном опыте) можно получить на собеседовании на должность middle/senior iOS Developer. Так сказать, шпаргалка. Заодно можно проверить свой уровень знания платформы.

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

Многие из нас часто вставляют на свои сайты карты. Обычно, это карта на странице контактов с единственным маркером, которым отмечено место офиса. Но иногда у заказчика включается фантазия и начинается «творчество». В свое время я потратил много времени, чтобы разобраться в постоянно меняющемся Google Maps API и хочу поделиться с вами своими наработками для решения обычных проблем с картами, которые выходят за рамки одного маркера.

Все, что описано ниже, можно узнать внимательно читая документацию GMaps API. Предполагается, что читатель уже умеет внедрять карту, подключать API и ставить маркер. Статья не претендует на полноту изложения, но может быть полезна начинающим пользователям Google Maps API.

Я руковожу разработкой ПО уже достаточно много лет. За эти годы мне пришлось провести более тысячи интервью и посчастливилось захантить больше сотни классных программистов. Естественно, у меня сложилась определенная практика проведения технических собеседований, которой я собираюсь поделиться. Возможно, это окажется кому-то полезным.

Ставим задачу

Кого ищем? Ищем эффективных бойцов. Известно, что эффективность программистов со схожим опытом может отличаться в 10 раз (Ф. Брукс) или даже в 27 раз (Р. Гласс). Сразу, оговорюсь, эффективность это не только количество трупов врагов реализованных требований к ПО на единицу трудозатрат, но и умение результативно взаимодействовать с окружающими. Это важно, потому что по моим наблюдениям 50% проектных человеко-часов тратится на коммуникации. У нас это называется «синхронизация ментальных моделей».

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


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

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

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

Когда-то давно на хабре была пара статей как не надо писать на java с интересными задачками по java.
Часть 1, Часть 2
Они очень интересные, но, к сожалению, автор не стал продолжать.

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

В конце статьи, разумеется, будут ответы с разъяснениями, а также дополнительные задания для самых сильных.