Агрегирующие счетчики Tally

Question

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

Обычно это происходит, когда я подсчитываю конфигурации, вхождения, выполняю некоторую дискретную статистику и т. Д.

Итак, я определил очень простую, но удобную функцию для агрегирования Tally:

aggTally[listUnTallied__List:{}, 
         listUnTallied1_List,
         listTallied_List] := 
 Join[Tally@Join[listUnTallied, listUnTallied1], listTallied] //. 
     {a___, {x_, p_}, b___, {x_, q_}, c___} -> {a, {x, p + q}, b, c};

такой, что

l = {x, y, z}; lt = Tally@l;
n = {x};
m = {x, y, t};

aggTally[n, {}]
  {{x, 1}}

aggTally[m, n, {}]
  {{x, 2}, {y, 1}, {t, 1}}

aggTally[m, n, lt]
  {{x, 3}, {y, 2}, {t, 1}, {z, 1}}

Эта функция имеет две проблемы:

1) Производительность

Timing[Fold[aggTally[Range@#2, #1] &, {}, Range[100]];]
  {23.656, Null}
(* functional equivalent to *)
Timing[s = {}; j = 1; While[j < 100, s = aggTally[Range@j, s]; j++]]
  {23.047, Null}

2) Это не подтверждает, что последний аргумент является вещественным списком с подсчетом или нулем (хотя для меня это менее важно)

Есть ли простое, элегантное, быстрое и эффективное решение? (Я понимаю, что это слишком много требований, но желать можно бесплатно)

Answer 1

Возможно, это подойдет вашим потребностям?

aggTallyAlt[listUnTallied__List : {}, listUnTallied1_List, listTallied : {{_, _Integer} ...}] :=
{#[[1, 1]], Total@#[[All, 2]]} & /@ 
       GatherBy[Join[Tally@Join[listUnTallied, listUnTallied1], listTallied], First]

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

EDIT:

Вот более быстрая версия:

aggTallyAlt1[listUnTallied__List : {}, listUnTallied1_List, listTallied : {{_, _Integer} ...}] :=
Transpose[{#[[All, 1, 1]], Total[#[[All, All, 2]], {2}]}] &@
   GatherBy[Join[Tally@Join[listUnTallied, listUnTallied1], listTallied], First]

Время для этого:

In[39]:= Timing[Fold[aggTallyAlt1[Range@#2, #1] &, {}, Range[100]];]
Timing[s = {}; j = 1; While[j < 100, s = aggTallyAlt1[Range@j, s]; j++]]

Out[39]= {0.015, Null}

Out[40]= {0.016, Null}

Answer 2

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

aggTally[listUnTallied__List : {}, listUnTallied1_List, 
   listTallied : {{_, _Integer} ...}] := 
  Sort[Join[Tally@Join[listUnTallied, listUnTallied1], 
     listTallied]] //. {a___, {x_, p_}, {x_, q_}, c___} -> {a, {x, p + q}, c};

Answer 3

Вот самая быстрая вещь, которую я придумала, (а) использование тегов, доступных с Sow и Reap:

aggTally5[untallied___List, tallied_List: {}] :=
  Last[Reap[
    Scan[((Sow[#2, #] &) @@@ Tally[#]) &, {untallied}];
    Sow[#2, #] & @@@ tallied;
    , _, {#, Total[#2]} &]]

Не собираюсь выигрывать конкурсы красоты, но этовсе о скорости, верно?=)

Answer 4

Если вы остаетесь чисто символическим, вы можете попробовать что-то вроде

(Plus @@ Times @@@ Join[#1, #2] /. Plus -> List /. Times -> List) &

для присоединения к спискам. Это глупо быстро, но возвращает что-то, что не соответствует списку, поэтому нужно немного поработать (после чего он может перестать быть таким быстрым;)).

РЕДАКТИРОВАТЬ: Итак, у меня есть рабочая версия:

aggT = Replace[(Plus @@ Times @@@ Join[#1, #2] 
                  /. Plus -> List 
                  /. Times[a_, b_] :> List[b, a]), 
                k_Symbol -> List[k, 1], {1}] &;

Используя пару случайных символических таблиц, я получаю

a := Tally@b;
b := Table[f[RandomInteger@99 + 1], {i, 100}];

Timing[Fold[aggT[#1, #2] &, a, Table[a, {i, 100}]];]
--> {0.104954, Null}

Эта версия только добавляет списки, ничего не проверяет, по-прежнему возвращает некоторые целые числа и сравнивает с функцией Леонида:

Timing[Fold[aggTallyAlt1[#2, #1] &, a, Table[b, {i, 100}]];]
--> {0.087039, Null}

это уже на пару секунд медленнее: - (.

Ну хорошо, хорошая попытка.