Friday, December 24, 2010

Вопросы с собеседований Google, часть 4

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




Вопросы:
16) Напишите функцию (и вспомогательные функции, если потребуется), которая берет на вход имя колонки из Excel (A,B,C,…AA,AB,AC...AAA) и возвращает соответствующее ему целочисленное значение (A=1,B=2,AA=27...)

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

18) Алгоритмы поиска по дереву. Напишите код BFS и DFS, оцените время выполнения и требования к памяти. Измените код BFS и DFS, так чтобы он работал с графами содержащими циклы и с графами со взвешенными ребрами. Сделайте так, чтобы код печатал путь от исходной вершины к искомой.

19) Вам дан циклический список чисел. Циклический, значит, что когда вы доходите до конца, вы снова возвращаетесь к началу. Напишите самый эффективный алгоритм поиска минимального числа в этом списке. Как найти заданное число в этом списке? Числа в списке упорядочены строго в порядке возрастания, но вы не знаете, в каком месте список начинается, например: 38, 40, 55, 89, 6, 13, 20, 23, 36.

20) В чем разница между локальными и глобальными переменными?


Возможные варианты решения...

Monday, December 20, 2010

Латентно-семантический анализ


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


Читать дальше >>>

Wednesday, December 15, 2010

Стеммер Портера для русского языка

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

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

Нет смысла переписывать описание алгоритма, оно, пусть и на английском, детально изложено на сайте самого Мартина Портера

Исходники на Java:
import java.util.regex.Matcher;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Porter {

    private static final Pattern PERFECTIVEGROUND = Pattern.compile("((ив|ивши|ившись|ыв|ывши|ывшись)|((?<=[ая])(в|вши|вшись)))$");

    private static final Pattern REFLEXIVE = Pattern.compile("(с[яь])$");

    private static final Pattern ADJECTIVE = Pattern.compile("(ее|ие|ые|ое|ими|ыми|ей|ий|ый|ой|ем|им|ым|ом|его|ого|ему|ому|их|ых|ую|юю|ая|яя|ою|ею)$");

    private static final Pattern PARTICIPLE = Pattern.compile("((ивш|ывш|ующ)|((?<=[ая])(ем|нн|вш|ющ|щ)))$");

    private static final Pattern VERB = Pattern.compile("((ила|ыла|ена|ейте|уйте|ите|или|ыли|ей|уй|ил|ыл|им|ым|ен|ило|ыло|ено|ят|ует|уют|ит|ыт|ены|ить|ыть|ишь|ую|ю)|((?<=[ая])(ла|на|ете|йте|ли|й|л|ем|н|ло|но|ет|ют|ны|ть|ешь|нно)))$");

    private static final Pattern NOUN = Pattern.compile("(а|ев|ов|ие|ье|е|иями|ями|ами|еи|ии|и|ией|ей|ой|ий|й|иям|ям|ием|ем|ам|ом|о|у|ах|иях|ях|ы|ь|ию|ью|ю|ия|ья|я)$");

    private static final Pattern RVRE = Pattern.compile("^(.*?[аеиоуыэюя])(.*)$");

    private static final Pattern DERIVATIONAL = Pattern.compile(".*[^аеиоуыэюя]+[аеиоуыэюя].*ость?$");

    private static final Pattern DER = Pattern.compile("ость?$");

    private static final Pattern SUPERLATIVE = Pattern.compile("(ейше|ейш)$");

    private static final Pattern I = Pattern.compile("и$");
    private static final Pattern P = Pattern.compile("ь$");
    private static final Pattern NN = Pattern.compile("нн$");

    public String stem(String word) {
        word = word.toLowerCase();
        word = word.replace('ё', 'е');
        Matcher m = RVRE.matcher(word);
        if (m.matches()) {
            String pre = m.group(1);
            String rv = m.group(2);
            String temp = PERFECTIVEGROUND.matcher(rv).replaceFirst("");
            if (temp.equals(rv)) {
                rv = REFLEXIVE.matcher(rv).replaceFirst("");
                temp = ADJECTIVE.matcher(rv).replaceFirst("");
                if (!temp.equals(rv)) {
                    rv = temp;
                    rv = PARTICIPLE.matcher(rv).replaceFirst("");
                } else {
                    temp = VERB.matcher(rv).replaceFirst("");
                    if (temp.equals(rv)) {
                        rv = NOUN.matcher(rv).replaceFirst("");
                    } else {
                        rv = temp;
                    }
                }

            } else {
                rv = temp;
            }

            rv = I.matcher(rv).replaceFirst("");

            if (DERIVATIONAL.matcher(rv).matches()) {
                rv = DER.matcher(rv).replaceFirst("");
            }

            temp = P.matcher(rv).replaceFirst("");
            if (temp.equals(rv)) {
                rv = SUPERLATIVE.matcher(rv).replaceFirst("");
                rv = NN.matcher(rv).replaceFirst("н");
            }else{
                rv = temp;
            }
            word = pre + rv;

        }

        return word;
    }

}


Для желающих протестировать, волшебная кнопка:



Tuesday, December 14, 2010

Стоп-символы русского языка

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


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


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

P.S. Cуществуют еще, так называемые, зависимые стоп-символы. Это, например, слово Владимир в фразе Владимир Путин. Такие слова нельзя выделить в отдельный список, однако их приходится учитывать при создании алгоритмов анализа текстов. Многие из них являются частью именованных элементов и представляют особый интерес. К ним мы еще обязательно вернемся.

Инвестирование, век живи - век учись.


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

Thursday, December 9, 2010

Японские свечи, автоматическое распознавание

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

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

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



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

Monday, December 6, 2010

Вопросы с собеседований Google, часть 3

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

Для желающих решать самостоятельно, сами вопросы:

11) Напишите функцию f(a,b) которая получает на вход две строки a и b и возвращает строку, содержащую символы содержащиеся в обеих строках, в том порядке, в котором они перечислены в строке a. Напишите версию с алгоритмической сложностью O(N2) и O(N)
12) Вам дана программа, которая падает во время работы. Вы запустили её 10 раз в дебаггере и обнаружили, что она никогда не падает в одном и том же месте. Известно что программа однопоточная и использует только стандартную библиотеку С. Что может вызывать подобное поведение? Как вы проверите свои гипотезы?
13) Объясните, как работает контроль насыщения (congestion control) в TCP?
14) В Java, в чем разница между final, finally и finalize?
15) Что такое многопоточное программирование и что такое взаимная блокировка (deadlock)?

Продолжение...

Thursday, December 2, 2010

Вопросы с собеседований в Google, часть 2

Продолжаю решать вопросы с собеседований в Google. Первый пост тут

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

6) Спроектируйте библиотеку классов для создания карточных игр
7) Вам нужно проверить, что у вашего друга есть ваш правильный телефонный номер, но вы не можете спросить его напрямую. Вы должны написать вопрос на открытке и дать её Еве, которая отнесет открытку Бобу и потом вернет ответ вам. Что следует написать на открытке помимо вопроса, чтобы Боб смог закодировать сообщение так, чтобы Ева не смогла расшифровать ваш телефонный номер? 
8) Как передаются Cookies в HTTP протоколе?
9) Спроектируйте таблицы SQL базы данных для системы проката автомобилей.
10) Напишите регулярное выражение которое матчит email-адрес.


Wednesday, December 1, 2010

Вопросы и ответы с собеседований в Google

Здесь опубликован список вопросов с собеседований Google на должность разработчика.

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

Вопросов много, посему это растянется на несколько постов. Итак, поехали:

1) Почему крышки для канализационных люков круглые?

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

2) Чем мутекс отличается от семафора? Кого из них вы будете использовать для того чтобы обезопасить операцию инкремент?

Прежде всего, мутекс бинарный, то есть либо занят – либо свободен. Либо открыт – либо закрыт. Семафор же может принимать множество значений от 0 до некоторого заданного максимального значения.

Но это еще не всё.  Мутекс всегда приналежит одному единственному потоку. Этот поток его получает и он же обязан его вернуть. Семафор же, напротив, никому не принадлежит и может получить сигнал из любого потока (процесса).

Что же касается второй части вопроса, я буду использовать мутекс.

3) Напишите программу на C которая измеряет скорость переключения контекста на UNIX/Linux.

В C я не силен, а вот написать программу измеряющую скорость переключения контекста на Java… давайте попробуем:
public class ContextSwitch implements Runnable{

    private Object lock = new Object();
    private volatile int counter = 0;
    public static final int MAX_CNT = 1000000;

    public void run() {
        for(;;){
           synchronized (lock){
               counter++;
               lock.notify();
               if (counter<MAX_CNT){
                   try { lock.wait(10000); } catch (InterruptedException e) {}
               }else{
                   break;
               }
           }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        ContextSwitch cts = new ContextSwitch();
        Thread t1 = new Thread(cts);
        Thread t2 = new Thread(cts);
        long startTime = System.currentTimeMillis();
        t1.start();
        t2.start();
        t1.join();
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);
    }

}

На моем компьютере получается 100000 переключений в секунду.


4)Вам дана функция возвращающая случайное число в диапазоне от 1 до 5. Напишите функцию которая будет возвращать случайное число в диапазоне от 1 до 7.

Дополнение: обе функции возвращают целые числа.

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

int i;
do
{
  i = 5 * (rand5() - 1) + rand5();  // i равномерно распределено между 1 и 25
} while(i &gt; 21);
// i равномерно распределено между 1 и  21
return i % 7 + 1; // результат равномерно распределен между 1 и 7

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


5)Опишите алгоритм обхода графа в глубину.

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

Sunday, November 28, 2010

Сингулярное разложение SVD

Есть такая тема в линейной алгебре, которую почему-то упорно игнорируют в институтах. Называется она сингулярное разложение матрицы или, на английском, Singular Value Decomposition. По-сути, сингулярное разложение матрицы это способ разложить матрицу в серию последовательных приближений, тем самым раскрывая её внутреннюю структуру. Используется это во множестве областей таких как text mining, обработка сигналов, сжатие изображений и пр.
Что это такое, я расскажу на примере котировок на бирже. Допустим у нас есть набор котировок в конце дня для нескольких акций.

GAZP AVAZ SBER
2.11 170.16 102.35 35.36
3.11 170.19 103.3 35.65
8.11 174.2 103.95 36.27
9.11 176.1 103.59 37.4
10.11 174.47 100.44 36.9
11.11 172.6 98.4 35.19
12.11 171.88 97.94 33.6
13.11 171.69 97.8 32.95
15.11 171.79 99.2 32.96
16.11 169.57 95.26 29.81
17.11 168.81 97.2 35.8
18.11 170.7 99.66 33.8
19.11 172.2 98.7 33.5

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

Ri = 100% * (Vi – Vi-1)/Vi

Это не совсем корректно с финансовой точки зрения, но для наших целей сойдет:

GAZP AVAZ SBER
0.16 0.49 0.02
0.02 0.93 0.83
2.36 0.63 1.74
1.09 -0.35 3.12
-0.93 -3.04 -1.34
-1.07 -2.03 -4.64
-0.42 -0.47 -4.53
-0.11 -0.14 -1.92
0.06 1.43 0.01
-1.29 -3.97 -9.54
-0.45 2.04 20.1
1.12 2.53 -5.59
0.88 -0.96 -0.88


Так вот, математики утверждают, что любую матрицу можно разложить в произведение трех матриц:

A = U*W*VT               (1)

где U и V – ортогональные матрицы, а W – диагональная матрица. Причем, хитрые математики предпочитают когда все отсортировано, поэтому диагональные элементы матрицы W располагаются в порядке убывания. Это и есть сингулярное разложение или SVD. В нашем случае оно будет иметь вид:


0 -0.08 0.02
0.04 -0.12 0.12
0.08 -0.21 -0.71
0.12 0.05 -0.45
-0.07 0.48 -0.11
-0.2 0.26 0.12
-0.19 -0.01 0.13
-0.08 -0.02 0.04
0.01 -0.22 0.19
-0.41 0.45 -0.02
0.82 0.2 0.17
-0.21 -0.58 0.07
-0.04 0.06 -0.41
*
24.51 0 0
0 6.09 0
0 0 2.79

*
0.02 0.15 0.99
-0.4 -0.9 0.14
-0.92 0.4 -0.04

Диагональные элементы wk матрицы W называются сингулярными числами. Столбцы матрицы U называются левыми сингулярными векторами {uk}, и т.к. матрица ортогональна, то эти векторы формируют ортонормированный базис. Т.е. ui*uj = 1 только если i=j, во всех остальных случаях ui*uj = 0. Строки матрицы V называются правыми сингулярными векторами {vk} и формируют другой ортонормированный базис. Теперь мы можем переписать наше равенство (1) в виде:
Ar = Σk=1r(uk * wk * vkt)
Причем Ar гарантированно является наиболее точным приближением матрицы A среди всех матриц с рангом r.

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

В некотором смысле, SVD разложение напоминает Фурье-преобразование. Только если в Фурье-преобразовании нам заранее задан набор базисов относительно которых мы раскладываем нашу функцию. То здесь базисы выбираются исходя из степени их влияния на результирующую матрицу.

Перейдем теперь к более реалистичному примеру. Для него я взял дневные котировки 18 крупных российских компаний за последний год (AFLT, AVAZ, BEGY, GAZP, KMAZ, KRSG, LKOH, LSNG, MDMBP, MMBM, ROSB, ROSN, SBER, SIBN, SNGS, TATN, TRNFP, VTBR)
Аналогично примеру выше, применил операцию SVD для этих котировок и получил разложение A = U*W*VT. Получившиеся матрицы слишком большие чтобы приводить их в тексте, для желающих повторить эксперимент, данные можно взять тут.


Рассмотрим матрицу V, особый интерес в ней для нас представляют первые столбцы. Ведь помните, что в матрице W диагональные значения отсортированы и, стало быть, во всем этом произведении U*W*V Наибольшее значение имеют первые столбцы матрицы U и первые строки матрицы VT (т.е. столбцы матрицы V) Более того, строки матрицы V соответствуют отдельным компаниям (это простое следствие закона произведения матриц) Давайте возьмем первые три столбца полученной матрицы V и отметим соответствующие точки на графике:





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

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










P.S. для расчета сингулярного разложения я использовал Java библиотеку Jama - очень простая, надежная и удобная библиотека, единственный недостаток - не поддерживаются разреженные матрицы, что не значительно в нашей ситуации, но может быть очень важно если SVD используется для анализа текста (об этом я расскажу чуть позже). Кроме того, сингулярное разложение умеют выполнять многие математические пакеты, такие как Mathcad или Mathematica. О другом и, пожалуй, самом известном применении SVD латентно семантическом анализе я напишу в ближайших постах.

Friday, November 19, 2010

Twitter предсказывает котировки на рынке.

Интересная статья о том, как можно предсказать котировки на рынке используя Twitter. Авторы утверждают, что сумели достичь точности более чем 87%, что, очевидно должно сделать их баснословно богатыми. Загвоздка только в одном, если это действительно работает, то как только эта методика стала известно широкой публике, она будет включена во всевозможные инструменты для анализа рынка используемые крупными инвесторами. И это, в свою очередь, очень скоро приведет к снижению эффективности такого инструмента. Я бы на их месте держал такой инструмент в строжайшей тайне и делал бы на нем деньги.

Что же они сделали? Они брали сообщения пользователей в twitter группировали по дням и скармливали алгоритму под названием GPOMS, авторство которого приписывается Google, но сам Google почему-то не дает никакой информации по нему. В результате они получили шесть временных рядов настроений: спокойствие, тревога, уверенность, энергичность, доброта и счастье. Эти ряды они скоррелировали с индексом Dow Jones Industrial Average и выяснилось, что так называемое, «Спокойствие» с точностью 87.6% коррелирует с поведением индекса через 3 дня. Естественно, все предсказания работают только в случае отсутствия неожиданных новостей, когда поведение рынка не подвержено сильному влиянию происходящих или ожидаемых событий.

Что ж, не считая использования некого магического алгоритма GPOMS, в целом статья выглядит интересной и является достойным чтивом для всех кто интересуется data mining-ом. Хотя применение на российском рынке выглядит сомнительным, хотя бы потому, что в США на фондовом рынке играет огромное количество людей, в отличии от Роcсии, где это прерогатива небольшой интересующейся прослойки. А посему и настроение масс вряд ли будут существенно влиять на цены акций. Хотя, кто знает. Давайте писать наши собственные алгоритмы и… держать их в тайне.

Monday, November 15, 2010

Как извлечь полезный текст из HTML. Часть 2

В прошлой заметке я рассказал, как можно извлечь полезный текст из HTML страниц. Решение основывалось на том, что в тех участках HTML-страниц где содержится полезный текст, как правило, очень мало разметки. То есть, величина отношения количества текста к количеству разметки больше некоторого порогового значения. Для своего тестирования я использовал новостные ленты rbc.ru, rbcdaily.ru и свой блог algorithmist.ru.
Этот подход дал неплохие результаты, но к сожалению он дает очень большое количество ложных срабатываний, около 2% на указанных выше сайтах. Улучшить ситуацию нам помогут методы машинного обучения, а именно нейронные сети. Идея заключается в том, чтобы в момент проверки является ли та или иная строчка полезным текстом обратиться к предварительно натренированной нейронной сети и спросить у нее.
В качестве параметров для нейронной сети я выбрал следующие атрибуты:

  • плотность HTML разметки в данной строке
  • длина строки
  • плотность HTML разметки в предыдущей строке
  • длина предыдущей строки
  • плотность HTML разметки в следующей строке
  • длина следующей строки
  • номер строки в документе


Все длины строк предварительно нормированы относительно максимальной длины строки в документе. Номер строки в документе так же нормирован относительно общего количества строк. Таким образом все 7 параметров принимают значения от 0 до 1 включительно.
Для создания нейронной сети я воспользовался библиотечкой Encog
За основу была взята простейшая feed forward нейронная сеть и активирующая функция гиперболический тангенс:



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



Для тренировки нейронной сети было создано два набора данных. Один тренировочный, другой проверочный. Конечно, мне было слишком лениво создавать большое количество данных вручную, поэтому каждый набор состоял всего из 10 статей с разных сайтов.
В результате, получилась нейронная сеть с характеристиками: количество ложных срабатываний 0.4%, количество пропусков события 0%. Конечно, эти результаты сильно зависят от того, какие именно сайты скармливать нейронной сети. Она не 100% универсальная. Но на большинстве новостных лент и блогов ведет себя неплохо выдавая внятное содержимое практически для любой страницы.
Думаю, что если требуется получить максимально точный результат, то лучше тренировать отдельные нейронные сети на каждый веб сайт. На практике это гораздо проще чем писать специальный HTML парсер и поддерживать его при малейших изменениях сайта.
Как и в прошлый раз, кнопка для желающих протестировать:





Как извлечь полезный текст из HTML. Часть 1

Задача на первый взгляд может показаться тривиальной: извлечь полезный текст из HTML страниц с различных сайтов, например новости с новостных лент. На практике, однако, реализация подобной функциональности, как правило, оканчивается написанием кучи парсеров заточенных под конкретные сайты. Поддерживать такие парсеры – сущий кошмар, особенно если система должна работать в автономном режиме долгое время. Хотелось бы иметь универсальное решение. Сегодня я опишу один из возможных вариантов решения этой проблемы.

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

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

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

  
boolean isMarkup = false;
int markupCnt = 0;
for (int i = 0; i < sline.length(); i++) {
char ch = sline.charAt(i);
if (ch == '<') {
isMarkup = true;
}
if (isMarkup) {
markupCnt++;
}
if (ch == '>') {
isMarkup = false;
}
}

Красной линией на графике обозначается длина строки, синей линией количество не-HTML текста. В целях улучшения визуализации, показаны данные усредненные по 5 строк.



Не слишком понятная картина, правда? Некий пик между 89 и 100, а в остальном, много пиков и провалов. Беглый взгляд в HTML и становится понятно, что в нашем случае он очень сильно засорен JavaScipt-ом и HTML-комментариями. Для улучшения результатов, стоит их удалить. Это сделать достаточно просто, предварительно обработав HTML. После этого, результаты становятся более очевидными:



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



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

Протестировать результаты такого фильтра можно тут, введите адрес страницы которую бы вы хотели отфильтровать и нажмите старт.




Saturday, November 13, 2010

Об округлении, банкирах и математиках

Казалось бы, что может быть проще, округлить дробь до целого? И чего тут обсуждать, нас всех в школе учили это делать. Однако… берем Java:
        
System.out.println(Math.round(2.5));
System.out.println(Math.round(3.5));

Получаем
3
4
Всё правильно? Да, так нас учили в школе, меня по-крайней мере. Советский союз - колыбель инженеров, а это стандартное математическое округление.
Но, теперь возьмем C#
  
Console.WriteLine(Math.Round(2.5));
Console.WriteLine(Math.Round(3.5));

Получаем
2
4
Оп-п-паньки. Неожиданно, правда? Получается что в C# округление работает не так как в Java. Лезем в документацию и читаем:

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

И ведь действительно, есть такой стандарт и действительно так принято. США – колыбель банкиров. И говорят, их так учат округлять в школе.

Но вернемся к нашему программированию. Чтобы сделать всё еще более запутанным, попробуем вот такой Java код
  
System.out.println(new DecimalFormat("0").format(2.5));
System.out.println(new DecimalFormat("0").format(3.5));

В результате
2
4

Вот такая вот петрушка, а теперь представьте что есть приложение где серверная часть написана на Java а клиентская на .Net и какие прелестные и неуловимые баги это может породить. Или пусть даже всё написано на Java, но например значения в таблице мы форматируем с помощью DecimalFormat а «итого» считаем с помощью Math.round(). Счастливых вам ночей с дебаггером, дорогие программисты…

К счастью, в .Net метод Round перегружен Round(Decimal) / Round(Decimal, MidpointRounding) и при необходимости можно явно указать способ округления. Таким образом, привести C# к Java достаточно просто:
  
Console.WriteLine(Math.Round(2.5, MidpointRounding.AwayFromZero));
Console.WriteLine(Math.Round(3.5, MidpointRounding.AwayFromZero));

К сожалению, я не знаю простого способа привести Java к C#. Нужно либо использовать BigDecimal в конструктор которого передать MathContext с типом округления ROUND_HALF_EVEN либо писать собственный метод.

Friday, November 12, 2010

Динамическое программирование на Haskell. Часть 3

В продолжение моих предыдущих постов (1, 2) о замечательном языке программирования Haskell. Вот мы решили задачу, получили программу, которую можно запускать и увидеть результат. Но что же со временем выполнения? А как собственно измерить время выполнения программы или части программы в Haskell?
Эта задача оказывается сложнее чем в императивных языках. И причиной тому, склонностью Haskell к ленивым вычислениям. Haskell настолько ленив, что не будет вычислять ничего до тех пор пока в этом не возникнет реальной необходимости. С одной стороны это открывает перед нами такие возможности как бесконечные массивы и бесконечная рекурсия. А с другой стороны, это создает некоторые трудности для нас, привыкших к императивному мышлению.
Итак, поехали. Имеется программа:
import Array

change :: [Int] -> Int -> Int
change xs n = dp!n
where
dp = listArray (0,n) [ cell i | i<-[0..n]]
cell 0 = 0
cell i = succ$minl [dp!(i-x)| x<-xs, i>=x]

minl :: [Int] -> Int
minl [] =  0
minl xs =  minimum xs


В императивном языке, можно было бы просто написать:
timer :: Int -> IO()
timer n = do
t0 <- getCPUTime
let c = change [1,2,5,10,50] n –(1)
t1 <- getCPUTime
putStrLn $ show $ div (t1-t0) cpuTimePrecision
Но в нашем случае, это не работает. Результат будет все время 0, потому что Haskell заметит, что переменная c не нужна и, стало быть, вычислять её не стоит. Чтобы все-таки получить результат, необходимо модифицировать строчку помеченную (1), получим следующую программу:
timer :: Int -> IO()
timer n = do
t0 <- getCPUTime
return $! change [1,2,5,10,50] n  -- (1)
t1 <- getCPUTime
putStrLn $ show $ div (t1-t0) cpuTimePrecision
Результат работы этой программы: 1000000 : 255656 100000 : 4093 10000 : 187 1000 : 15 Как мы видим время выполнения далеко от полиномиального, как предполагается в динамическом программировании. И, к сожалению, большая часть этого времени тратится в сборщике мусора. В чем легко убедиться запустив программу с ключиком: +RTS –sstderr %GC time 97.8% Проблема в том, что наша программа выделяет слишком много слишком много массивов. К счастью, решение есть. Пусть и несколько более запутанное:
change :: [Int] -> Int -> Int
change xs n = cs!!n
where
cs = 0 : (map succ (foldl1 minimize (map (\x -> replicate (x-1) maxBound ++ cs) xs)))

minimize [] [] = []
minimize (x:xs) (y:ys) = (min x y) : minimize xs ys


Что здесь происходит? Мы создаем ленивый массив cs в котором храним все решения задачи для заданного набора монет. Как вычисляются значения в этом массиве? Для этого мы создаем по ленивому массиву для каждой монеты, очевидно что если величина монеты X то первые X-1 значение в этом массиве будут не определены. Ведь мы не можем разменять сумму монетой большего достоинства чем сама сумма. Чтобы не усложнять вычисления, вместо неопределенности мы вбиваем самое большое возможное значение maxBound. Оставшиеся значения в этом массиве заполняются результирующим массивом (вот она прелесть Хаскеля, массив заполняет сам себя!)
Дальнейшее просто, каждый элемент массива cs равен минимальному значению из всех соответствующих элементов частных массивов плюс единица.

Запускаем еще раз наш таймер и смотрим время выполнения:

1000000 : 8656
100000 : 718
10000 : 62
1000 : 0

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

Thursday, November 11, 2010

Topcoder MM DigitsPattern

Подошел к концу очередной Topcoder MM, задачка DigitsPattern, что ж этот матч был пожалуй самым неоднозначным из всех что мне доводилось видеть. Здесь было всё, и бурный старт большого числа участников в начале и осознание того, что что-то не так в середине и озарение уже ближе к концу. Концовка же была самой знаменательной. Такого еще не бывало, аж 46 участников разделили между собой первое место.
Видя такое единодушие среди участников невольно задумываешься, а нет ли здесь случайно точного решения. Какого-нибудь динамического или жадного алгоритма. На поиски этого точного решения я и потратил чуть меньше недели. Скажу сразу, не нашел. Может быть оно и есть, вот только мое решение было далеко от идеального когда оно тоже поднялось на первое место. Что же это, слабость тестовых данных или сама задачка такова, что её способны решить столь большое число участников. Я надеюсь, что первое, но лучше подождем финальных результатов, они либо опровергнут либо подтвердят мою гипотезу.
Задачака звучала так (за полной формулировкой обращайтесь к исходникам): Вам требуется последовательно заполнить поле в клетку различными цифрами. Когда вы зполняете некоторую свободную клетку, она получает значение 1, все соседние с ней клетки получают +1 к своему значению, если они заполнены. В качестве входного параметра вам дается целевой шаблон и ваша цель заполнить как поле как можно ближе к этому шаблону. Близость к шаблону определяется как сумма абсолютной величины отклонения значения клетки в шаблоне от значения полученного в результате заполнения. Есть еще особые правила формирования шаблона, задаются размеры поля и способ кодирования ответа и входных параметров, все это интересующиеся могут почитать в исходном тексте.
Первая идея которая пришла мне в голову заключалась в том, чтобы нумеровать клетки в порядке обратном их величине в шаблоне. Это очевидное и безумно простое решение дало бы в итоге ~200-ое место. Любые попытки перебора, перестановок и прочих манипуляций с этим подходом едва ли вывели бы даже в первую сотню.
Озарением стало, что можно просто последовательно отбирать клетки с минимальным значением разности «максимально возможное значение клетки» - «требуемое значение клетки». Максимально возможное значение для данной клетки равно количеству не заполненных на данный момент времени соседей + 1. Очень простая формула и на уливление хороший результат. Это решение подняло меня в топ 100. Следом была простое и очевидное изменение: немного менять порядок выбираемых клеток, решение за решением, это дало мне 50-ое место.
Остаток времени я посвятил нежному и внимательному тюнингу решения: добавил кэш, чтобы отслеживать состояния в которых уже был. Добавил дополнительную сортировку для выбираемых клеток (теперь уже они выбирались не просто с минимальным значением разности но и с учетом соседних клеток). Эти манипуляции вывели меня на 1-ую строчку предварительного рейтинга.
Выход на первую строчку охладил интерес к дальнейшему решению, наверное зря. Ведь на собственной базе данных из 1000 тестов, увеличив время решения в 10 раз, я легко убедился, что мое решение не оптимально как минимум в 17 случаях. Но желания что-то подкручивать и искать дальнейшие оптимизации уже не было.

Интересные находки:
Класс java.util.BitSet, когда-то я о нем читал в книжках, но до сих пор на практике не приходилось использовать. В этой задачке он пригодился для кэширования. BitSet служил ключем для кэша. К сожалению, вскоре по результатам профайлинга мне пришлось сделать собственную реализацию FastBitSet потому что скорость работы стандартной была явно не удовлетворительной. Конечно это связанно с расширенным функционалом стандартной реализации и с ограниченными требованиями в моем случае.

Tuesday, November 9, 2010

Рисуем графы на Java

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

Graphviz



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


JGraph



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


Jung




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

Prefuse



Это гораздо больше чем библиотека для визуализации графов. К сожалению разработка проекта заброшена, последняя версия на сайте beta от 2007-го года доступна только в виде исходников. Впрочем, исходники собрались без проблем. А вот с документацией, увы, проблема, на сайте всё ограничивается оглавлением, большинство страниц содержат печальное «Coming soon...». Было бы здорово если бы кто-нибудь взялся и продолжил развитие этого продукта.

Итого, мой выбор остановился на Jung. Среди всех перечисленных вариантов это единственный удовлетворял основным критериям: бесплатный и на Java. Жаль, что выбор библиотек такого рода столь ограничен.

Friday, October 22, 2010

Не всё то быстро, что в библиотеке

Так получается иногда, что и алгоритм написан правильно и всё вроде коротко и ясно, а решение все равно не укладывается в требуемые временные ограничения... Эта история началась с задачки.
На первый взгляд оптимальное и простое решение пусть и давало правильные ответы, но на максимальном объеме данных работало неприлично долго. Что делать, полез смотреть решения более умных коллег. Каково же было мое удивления, когда другие решения оказались по-сути такими же, но только почти в 10 раз быстрее.
Потанцевав с бубном, проверив еще раз свое решение и убедившись что оно идентично правильному, обратил внимание на такое маленькое различие.

В моем решении, я возводил некоторое число в степень, всё это происходило в цикле:
  
t1 += Math.pow(t0%10, K);


Аналогичная строчка в правильном решении:
  
int k = t0%10;
for (int ki=1; ki<K; ki++) k*=t0%10;
t1 += k;


-В чем секрет? Подумал я. Ведь вызов стандартной функции возведения в степень должен быть достаточно быстрым. Секрет, как оказалось, был именно в этом.
В чем позволяет легко убедиться маленький эксперимент:
  
public static void main(String[] args) {
long t0 = System.currentTimeMillis();
for(int x=0; x<100000; x++){
for(int a=0; a<10; a++){
Math.pow(x, a);
}
}
long t1 = System.currentTimeMillis();
for(int x=0; x<100000; x++){
for(int a=0; a<10; a++){
pow(x, a);
}
}
long t2 = System.currentTimeMillis();
System.out.println("Math.pow() time " + (t1-t0));
System.out.println("Simple pow time " + (t2-t1));

}

private static double pow(double x, long a){
double res = 1;
for(int i=0; i<a; i++) res*=x;
return res;
}

Результат работы:
Math.pow() time 375
Simple pow time 31

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

Что мне не понятно, так это почему в стандартной библиотеке нет способа решения проблемы. Ведь это задача встречается достаточно часто, настолько часто, что некоторые языки программирования даже имеют соответствующий оператор возведения в степень. В Java можно было бы просто перегрузить метод Math.pow(double a, int pow), добавить проверку на величину pow и по результату проверки использовать либо простой цикл либо стандартное возведение в степень.

Saturday, June 19, 2010

Что день грядущий нам готовит или новые вкусности JDK7

Релиз JDK7 уже совсем близко и настало время поковыряться да посмотреть, что же нового он нам несет. Начнем с долгожданного и интересного пакета по имени java.dyn.
Классы в этом пакете служат для реализации JSR 292 (invokedynamic support). Та самая поддержка динамического вызова методов в Java которая должна существенно улучшить производительность новых языков программирования работающих поверх JVM (Scala, Jruby итд)
Многие элементы JSR 292 доступны и для Java программистов. Взять, к примеру, классы MethodHandle и MethodType.
MethodHandle позволяет нам получить ссылку на метод и вызвать его. В принципе, и раньше мы могли сделать тоже самое с помощью Reflection API. Утверждается, однако, что MethodHandle, работает быстрее поскольку поддерживается на уровне инструкций JVM.
Перейдем сразу к коду:

  
import java.dyn.MethodType;
import java.dyn.MethodHandle;
import java.dyn.MethodHandles;
import java.io.PrintStream;
….
MethodType type = MethodType.methodType(Void.TYPE, String.class);
MethodHandle handle = MethodHandles.lookup().findVirtual(PrintStream.class, "println", type);
handle.<void>invoke(System.out, "Hello!");

Что здесь происходит? Сначала мы создаем тип метода, который собираемся вызвать. Потом получаем ссылку handle на сам метод, в нашем случае это метод println(String s) класса PrintStream. И, наконец, вызываем этот метод, передавая в качестве первого параметра объект у которого будет вызван метод.
Особенно интересно то, что если заглянуть в класс MethodHandle то никакого метода invoke там нет. Вот оно, волшебство invokedynamic.
Спускаясь на землю, то есть на жесткий диск и процессор реального компьютера, нам придется немного попрыгать с бубном, чтобы запустить этот код. Для начала, нужно будет jvm дополнительные параметры. Ведь несмотря на то, что invokedynamic официально включен в jdk7, эта функциональность до сих пор считается экспериментальной.
Итак, запускаем
  
javac ./MethodHandleTest.java
java -XX:+UnlockExperimentalVMOptions -XX:+EnableMethodHandles -XX:+EnableInvokeDynamic MethodHandle

Получаем ошибку внутри JVM.
  
Invalid layout of java.dyn.CallSite at target
# A fatal error has been detected by the Java Runtime Environment …

Если вы, как и я, видите эту ошибку, значит разработчики все еще не озаботились исправлением несовместимости версий JVM и классов JDK. Поэтому нам самим придется скачать и добавить в bootclasspath jar-ник Качаем отсюда http://blogs.sun.com/jrose/resource/jsr292/hs19-b01-jsr292-patch.jar Кладем куда угодно на диске, и запускаем:
  
java -XX:+UnlockExperimentalVMOptions -XX:+EnableMethodHandles -XX:+EnableInvokeDynamic
-Xbootclasspath/p:<Путь к скачанному файлу>hs19-b01-jsr292-patch.jar MethodHandle

Hello!


Ура! Теперь всё работает.
В чем же разница? Мы и раньше могли сделать точно так же используя Reflection API:
  
import java.lang.reflect.Method;
import java.io.PrintStream;
...
Method handle = PrintStream.class.getDeclaredMethod("println", new Class[]{String.class});
handle.invoke(System.out, "Hello Reflection!");

Я решил проверить, а так ли в действительности хороша производительность, как нам обещали:
  
import java.dyn.MethodType;
import java.dyn.MethodHandle;
import java.dyn.MethodHandles;
import java.lang.reflect.Method;
import java.lang.reflect.InvocationTargetException;

public class PerformanceTest {
public static final int CNT = 100000;

public static void main(String[] args) throws InvocationTargetException, NoSuchMethodException, IllegalAccessException {
long t0 = System.currentTimeMillis();
reflectionAPITest();
System.out.println("Reflection API " + (System.currentTimeMillis()-t0));
t0 = System.currentTimeMillis();
methodHandlerTest();
System.out.println("Method handler " + (System.currentTimeMillis()-t0));

}

private static void reflectionAPITest() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
PerformanceTest target = new PerformanceTest();
for(int i=0; i<CNT; i++){
Method handle = PerformanceTest.class.getDeclaredMethod("increment", new Class[]{int.class});
handle.invoke(target, i);
}
}

private static void methodHandlerTest() {
PerformanceTest target = new PerformanceTest();
for(int i=0; i<CNT; i++){
MethodType type = MethodType.methodType(Integer.TYPE, Integer.TYPE);
MethodHandle handle = MethodHandles.lookup().findVirtual(PerformanceTest.class, "increment", type);
handle.<int>invoke(target, i);
}
}

public int increment(int i){
return i+1;
}
}

Хмм, все оказывается далеко не так гладко:
Reflection API 388
Method handler 821
Получается, что старый, добрый Reflection API почти вдвое быстрее чем новый MethodHandler.
К счастью, ситуация меняется радикально хэндл используется повторно. Так же, для сравнения, я добавил прямой вызов метода:
  
import java.dyn.MethodType;
import java.dyn.MethodHandle;
import java.dyn.MethodHandles;
import java.lang.reflect.Method;
import java.lang.reflect.InvocationTargetException;

public class PerformanceTest {
public static final int CNT = 10000000;

public static void main(String[] args) throws InvocationTargetException, NoSuchMethodException, IllegalAccessException {
long t0 = System.currentTimeMillis();
reflectionAPITest();
System.out.println("Reflection API " + (System.currentTimeMillis()-t0));
t0 = System.currentTimeMillis();
methodHandlerTest();
System.out.println("Method handler " + (System.currentTimeMillis()-t0));
t0 = System.currentTimeMillis();
directCall();
System.out.println("Direct call " + (System.currentTimeMillis()-t0));

}

private static void directCall() {
PerformanceTest target = new PerformanceTest();
for(int i=0; i<CNT; i++){
target.increment(i);
}
}

private static void reflectionAPITest() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
PerformanceTest target = new PerformanceTest();
Method handle = PerformanceTest.class.getDeclaredMethod("increment", new Class[]{int.class});
for(int i=0; i<CNT; i++){
handle.invoke(target, i);
}
}

private static void methodHandlerTest() {
PerformanceTest target = new PerformanceTest();
MethodType type = MethodType.methodType(Integer.TYPE, Integer.TYPE);
MethodHandle handle = MethodHandles.lookup().findVirtual(PerformanceTest.class, "increment", type);
for(int i=0; i<CNT; i++){
handle.<int>invoke(target, i);
}
}

public int increment(int i){
return i+1;
}
}

Пришлось увеличить количество итераций, и результат впечатляет:
Reflection API 1793
Method handler 347
Direct call 20
Теперь MethodHandle работает во много раз быстрее. И пускай на порядок медленней чем непосредственный вызов, все же это лучше чем вызов через Reflection API.
Что же, не будем торопиться заменять все reflection-вызовы на MethodHandler. В некоторых случаях, однако, это может оказаться очень полезным.

Спасибо за внимание, особенно тем, кто дочитал до конца. В своей следующей заметке о JDK7 я расскажу о самом странном классе InvokeDynamic. Всем хорошего дня!

Tuesday, June 1, 2010

Динамическое программирование на Хаскеле, часть 2

Этот пост является продолжением моего предыдущего поста про использование Haskell в динамическом программировании.
Давайте немного усложним задачу. Пусть теперь нам требуется не просто вернуть минимальное количество монет, которое требуется чтобы разменять заданную сумму, а нужно вернуть список монет.
Как это реализуется с точки зрения DP? В предыдущем решении для каждой суммы мы сохраняли оптимальное значение. Теперь нам нужно дополнительно хранить список монет, приведших к данному значению. Решение в лоб: связать с каждым элементом массива список в котором будет хранится полный перечень используемых монет. Этот подход не очень рационален с точки зрения используемой памяти. Куда лучше хранить лишь дельту. То есть, для каждой суммы мы храним значение последней добавленной монеты. Тогда, после того как решение найдено, мы можем пройти по этим дельтам в обратную сторону и собрать все монеты которые были использованы. Итак, переходим от слов к делу.
Решение на императивном языке Java будет выглядеть следующим образом:
  
public int[] change(int[] coins, int s) {
int[] dp = new int[s + 1];
int[] backtrack = new int[s + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for ( int i = 1; i <= s; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i && dp[i - coins[j]] + 1 < dp[i]) {
dp[i] = dp[i - coins[j]] + 1;
backtrack[i] = i - coins[j];
}

}
}
int[] res = new int[dp[s]];
int i = s;
int n = 0;
while(i!=0){
res[n++] = i-backtrack[i];
i = backtrack[i];
}
return res;
}


Как написать аналогичное решение на Haskell? Достаточно просто. Для этого на помощь нам приходят кортежи (они же туплы). Очень удобная структура данных имеющаяся в любом функциональном языке программирования.
По сути, кортеж, это просто набор элементов. Элементы могут быть одного а могут быть разных типов. Объявляются кортежи в Haskell очень просто:

  
let a = (1, 2)


a – это кортеж из двух элементов 1 и 2.
Чтобы достать элемент из кортежа, мы можем использовать функции fst, snd или pattern matching.
Теперь собственно решение. Идея та же, что и в императивном подходе. Только теперь мы не заводим дополнительный массив, а прямо в исходном массиве храним кортежи со связкой: оптимальное значение – величина последней монеты.
  
import Array
import Data.List


minl :: [(Int, Int)] -> (Int, Int)
minl [] = (0, 0)
minl xs = minimumBy (\x y -> compare (fst x) (fst y)) xs

changeValues :: [Int] -> Int -> [Int]
changeValues xs n = extract dp n
where
dp = listArray (0,n) [ cell i | i<-[0..n]]
cell 0 = (0, 0)
cell i = minl [(succ$fst (dp!(i-x)), x) | x<-xs, i>=x]
extract dp 0 = []
extract dp n = (snd (dp!n)):(extract dp (n-(snd (dp!n))))


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

Tuesday, May 25, 2010

Динамическое программирование на Хаскеле

Динамическое программирование это подход к решению задач основанный на рекуррентной формуле решения и одном или нескольких стартовых значениях. Задача решается методами динамического программирования если решения подзадач меньшего размера может быть использовано для вычисления решения исходной задачи. Алгоритмы DP обладают полиномиальной сложностью, что намного превосходит другие способы решения задач такого рода.
Для примера, классическая DP-задача 'Размен монет':
Вам даны монеты определенного достоинства (V1, V2, V3…, VN) необходимо посчитать, какое минимальное количество монет потребуется чтобы набрать заданную сумму S. Количество монет каждого достоинства не ограничено.
Рекуррентная формула для решения этой задачи:
  
D(S) = 1 + MIN (D(S-Vi))

Где D(S) это минимальное количество монет которое потребуется чтобы набрать сумму S
Как мы это можем реализовать в императивном стиле?
  
public int change(int[] coins, int s) {
int[] dp = new int[s + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for ( int i = 1; i <= s; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i && dp[i - coins[j]] + 1 < dp[i]) {
dp[i] = dp[i - coins[j]] + 1;
}
}
}
return dp[s];
}

В основе этого решения лежит запоминание предыдущих результатов.
Как это решить на Haskell? Ведь мы уже не можем использовать изменяемые массивы или хэш-таблицы. Зато Haskell нам дает в руки такой мощный инструмент как lazy-evaluation. Lazy-evaluation это тоже в своем роде 'запоминание’ только в обратную сторону. Итак решение:
  
import Array

change :: [Int] -> Int -> Int
change xs n = dp!n
where
dp = listArray (0,n) [ cell i | i<-[0..n]]
cell 0 = 0
cell i = succ$minl [dp!(i-x)| x<-xs, i>=x]


minl :: [Int] -> Int
minl [] = 0
minl xs = minimum xs

Что здесь происходит? Прежде всего, мы создаем массив с решениями
  
dp = listArray (0,n) [ cell i | i<-[0..n]]

Но в чем особенность? Особенность в том, что значения в этом массиве появляются по-требованию.
  
cell i = succ$minl [dp!(i-x)| x<-xs, i>x]

Здесь, справа налево, мы вычисляем i-ый элемент массива. Сначала выбираем все монеты достоинство которых меньше либо равно вычисляемой суммы, потом для каждого такого значения смотрим оптимальное решение в массиве. Заметьте, решения там может еще не быть, но оно будет вычислено для нас по-требованию, причем будет вычисленно лишь однажды и лишь для тех значений, которые нам на самом деле нужны! Находим минимальное решение и прибавляем к нему единицу (succ)
Маленькая утилитная функция, которую пришлось ввести minl нужна лишь потому, что стандартная функция minimum не работает с пустыми массивами.

Заключение


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

Friday, May 21, 2010

Hello World генетический алгоритм

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

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

Чтобы с чего-то начать с генетическим алгоритмом, я написал генетический Hello World. Что он делает? Он берет случайные строки мутирует и скрещивает их до тех пор пока не получится строка ”Hello World!”. На мой взгляд, этот пример является наглядным пособием по реализации генетического алгоритма и помогает в написании генетических алгоритмов для реальных задач.


  

import java.util.List;
import java.util.Collections;
import java.util.ArrayList;


public class GAHelloWorld {

public static final int POPULATION_SIZE = 1000;
public static final double ELITE_RATE = 0.1;
public static final double SURVIVE_RATE = 0.5;
public static final double MUTATION_RATE = 0.2;
public static final String TARGET = "Hello World!";
private static final int MAX_ITER = 1000;

void initializePopulation(List<Genome> population) {
int tsize = TARGET.length();

for (int i = 0; i < POPULATION_SIZE; i++) {
StringBuilder str = new StringBuilder();
for (int j = 0; j < tsize; j++) {
str.append((char) (Math.random() * 255));
}
Genome citizen = new Genome(str.toString());
population.add(citizen);
}

}



String mutate(String str) {
int tsize = TARGET.length();
int ipos = (int) (Math.random() * tsize);
char delta = (char) (Math.random() * 255);

return str.substring(0, ipos) + delta + str.substring(ipos + 1);

}

List<Genome> mate(List<Genome> population) {
int esize = (int) (POPULATION_SIZE * ELITE_RATE);
int tsize = TARGET.length();
List<Genome> children = new ArrayList<Genome>();

selectElite(population, children, esize);

for (int i = esize; i < POPULATION_SIZE; i++) {
int i1 = (int) (Math.random() * POPULATION_SIZE * SURVIVE_RATE);
int i2 = (int) (Math.random() * POPULATION_SIZE * SURVIVE_RATE);
int spos = (int) (Math.random() * tsize);

String str = population.get(i1).str.substring(0, spos) +
population.get(i2).str.substring(spos);
if (Math.random() < MUTATION_RATE) {
str = mutate(str);
}
Genome child = new Genome(str);
children.add(child);


}
return children;
}

private void selectElite(List<Genome> population, List<Genome> children, int esize) {
for(int i=0; i<esize; i++){
children.add(population.get(i));
}
}

private void go(){
List<Genome> population = new ArrayList<Genome>();
initializePopulation(population);

for (int i=0; i< MAX_ITER; i++) {
Collections.sort(population);
System.out.println(i + " > " + population.get(0));

if (population.get(0).fitness == 0) {
break;
}

population = mate(population);
}

}

public static void main(String[] args) {
new GAHelloWorld().go();
}

}
class Genome implements Comparable<Genome> {
final String str;
final int fitness;

public Genome(String str) {
this.str = str;
int fitness = 0;
for (int j = 0; j < str.length(); j++) {
fitness += Math.abs(str.charAt(j) - GAHelloWorld.TARGET.charAt(j));
}
this.fitness = fitness;
}

public int compareTo(Genome o) {
return fitness - o.fitness;
}

public String toString(){
return fitness + " " + str;
}

}


Результат работы генетического Hello World-а:
  
0 > 419 Un~?z^Kr??p┬
1 > 262 Un~?z^Kr?j?↨
2 > 262 Un~?z^Kr?j?↨

15 > 46 Afpdm'Ynosa"
16 > 46 Afpdm'Ynosa"
17 > 42 Afpdm'Ynoia"
18 > 27 Jfpmm↓Vopoa"

33 > 9 Ielmo▼Wnole"
34 > 8 Ielmo▲Vopld"
35 > 8 Ielmo▲Vopld"

50 > 1 Hello World"
51 > 1 Hello World"
52 > 0 Hello World!


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