?

Log in

 

swizard

About Свежие записи

Трамплины и продолжения 27 авг, 2016 @ 06:17
Любопытно, конечно, что наибольшую популярность завоёвывают именно плохие с инженерной точки зрения технологии. Я не могу объяснить этот феномен: казалось бы, согласно эволюционной теории "более лучшие" вещи должны постепенно заменять эквивалентные по функционалу "более худшие", но этого не происходит. И даже не всегда проблема в том, что что-то сложнее, а что-то легче: обычно, в плохо продуманных технологиях сложность как раз выше, просто она "отложенная".

Давайте, например, посмотрим на такие платформы: Common Lisp/Scheme, Haskell или OCaml. А потом на такие: Java или Javascript. В чём разница? Правильно, в одних есть хвостовая рекурсия, в других нет :)

Ладно, на самом деле, большинству программистов наджави эта рекурсия нафиг не сдалась. Полагаю, что многие и не подозревают даже что это такое, и подобное неведение никак не мешает им вполне комфортно существовать на свете. Но оная проблема встаёт достаточно остро для пользователей более вменяемых языков, которые используют джаву или js в качестве бэкенд-платформы. Например, Clojure для jvm или Elm для javascript. Эти языки предполагают функциональную парадигму программирования, и отсутствие TCO при этом причиняет серьёзные неудобства.

Честно говоря, натолкнувшись на переполнение стека в Elm, я был несколько ошарашен. Ничто не предвещает беды, вокруг тепло и уютно: с одной стороны, у тебя почти хаскель, с другой тебе было обещано отсутствие рантайм-исключений (если ты не выходишь за рамки чистого elm). И тут херак, привет из js:

RangeError: Maximum call stack size exceeded

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

Итак, давайте рассмотрим следующий синтетический пример:


isEven : Int -> Bool
isEven x =
    case abs x of
        0 -> True
        v -> isOdd <| v - 1


isOdd : Int -> Bool
isOdd x =
    case abs x of
        0 -> False
        v -> isEven <| v - 1


isSumEven : Int -> Int -> Bool
isSumEven a b =
    isEven a == isEven b


Я тут попытался смоделировать проблему: у нас есть две взаимно-рекурсивные функции (определяющие, чётное или нечётное число на входе) и одна утилитарная, которая их как-то использует (предсказывает, будет ли сумма двух чисел чётная).

Можно сразу посмотреть в репле, как они (не) работают:


> isEven 2
True : Bool
> isOdd 13
True : Bool
> isSumEven 100 1
False : Bool
> isEven 100000
RangeError: Maximum call stack size exceeded


Как их заставить работать, если платформа не поддерживает TCO? Никак, надо переписывать.

Общепринятая практика использовать в таких случаях технику, которая называется trampolining. Она широко используется, например, в Clojure. Идея там достаточно простая. Мы рефакторим функции, использующие рекурсию таким образом, чтобы:

  1. во всех местах, где производится рекурсивный вызов, вместо этого возвращалось наружу продолжение (достаточно просто обычного замыкания: thunk)
  2. на самом "верхнем" уровне выполняется обычный тупой цикл (trampoline), который последовательно вызывает отрефакторенную функцию до тех пор, пока она возвращает продолжения

Тем самым все функции перестают быть рекурсивными, и использование стека становится чётко детерминировано: из всех условных веток возвращаются либо результаты, либо замыкания (которые потом будут вызваны из трамплина).

В Elm, оказывается, есть даже микро-пакетик с трамплинами: elm-lang/trampoline. С его помощью можно переписать вышеприведённые взаимно-рекурсивные функции следующим образом:


import Trampoline exposing (Trampoline, done, jump, evaluate)


isEvenTr : Int -> Trampoline Bool
isEvenTr x =
    case abs x of
        0 -> done True
        v -> jump <| \() -> isOddTr <| v - 1


isOddTr : Int -> Trampoline Bool
isOddTr x =
    case abs x of
        0 -> done False
        v -> jump <| \() -> isEvenTr <| v - 1



В данном случае, всё получается достаточно прямолинейно: когда готов результат, возвращаем его через done, а когда нужно выполнить рекурсивный вызов, оборачиваем его в thunk и возвращаем через jump. Соответственно, в пакете trampoline лежит ещё функция evaluate, которая как раз крутит цикл, вызывая по-очереди все возвращаемые продолжения. Проверяем:


> evaluate <| isEvenTr 2
True : Bool
> evaluate <| isOddTr 13
True : Bool
> evaluate <| isOddTr 100000
False : Bool


Да, в этом варианте всё работает!

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


jump <| \() -> isOddTr <| v - 1


Лично я его автоматически написал сначала так:


jump <| always <| isOddTr <| v - 1


За что был наказан потерянным часом на отладку. Кто может предположить, в чём кроется засада? :) Для справки: always.

Ладно, возвращаемся к примерам. Как написать трамплин-версию isSumEven? В принципе, можно как-то так:


isSumEvenTr : Int -> Int -> Trampoline Bool
isSumEvenTr a b =
    done <| (evaluate <| isEvenTr a) == (evaluate <| isEvenTr b)


Конкретно для этого синтетического примера, наверно, такой вариант особо ничем не плох. Но всё же: можно ли обойтись только одним evaluate? Очевидно, что можно, если получится каким-то образом "попасть внутрь" типа Trampoline a, чтобы достать значение a или, хотя бы, как-то его преобразовать. Но вот незадача: этот тип не является функтором или монадой, никаких соответствующих комбинаторов для него нет, да и вообще это всё страшные слова, и такой мерзости у нас в эльме не водится! Следовательно, единственный вариант — это честно интерпретировать Trampoline a через evaluate. Или нет?

На самом деле, есть способ "состыковать" несколько Trampoline-ов, чтобы выполнить их в одном цикле-эвалюаторе: опять же, CPS. Но для этого нам опять нужно отрефакторить функции, на этот раз в continuation passing style:


isEvenTrK : Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isEvenTrK x k =
    case abs x of
        0 -> k True
        v -> jump <| \() -> isOddTrK (v - 1) k


isOddTrK : Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isOddTrK x k =
    case abs x of
        0 -> k False
        v -> jump <| \() -> isEvenTrK (v - 1) k


isSumEvenTrK : Int -> Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isSumEvenTrK a b k =
    isEvenTrK a <|
        \resultA ->
            jump <| \() -> isEvenTrK b <|
                \resultB ->
                    k <| resultA == resultB



Главное изменение: функции теперь не возвращают результаты напрямую (логически, они уже ничего не должны возвращать), вместо этого они принимают дополнительные параметр: "продолжение", которому этот результат передаётся. Теперь в isEvenTrK появилась возможность состыковать две "затрамплиненные" функции внутри продолжения, при этом сохранив тип возвращаемого значения Trampoline Bool, который уже скармливается единственному evaluate:


> evaluate <| isSumEvenTrK 100000 1 done
False : Bool
> evaluate <| isSumEvenTrK 100000 100000 done
True : Bool


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

Ну, в целом, как-то так. Далее полагается, чтобы я написал какие-то выводы или подытоги, но какие тут могут быть выводы? Сложно, запутанно. Но это и есть та самая "отложенная сложность", про которую я говорил в начале поста. Был бы в вашем джаваскрипте изначально родной TCO, я бы не писал этот текст, а вместо этого сделал бы что-нибудь полезное.

Вернуть итератор 23 авг, 2016 @ 05:36
А между тем, зацените, в nightly rust научились делать вот так:

#![feature(conservative_impl_trait)]

fn numbers() -> impl Iterator<Item = i32> {
    1 ..
}

Дословно, мы из функции возвращаем некоторый анонимный тип, всё что известно про которого — это то, что он реализует типаж Iterator, ассоциативный тип Item коего установлен в i32.

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

fn numbers() -> Box<Iterator<Item = i32>> {
    Box::new(1 ..)
}

… что плохо, потому что здесь одна совершенно ненужная аллокация, и итерация через vtable. Либо писать вот так:

fn numbers() -> std::ops::RangeFrom {
    1 ..
}

… что тоже омерзительно, по ряду причин:
  • Надо знать возвращаемый тип, а он может быть сильно составным (и будет, в случае с лесенкой преобразований итератора).
  • Зачастую приходится оборачивать его в newtype, чтобы не экспортировать из модуля кишки (и имплементировать соответствующий Deref).
  • В некоторых случаях тип вообще невозможно прописать руками, например, когда generic биндится замыканием (а тип замыкания нельзя написать руками).

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

Помимо итераторов, данная возможность даст возможность возвращать замыкания перемещением (by move), как-то так:

#![feature(conservative_impl_trait)]

fn adder(a: i32) -> impl Fn(i32) -> i32 {
    move |x| x + a
}

Это ваще космос. По факту можно будет с относительным комфортом писать в функциональном стиле на языке, в котором нет garbage collector (!!), и при этом без сегфолтов и утечек.

Да, и ещё формат ошибок в Rust теперь слизали с Elm, и они теперь выглядят максимально подробно:


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

Вероятностные алгоритмы. 5 июн, 2016 @ 03:06

Введение.

Традиционным образом (то есть, в самые последние сутки дедлайна) я поучаствовал в конкурсе, организованном ребятами из конторы Hola.

Задание было придумано очень крутое. "Очень крутое" -- это, в моём понимании, такое задание, которое:

  1. Имеет практическую ценность.
  2. Не подразумевает одного единственного верного решения, до которого просто нужно додуматься в процессе конкурса.

Полностью условие можно почитать на офсайте, а вкратце оно звучит так:

  • Дан словарь из ~660k записей. Ориентировочно, это английские слова.
  • Надо написать функцию "test(word)", которая возвращает true, если заданное слово входит в словарь, и false, если нет.
  • Суммарный объём программы и файла с данными, которым она может пользоваться, не должен превышать 65536 байт.
  • Побеждает решение, которое даст максимальный процент правильных ответов на большом количестве тестов.

Чтобы было повеселее, в тестах используется специальный генератор слов, которые визуально (и грамматически) очень похожи на нормальные английские, но при этом в словаре их нет, например: "goldrunk". И, напротив, в заданном словаре есть весьма странные записи, в которых распознать английский язык очень сложно, например, "qwertys" или "rRNA".

Согласно комментариям участников в соответствующем треде на хабрахабре, основные идеи (успешных) решений были следующие:

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

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

Немного теории.

В статье на русскоязычной википедии говорится, что: "Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью". Это не совсем так -- принципиально, к ГСЧ в вероятностных алгоритмах обращаться необязательно. В англоязычной версии этой статьи есть более корректное определение: "uniformly random bits". Опять же, экономия может достигаться не только во времени работы, а по памяти, например.

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

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

Самое главное, что здесь нужно запомнить, это фразу: дискретно-равномерное распределение. "Равномерное распределение" на практике должно означать следующее: если случайная величина (ГСЧ, хэш-функция, значение сигнала) генерирует нам какое-то значение из интервала R, нужно, чтобы вероятность получения каждого значения из R была 1/R (или, хотя бы, очень близко к этому). При этом количество таких значений должно быть конечно (дискретно). Визуально, это выглядит следующим образом: допустим, мы взяли поле 10x10 и ткнули в рандомную точку. Получилось, например, как-то так:

А если мы воткнули их несколько тыщ, то должно получиться относительно равномерное покрытие, что-то типа такого:

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

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

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

Немного практики.

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

  • Locality-sensitive hashing: подбирает для множества элементов хэш-функцию таким образом, что "схожие" элементы попадают в одну корзину (хеши дают коллизию ожидаемым образом). Таким образом достигается существенное уменьшение размерности данных, и используется, например, в задачах кластеризации.
  • MinHash: ускорение расчёта коэффициента Жаккара для вычисления степени схожести двух множеств. Широко используется, например, для задач выявления нечётких дубликатов среди большого количества документов.
  • Семплирование потока данных. В отличие от простой выборки каждого N-ого элемента из потока, хешируют некоторый составной ключ (например, "пользователь"/"запрос"/"таймстамп"), после чего берут N корзин, и отбрасывают все результаты, не попавшие в одну из них. Это позволяет семплировать поток по сложным условиям, избегая дорогостоящей группировки.
  • Flajolet–Martin algorithm, и его развитие в виде HyperLogLog. Алгоритмы используют достаточно изящный хак для быстрой аппроксимации количества уникальных элементов в заданном множестве. Я реально советую ознакомится с описанием, это, действительно, хитрый трюк :)

Конкурсная задача.

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

Самый простой вероятностный алгоритм, который можно придумать, это подбрасывание монетки:

function test(word) {
    return Math.random() < 0.5;
}

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

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

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

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

Применив K таких случайных хеш-функций к одному и тому же аргументу (например, слову из словаря) мы получим K результатов, которые будут, опять же, случайно распределены по всему диапазону значений fnv. Я взял 32-х битную версию, соответственно, результаты хеширования будут в диапазоне 0 - 0xffffffff. Дальше надо как-то убедиться, что эти результаты имеют равномерное распределение. Этот факт явно каким-то образом должен доказываться, но я, к сожалению, не математик, поэтому тупо нарисовал график и посмотрел на него глазами. Выглядит как равномерное :) Это свойство в данном случае мне важно для того, чтобы можно было оценить вероятность того, что случайная хэш-функция даст конкретное значение. При равномерном распределении эта вероятность будет 1/R, где R = 232.

Дальше сделаем вот что: возьмём одну такую случайную хеш-функцию H, и прогоним через неё все N слов из словаря. Получим N чисел (хешей слов), которые как-то случайным образом будут раскиданы в интервале от 0 до 232 - 1. Теперь нам надо найти какое-то такое утверждение P, которое бы:

  1. Выполнялось бы для всех полученных чисел.
  2. Не выполнялось для как можно большего количества остальных чисел из [0, 232).

Идея понятна: алгоритм получает слово, считает от него хеш с помощью хеш функции H, проверяет результат на условие P, и, если оно ложно, то это слово точно не из словаря. Если условие истинно, то слово, с какой-то вероятностью, может быть в словаре. С какой? Это зависит от природы утверждения P. Далее нам достаточно провести несколько проб (повторить алгоритм несколько раз для различных хеш-функций), с каждым разом увеличивая вероятность срабатывания P, чтобы достичь удовлетворяющей нас достоверности ответов.

Допустим, к примеру, сложилось такая ситуация, что все хеши слов из словаря оказались чётными. Тогда все нечётные значения из интервала от 0 до 232 означали бы true negative. Вероятность этой ситуации (хеш проверяемого слова оказался нечётным) была бы почти 0.5 -- это очень крутой результат для одной только пробы. Ведь тогда нам для достоверности ответа "слова точно нет в словаре" в 99% достаточно log0.50.01 = ~7 проб, то есть, всего семь рандомных хеш-функций.

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

Конкретно под наш словарь можно попробовать делить всё множество значений хеш-функций не на две корзины (чётные и нечётные числа), а на большее количество: M > 2. Тогда нашей задачей будет подобрать для каждой используемой хеш-функции такое (в идеале, минимальное) количество корзин, чтобы при хешировании всех слов из словаря одна из корзин оказалась пустой.

Если значения хеш-функций имеют равномерное распределение (а они имеют в нашем случае), вероятность попадания хеша в одну из корзин будет равняться 1/M. Каким же должен быть M, чтобы, раскидав по этому такому количеству корзин 660 тысяч хешей, у нас бы осталась одна пустая корзина? Это как-то явно подсчитывается при помощи математики, но (если вы, подобно мне, ничерта не помите из тервера) можно немного схалтурить, и получить нужные цифры при помощи несложного программирования.

Проведём эксперимент: сгенерируем нужное количество 32-х битных случайных чисел, по одному на слово из словаря -- как будто, это результаты хеширования. Программный ГСЧ должен давать равномерное распределение, и хеш-функция тоже даёт равномерное распределение, так что это относительно равноценная замена. Далее тупо брутфорсом попробуем подобрать минимальное количество корзин так, чтобы в одну из них ни одно рандомное число не попало. Вот как это примерно может выглядеть на Common Lisp:

(defun get-minimum-buckets-count (words-count)
  (iter
    ;; generate pseudo hashes
    (with pseudo-hashes =
              (iter (repeat words-count)
                    (collect (random (ash 1 32)) result-type simple-vector)))
    (for buckets-count from 2)
    ;; make buckets with hit counters
    (for buckets-hits =
         (make-array buckets-count
                     :element-type 'fixnum
                     :initial-element 0))
    ;; collect hits
    (iter (for i from 0)
          (for hash in-sequence pseudo-hashes)
          (for bucket = (mod hash buckets-count))
          (incf (elt buckets-hits bucket)))
    ;; check whether an empty bucket exists
    (for empty-bucket = (position 0 buckets-hits))
    (when empty-bucket
      (return-from get-minimum-buckets-count
        (values buckets-count empty-bucket)))))        

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

Запустив эту функцию для 660000 слов, мы (через некоторое время) получим результат для M порядка ~33000. Разумеется, при каждом запуске он будет разный (так как псевдо-хеши генерируются каждый раз случайным образом), но это будут всегда приблизительно одинаковые значения с небольшим разбросом. На практике это означает, что мы можем получить с одной пробы вероятность 0.00003, что слово не входит в заданный словарь: для этого достаточно проверить, что хеш слова попал в пустую корзину. На первый взгляд совсем мизерный шанс, но давайте прикинем, что с этого можно получить.

Итак, мы можем взять одну рандомную хеш функцию H0, словарь, и найти для них два числа: M0 (минимальное количество корзин, раскидывая хеши по которым образуется одна пустая), и B0 (номер пустой корзины). Эти два числа описывают пробу P0, которая даёт шанс в 0.003%, что проверяемое слово точно не принадлежит словарю. Если же мы посчитаем таким же образом P1 для другой функции H1, мы сможем провести две независимые пробы, увеличив вероятность true negative до 0.00006 (вероятность не попасть в пустую корзину для одной пробы равняется 1.0 - 0.00003 = 0.99997, а для двух независимых проб вероятности умножаются). Аналогично, десять подобных проб дадут уже вероятность в 0.03%, сто в 0.3%, а десять тысяч, например, целых 26.1%. Продолжая этот ряд, можно подобрать число 153000 -- именно столько проб нужно выполнить, чтобы с вероятностью 99% определить true negative.

Одна проба однозначно задаётся двумя числами M и B, соответственно, для 150-ти тысяч проб нужно сохранить 300 тысяч чисел. Это явно больше того, что можно запихать в заданные задачей лимиты. Нетрудно прикинуть, что, если мы аллоцируем, ориентировочно 14 бит для M и 15 бит для B, в 64 Kb можно вместить всего порядка 18000 проб. А ведь там ещё должно остаться какое-то место для сценария на js! Соответственно, чуть более реалистичная цифра в 17000 проб даст вероятность определения true negative в ~40%.

Что это означает на практике? Это означает следующие вещи:

  • Если на вход функции test было подано слово из словаря, все пробы будут успешными (хеши не попадут в пустые корзины), и будет возвращена истина. Это true positive.
  • Если на вход функции test было подано слово не из словаря, то:
    1. с вероятностью 40% одна из проб даст неуспех (один из хешей попадёт в пустую корзину), и будет возвращена ложь. Это true negative.
    2. с вероятностью 60% все пробы, всё же, дадут успех, и будет возвращена истина. Это false positive.
  • Ситуация false negative в данной конфигурации невозможна, потому что мы, формируя множество проб, специально так подбирали числа M, чтобы для слов из словаря обязательно оставалась пустая корзина.

Итоговый процент верных ответов зависит от характера тестовых данных: в худшем случае он будет стремиться к 40% (если на вход подаются только слова не из словаря), в лучшем -- к 100% (если на входе только слова из словаря), а в случае половина тех, и половина других, это должно быть значение порядка 70%.

Эту цифру можно чуть-чуть улучшить, параллельно значительно упростив формат сериализованной пробы (что тоже немаловажно, ведь размер js-скрипта тоже имеет значение). Можно подбирать M специальным образом, чтобы пустая корзина оказывалась всегда, например, в нулевой позиции (B == 0, или H % M == 0). В этом случае для записи пробы нам достаточно только одного числа M. Эксперименты показывают, что это получаются значения из диапазона примерно 38000 - 91000: это означает, что соответствующие вероятности для проб будут меньше, но зато для их упаковки теперь достаточно 16 бит, следовательно количество проб можно увеличить до ~32000, и, главное, сильно упростить код для их упаковки/распаковки.

Конечно, полученная цифра в 70% верных ответов выглядит не очень впечатляюще. Но следует отметить две вещи про это решение:

  1. Удивительная простота алгоритма в целом, и элементарная масштабируемость: для достижения нужной точности нужно просто последовательно увеличивать количество проб.
  2. Это абсолютно "чистый" и "честный" результат: на нетронутых оригинальных входных данных, когда словарь взят полностью как есть. Всегда можно приложить некоторые усилия к препроцессингу: порезать слова, оканчивающиеся на "'s", разделить на префиксы/суффиксы, и т.п. Ребята в комментариях к задаче на хабрахабре писали, что они относительно безболезненно уменьшали словарь до 280000 записей. А 280 тысяч хешей в нашем алгоритме уже означают M ~ 13000, что, в свою очередь, даёт вероятность одной пробы 0.0076% и порядка 18000 проб в 64 Kb, выдающих, суммарно, почти 75% true negative! А это уже больше 87% верных ответов для случая 50/50 словарных и не словарных слов.

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

Полностью моё решение, вместе с расчитанными данными, можно взять в этом репо: сами хеши я породил из js (директория generator), а компилятор проб из них сделал на Rust (директория compiler).


Геймификация скучных процессов 25 апр, 2016 @ 23:18
13 апреля я опубликовал пост с текстом интересной, как мне тогда казалось, вакансии, и он провисел неделю. Много ли за эту неделю заинтересовалось ей людей? Нуль!
19 апреля я предложил развлекательную тестовую задачку для потенциальных кандидатов и им сочувствующих, и внезапно за одну такую же неделю мне наприсылали какие-то полчища резюме, что я даже немного впал в ступор :) Честно говоря, начал даже понимать профессиональных эйчаров, это не такая уж и простая работа, оказывается.

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

Задачка для интересу 19 апр, 2016 @ 00:38
Чёто вакансия вызвала интерес у удивительно малого количества народу, я даже затрудняюсь объяснить этот феномен :) Все так недолюбливают Эрланг? Но у меня же ещё Elm и Rust, и вообще, потенциально определённая свобода в этом плане. Пишите, когда ещё вам предложат попрограммировать с пользой на чём-то неунылом за деньги :)

Для подогрева интереса к вакансии выкладываю тестовую задачку для потенциальных кандидатов. А то чё я её зря что ли придумывал.
UPD 2016-04-20: добавил "sample_9".
UPD 2016-04-21: пофиксил рефенсные тайминги.

Итак, задачка из трёх частей, в порядке увеличения сложности. Делать надо на эрланге, если умеете эрланг, или на чём угодно, если не умеете. Ориентировочные критерии оценки такие:
  • Если человек сделал первую часть, то хорошо: с ним уже есть о чём говорить.
  • Если получилась вторая — очень хорошо.
  • Если третья — совсем круто!

Общее условие

Дана программа в виде упрощённого S-expression (что это?), например:

sample_1() -> <<"(+ (* 4 4) (* 2 (- 7 5)) 1)">>.

где первый элемент каждого списка — это операция (всего их три вида):
  1. сложение: атом "+"
  2. вычитание: атом "-"
  3. умножение: атом "*"
Все остальные возможные атомы — это целые числа.
Ещё примеры:

sample_2() -> <<"10">>.
sample_3() -> <<"(* 10 (- 0 1))">>.
sample_4() -> <<"(- (+ 10 10) -5 0)">>.
sample_5() -> <<"(+ (- (* (+ (- (* 1))))))">>.
sample_6() -> <<"(* 2 (+ (- 10 9) (- 3 (* 2 1))) (+ (- 10 9) (- 3 (* 2 1))))">>.
sample_7() -> <<"(+ (* 2 1) (+ 8 8) (- (+ 4 3 2 1) (* 3 3) (* 2 2)) (* 5 7))">>.
sample_8() -> <<"(- (+ (+ 3 3) (- 3 3) (+ 3 3) (- 3 3)) (* 2 2))">>.
sample_9() -> <<"(+ (- 6 1) (+ 0 1 1) (- 7 2) (* 3 4 5) (- 3 1) (+ 2) (- 0 10))">>.

Задача 1

Реализуйте функцию-интерпретатор "interpret/1" и вычислите результаты вышеприведённых программ.

Например:
interpret(sample_1()). --> 21
interpret(sample_2()). --> 10
interpret(sample_3()). --> -10
interpret(sample_4()). --> 25
interpret(sample_5()). --> 1
interpret(sample_6()). --> 8
interpret(sample_7()). --> 50
interpret(sample_8()). --> 8
interpret(sample_9()). --> 66

Задача 2

Представим, что все операции в программе имеют константную задержку, которая не зависит от процессора. Например, это некоторого рода длительная сетевая активность.
Итого, реализация каждой из операции теперь должна содержать вызов "timer:sleep(X)":
  • X = 2000 ms для сложения "+"
  • X = 3000 ms для вычитания "-"
  • X = 10000 для умножения "*"

Реализуйте функцию-интерпретатор "interpret_network/1", которая вычисляет результат заданной программы с минимально возможной задержкой.

Например:
interpret_network(sample_1()). --> 21 (delay 15 s)
interpret_network(sample_2()). --> 10 (delay 0 s)
interpret_network(sample_3()). --> -10 (delay 13 s)
interpret_network(sample_4()). --> 25 (delay 5 s)
interpret_network(sample_5()). --> 1 (delay 30 s)
interpret_network(sample_6()). --> 8 (delay 25 s)
interpret_network(sample_7()). --> 50 (delay 15 s)
interpret_network(sample_8()). --> 8 (delay 13 s)
interpret_network(sample_9()). --> 66 (delay 12 s)

Задача 3

Представим, что все операции в программе имеют константную задержку, которая зависит от процессора. Например, это некоторого рода тяжелые вычисления, выедающие 100% ядра процессора.
Наша машина оборудована N физическими ядрами.
Итого, реализация каждой из операции теперь должна содержать вызов "timer:sleep(X)", при этом максимальное количество "одновременно выполняющихся" операций должно быть меньше или равно N:
  • X = 2000 ms для сложения "+"
  • X = 3000 ms для вычитания "-"
  • X = 10000 для умножения "*"

Реализуйте функцию-интерпретатор "interpret_cpu/2", которая, используя процессор максимально оптимальным образом, вычисляет результат заданной программы с минимально возможной задержкой.

Например:
interpret_cpu(sample_1(), 2). --> 21 (delay 15 s)
interpret_cpu(sample_2(), 2). --> 10 (delay 0 s)
interpret_cpu(sample_3(), 2). --> -10 (delay 13 s)
interpret_cpu(sample_4(), 2). --> 25 (delay 5 s)
interpret_cpu(sample_5(), 2). --> 1 (delay 30 s)
interpret_cpu(sample_6(), 2). --> 8 (delay 28 s)
interpret_cpu(sample_6(), 3). --> 8 (delay 25 s)
interpret_cpu(sample_7(), 2). --> 50 (delay 26 s)
interpret_cpu(sample_7(), 3). --> 50 (delay 22 s)
interpret_cpu(sample_7(), 4). --> 50 (delay 15 s)
interpret_cpu(sample_8(), 2). --> 8 (delay 15 s)
interpret_cpu(sample_8(), 3). --> 8 (delay 13 s)
interpret_cpu(sample_9(), 2). --> 66 (delay 15 s)


Приглашаю всех желающих порешать, код выкладывайте на какой-нибудь gist и давайте ссылку в комменты. Свой вариант я выложу ближе к концу недели.
Other entries
» А вот, например, вакансия.
У нас же здесь явно могут оказаться релевантные люди, кому это может оказаться интересным. Короче, образовалась вот такая вакансия в нашей конторе: нужен человек, которому я смог бы передать один из своих текущих проектов. Там никакого особенного рокетсаенса, но проект нужный, важный, и ответственный.

От кандидата требуется:
  • Знание, или устойчивое желание и возможность освоить Erlang + OTP.
  • Знание основных паттернов проектирования систем обмена сообщениями.
  • Опыт сетевого программирования.
  • Навыки работы с linux.

Плюсами будут:
  • Опыт проектирования и разработки высоконагруженных сервисов.
  • Опыт работы с большими объёмами данных.
  • Знание функциональной парадигмы программирования.
  • Знание языков (или желание освоить) Elm и Rust.
  • Опыт работы с:
    • RabbitMQ
    • Apache Cassandra
    • Redis
    • cowboy http server
  • Навыки работы с freebsd.

Работа на полный рабочий день: по желанию либо в офисе (Москва, ул. Верейская), либо удалённо, с регулярным посещением офиса для совещаний. Белая зп, 130-250к (вилка большая, крутому и матёрому спецу тоже будем рады).

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

На этот раз обнаружил вот такую: http://wunderfund.io/dev_job — это типа тестовая задача для вакансии разработчика в какой-то мутной конторе.

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

Тут меня уже, надо сказать, одолела злоба. Особенно подбешивало описание задачи в разделе вакансии: "Если ты нам подходишь, решение задачки не составит для тебя труда." :) А тут, получается, что решение для меня составляет труд, и моя кандидатура не подходит на вакансию какого-то рядового плюсового разработчика, например.

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

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

А сегодня меня мне вдруг в голову пришла мысль. Я её проверил, и мои самые страшные подозрения подтвердились!

Короче, дело было так:

Я скачиваю .csv-шку с сайта и открываю её штатным маковским Numbers. Вижу примерно такое:



Ну хорошо, думаю, мак глупый, хочет в качестве разделителя столбцов точку с запятой согласно локали, а там просто запятая. Ну там данные простые, поэтому я не мучаюсь с форматированием, а просто тупо беру и забиваю в коде в данные всё, что после запятой (типа, второй столбец — 7, 688, 682 и тд).

Сегодня до меня дошло посмотреть в исходник .csv-шки. Оказывается, это нихрена не 7 и 688, а 7000 и 6880 =) А табличный процессор терминирующие нули радостно откусил, потому что, согласно тем же настройкам локали, запятая является разделителем дробной части числа. И "0,7000" оказалось не двумя столбцами с "0" и "7000", а одним столбцом с числом "0.7".

Короче, с правильными данными результат у меня-таки сошёлся. Но самое обидное даже не в этом, а в том, что с этими данными никакой код можно было вообще не писать — достаточно просто на них пристально посмотреть и воспользоваться калькулятором :(
» Медицинская карта
Тыщу лет уже не был в районной поликлинике. Вроде пока особо ничем не болею, поэтому по мелким рандомным поводам предпочитаю посещать платную, чисто чтобы время сэкономить. А там у них всех компы, и медицинская карта в электронном виде, в бд. И за пару лет у меня накопилась там полноценная история болезни: все визиты врачей, со всеми жалобами, и тд.

Выглядит эта история примерно так:
  1. Всего три обращения к врачам.
  2. Все три обращения — к хирургу.
  3. Список жалоб:
    • Укус котом.
    • Укус котом.
    • Укус котом.

В примерно таком виде:


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

Раньше было вот так:



Почти весь маршрут получался по паркам и набережным, всегда везде почищено, где-то на 2/3 пути с велодорожками. Порядка 13 км, по времени минут 45, что быстрее метро и автомобиля (если включать время на поиск парковки), но медленнее мотоцикла (рекорд был 9 минут по пробкам).

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

По-факту вышло пока как-то так:



Это даже меньше по расстоянию, чем было (~10 км), но тупо вдвое дольше — около полутора часов. Дофига отрезков, где приходится ехать медленно. В районе матвеевского (там где долина реки Раменки) по нынешней погоде ваще только пешком. Много мест, где приходится форсировать сугробы. Короче, надо ещё разбираться, пока ничего не понятно :)


» Смертоносные свиньи жидкого герметизатора
Подумалось чёто про бигдату. Гугл, например, ходит и прилежно индексирует интернет, в котором, благодаря нашим друзьям сеошникам и прочим спамерам, процентов 50 текстов выглядит как-то так:



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

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

Основная масса потока, это разнообразный спам и другие роботы, а львиная часть остального — твиты, вида: "@LAWBDM пожалуйста *осторожно погладила по голове*" и "ну почему почему напиши плес пожалуйста я же писала напиши веду себя как телка господи аааа*". Можно, конечно, майнить по конкретным аккаунтам, но выборка получается очень смещённая, ничего по этому предсказать нельзя.

Похоже, что у нас в 21 веке появилось много полезных инструментов для бигдаты, но вот самой даты в интернете что-то нет. Наверно, единственно полезное её применение — это обработка научных данных (с телескопов там, датчиков/зондов и тд).
Top of Page Разработано LiveJournal.com