День восьмой (Неслучайные числа)

ЗАДАЧА
Мультипликативный датчик и плохие параметры.

РЕШЕНИЕ
Один из способов генерации псевдослучайных чисел - мультипликативный датчик

rndvec <- function(len, m, d) {
  k <- 1
  vec <- vector()
  for (i in 1:len) {
     k <- (k * m) %% d
     vec[i] <- k/d 
  }
  vec
}

при m == 2^16 + 3, d == 2^31 даёт следующее распределение на кубе:

> vs <- rndvec(9999, 2^16 + 3, 2^31)
> x <- vs[vs %% 3 == 0]
> y <- vs[vs %% 3 == 1]
> z <- vs[vs %% 3 == 2]
> library(rgl)
> plot3d(x, y, z)

казалось бы, случайное и равномерное... Но если взглянуть на куб под другим углом: Тройки vs[3*i], vs[3*i + 1], vs[3*i + 2] образуют параллельные плоскости. Ни о какой случайности речи быть не может.

ВЫВОД
Несмотря на интуитивно понятную ушербность ("почти кратность" параметров), именно с такими параметрами датчик в своё время попал в одну из библиотек для IBM-360. Исторический факт.

БОНУС
Из картинок подобного рода сразу вспоминается исследование случайности ISN, для различных ОС. newtcp и oldtcp

День седьмой (Pipe operator)

 ЗАДАЧА
Поиск удобных способов организации кода. Реализация оператора |>. Частичная аппликация.

РЕШЕНИЕ
Интересное наблюдение - в R аргументы передаются фактически в виде ассоциативного списка, а значит, можно было бы реализовать 'каррирование по ключу'. Что это значит?

># в псевдокоде:

>paste_dot_sep <- paste((collapse='.')) 

># Это тоже, что paste_dot_sep <- function(x) paste(x, collapse='.') 

># Допустим и другой синтаксис.

>paste_dot_sep(c(1,2,3))

[1] "1,2,3"

Зачем это нужно?
Для удобства кодирования. Например,

># в псевдокоде:

> aff <- function(k, x, b) k*x + b

> scale10 <- aff((k=10)) # 10*x + b

> bias10  <- aff((b=10)) # k*x + 10

Язык не поддерживает и просто частичную аппликацию, поэтому будем эмулировать нужную функциональность с помощью:

> fn_ <- function(fun, ...) (function(x) fun(x, ...))

Из F# позаимствуем оператор |>.

> '|>' <- function(dat, ...) { 

            res <- dat

            funs <- list(...) 

            for (f in funs) res <- f(res) 

            res 

          }

Вот как можно использовать:

>'|>'(69, as.character, fn_(strsplit, ''), unlist, rev, fn_(paste, collapse=''), as.numeric)

[1] 96

> # или

> dat.str <-'1 2 3

+ 4 5 6

+ 7 8 9'

> '|>'(dat.str, fn_(strsplit, ' |\n'), unlist, as.numeric, fn_(matrix, nrow=3))

     [,1] [,2] [,3]

[1,]    1    4    7

[2,]    2    5    8

[3,]    3    6    9

> # 'корявая' альтернатива: '|>'(dat.str, fn_(strsplit, ' |\n'), fn_(get('[['),1), as.numeric, fn_(matrix, nrow=3))

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

ВЫВОД
В R не реализовано каррирование функций. Упрощает или, наоборот, усложняет это жизнь пользователям - спорный вопрос. На мой взгляд, разработчики должны в большей степени ориентироваться на "функционализацию" языка, чем на историческую совместимость с S и бесполезные игры с quote, eval, expression и пр. По большому счёту, есть HOF, функции - first class citizens, что мешает добавить каррирование? Аргументы по умолчанию - это лишь шаг в правильном направлении.

БОНУС
По наводке palm_mute узнал, что ocaml поддерживает подобную фунциональность с помошью labels.

О результатах Netflix contest

В декабрьском номере scgn за прошлый год была интересная статья о конкурсе на миллион от Netflix и промежуточных результатах.

В ней рассказывается о весьма драматической победе BellKor/KorBell. Впечатляет. После описания данных и условий конкурса идёт обзор различных стратегий для рекомендательных систем типа Collaborative Filtering и их комбинаций.

По ходу дела авторами было разработано несколько новых методов, да опубликовано несколько статей в ACM.