неожиданно, действительно ли для среднего арифметического list ranking нужно? Мне казалось, что-то более близкое к "TreeScan" в их терминах, правда там только последний результат нужен, так что код чуть попроще должен быть. (В смысле мне действительно интересно, т.к. всю радость с NESL я уже успел подзабыть)
Позиция в списке может быть взвешенной - суммой весов элементов "до". У обычной позиции в списке (list ranking) вес всегда 1. Тогда, комбинируя взвешенную и обычную позицию мы получаем среднее при применении одного и того же алгоритма.
не уверен, что до конца понял. Давай я проиллюстрирую как бы делал я, а ты скажешь, чем это отличается от того, что надо?
function fold(op,identity,a) = if #a == 1 then a[0] else let e = even_elts(a); o = odd_elts(a); in op(fold(op,identity,e),fold(op,identity,o));
function avg(a) = let x = fold('+,0,a); in x / #a;
avg([2, 8, 3, -4, 1, 9, -2, 7]);
тут мы делим список на четные и нечетные элементы, и т.д. (глубина log(N)), и сворачиваем (глубина N), простой вариант правда будет работать только для ассоциативной функции. Если нету O(1) функции длины (#a), то длину получать таким же образом.
Мой вариант: function pointer_jump_part_sum(pt,val, xs) = let npt = pt->pt; nval = {v + nv: v in val; nv in val->pt};
nxs = {x + nx*(if nv == 0 then 0 else 1): x in xs; nx in xs->pt; nv in val->pt; v in val}; in if eql(npt,pt) then (val, nxs) else pointer_jump_part_sum(npt,nval, nxs);
function wyllie_list_rank_part_sum(pt, xs) = let % set value to 1 everywhere except at the tails % val = {if i==pt then 0 else 1: pt; i in [0:#pt]}; in pointer_jump_part_sum(pt,val, xs);
% This example contains the two lists 0,1 -> 2,2 -> 1,3 -> 5,4 -> 6,5 4,6 -> 7,7 -> 3,8 % wyllie_list_rank_part_sum([2, 5, 1, 3, 7, 6, 6, 3], [1,2,3,4,5,6,7,8]);
%wyllie_list_rank_part_sum([0, 1, 2, 3, 5, 6, 7, 7], [1,1,1,1,1,1,2,1]); % Не считает последний элемент (для первого списка сумма 12, для второго - 13, соответственно, выпали 8 и 3). Это решается дополнительным параметром, но мне уже лень.
Comments 6
Reply
правда там только последний результат нужен, так что код чуть попроще должен быть.
(В смысле мне действительно интересно, т.к. всю радость с NESL я уже успел подзабыть)
Reply
Короче, мы "свели задачу к предыдущей". ;)
Reply
function fold(op,identity,a) =
if #a == 1 then a[0]
else
let e = even_elts(a);
o = odd_elts(a);
in op(fold(op,identity,e),fold(op,identity,o));
function avg(a) =
let x = fold('+,0,a);
in x / #a;
avg([2, 8, 3, -4, 1, 9, -2, 7]);
тут мы делим список на четные и нечетные элементы, и т.д. (глубина log(N)), и сворачиваем (глубина N), простой вариант правда будет работать только для ассоциативной функции. Если нету O(1) функции длины (#a), то длину получать таким же образом.
Reply
function pointer_jump_part_sum(pt,val, xs) =
let
npt = pt->pt;
nval = {v + nv: v in val; nv in val->pt};
nxs = {x + nx*(if nv == 0 then 0 else 1): x in xs; nx in xs->pt; nv in val->pt; v in val};
in
if eql(npt,pt) then (val, nxs)
else pointer_jump_part_sum(npt,nval, nxs);
function wyllie_list_rank_part_sum(pt, xs) =
let
% set value to 1 everywhere except at the tails %
val = {if i==pt then 0 else 1: pt; i in [0:#pt]};
in pointer_jump_part_sum(pt,val, xs);
% This example contains the two lists
0,1 -> 2,2 -> 1,3 -> 5,4 -> 6,5
4,6 -> 7,7 -> 3,8 %
wyllie_list_rank_part_sum([2, 5, 1, 3, 7, 6, 6, 3], [1,2,3,4,5,6,7,8]);
%wyllie_list_rank_part_sum([0, 1, 2, 3, 5, 6, 7, 7], [1,1,1,1,1,1,2,1]);
%
Не считает последний элемент (для первого списка сумма 12, для второго - 13, соответственно, выпали 8 и 3). Это решается дополнительным параметром, но мне уже лень.
Надеюсь, это простительно. ;)
Reply
Leave a comment