Purely functional data something

[kika]

Имхо, довольно распространенная задача. Скажем у нас есть множество структур, описывающих некую жызненную ситуацию, скажем мониторинг хостов в сети. Структура содержит имя хоста, адрес, всякие прочие фактически иммутабельные параметры плюс некое количество изменяющихся параметров мониторинга, время пинга, скорость передачи данных, количество HTTP ошибок и теде и тепе. Структуры хранятся, допустим для простоты, в хеше по имени хоста. Все отлично, софтина работает, обмеряет хосты, апдейтит табличку с записями и жизнь прекрасна. Теперь нам надо сделать запросы снаружи - типа а покажи-ка мне список хостов, отсортированных по пингу. Допустим, хостов у нас ровно один газиллион, поэтому сортировать на каждый запрос накладно.
В традиционной культуре мы строим сбалансированные деревья с указателями на структуры (а в структурах указатели на деревья) и организуем синхронное плавание.
А как в функциональной культуре решается такая задача? Pointer trickery тут какбе немного недоступна.

Вкратце: есть структура -record(host, {host_id, speed = 0}). и из нее ETS таблица из одного газиллиона записей. Надо быстро отдавать список хостов, отсортированный по speed. Можно наверное положить это в Мнезию и понадеяться на ее ORDER BY, а если без Мнезии, ручками?

Comments

[lionet.livejournal.com]

Организуем несколько деревьев. Одно — hostname → record(host). Другие — term → hostname. Джойны ручками, как и в ООП, разницы нет здесь в подходе к джойнам. В чём есть оптимизация сложности имплементации — это в возможности ленивого join'а тем же хаскелем, тобы не городить producers/consumers деревьев.

[kika.livejournal.com]

term→hostname - это в данном случае speed→hostname ? А как мне тогда проапдейтить дерево, когда я скорость пересчитал? В классической культуре у меня из ноды таблицы сразу ссылка на ноду в дереве, я ее удаляю и вставляю заново с новой скоростью.

[lionet.livejournal.com]

Псевдокод:

updateDerivedTree(DerivedTree, Hostname, Speed, Speed) -> ok;
updateDerivedTree(DerivedTree, Hostname, OldSpeed, NewSpeed) ->
    transform(DerivedTree, fun(
      {Speed, Host, Counter} when Speed == OldSpeed, Counter == 1 -> remove;
      {Speed, Host, Counter} when Speed == OldSpeed -> {replace, {Speed, Host, Counter-1}};
      _ -> ignore
    end),
    TransformResult = transform(DerivedTree, fun(
      {Speed, Host, Counter} when Speed == NewSpeed -> {Speed, Host, Counter+1}
      _ -> ignore
    end),
    case TransformResult of
      found -> ok;
      notfound -> add(DerivedTree, {Speed, Host, 1})
    end).

[kika.livejournal.com]

что делает transform/2 ? Обходит все дерево и прикладывает к каждой ноде fun?

[lionet.livejournal.com]

Вызывает двоичный поиск по ключу (ключ забыл явно вторым аргументом указать). O(logN). Когда найдёт ключ, то вызывает функцию, и осуществляет операцию, которая этой функцией была подсказана, и либо оставляет дерево в покое, либо трансформирует текущую ноду.

[kika.livejournal.com]

А ключом у тебя в дереве является скорость? А то что половина хостов имеют скорость 0, никому не помешает?

[lionet.livejournal.com]

А в чём дело? Если они просто её "имеют" — то дерево не перестраивается и даже не читается, так как срабатывает short-cirquit в псевдокоде, первой же строчкой.

А если значения флуктуируют в очень небольшом промежутке, тогда всё зависит от способа организации этого bag'а: есть ли в нём возможность указать secondary key. В простейшем случае можно сделать двухуровневый set: на первом уровне ключём является скорость, на втором - хост. Экстраполируя, получаем API для бэгов произвольной глубины:

transform(MultiBag, Keys, TransF) -> Result
Types   MultiBag = gb_trees()
       Keys = [term()]
       TransF = fun(Entry) -> retain | {replace, Entry} | delete

Пример:

transform(…, [0, "localhost"], fun({0, "localhost", _Key}) -> retain end).

[kika.livejournal.com]

Флуктуируют они в адском промежутке, конкретно скорость может колебаться от нуля до wire speed. Но идею я понял, спасибо.

[lionet.livejournal.com]

А если значения флуктуируют в очень небольшом промежутке

Фигню сморозил, конечно, очередной раз. Флуктуировать они могут как угодно, тут от степени флуктуации ничего не зависит.

[kika.livejournal.com]

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

[lionet.livejournal.com]

O(logN), он и в африке O(logN), даже с большой константой. А учитывая то, что при использовании эрланга ты уже получаешь фактор ~3-10x от скорости C, плюс-минус два в середине очень короткого цикла не должно волновать ;)

[kika.livejournal.com]

Ктоб ерлангу хороший компилятор написал...

[lionet.livejournal.com]

В случае решения на императивщине, сложность O(logN) на апдейтах.
В случае показанного выше решения — сложность O(logN) на апдейтах.