Как подсчитать частоту элемента в APL или J без петель

Предположим, у меня есть два списка, один - текст t, один - список символов c. Я хочу подсчитать, сколько раз каждый символ появляется в тексте.

Это можно сделать легко с помощью следующего кода APL.

+⌿t∘.=c

Однако он медленный. Он берет внешний продукт, затем суммирует каждый столбец.

Это алгоритм O (nm), где n и m - размер t и c.

Конечно, я могу написать процедурные программы в APL, которые читают символ t по символу и решают эту проблему в O (n + m) (предполагают идеальное хэширование).

Есть ли способы сделать это быстрее в APL без циклов (или условных)? Я также принимаю решения в J.

Edit: Фактически, я делаю это, когда текст намного короче, чем список символов (символы не являются ascii). Я рассматриваю, где текст имеет длину 20 и список символов имеют длину в тысячах.

Существует простая оптимизация, для которой n меньше m.

w  ← (∪t)∩c
f ←  +⌿t∘.=w
r ← (⍴c)⍴0
r[c⍳w] ← f
r

w содержит только символы из t, поэтому размер таблицы зависит только от t, а не от c. Этот алгоритм выполняется в O (n ^ 2 + m log m). Где m log m - время выполнения операции пересечения.

Однако субквадратичный алгоритм по-прежнему предпочтителен, если кто-то дал огромный текстовый файл.

Ответы

Ответ 1

NB. Использование слов "ключ" (/.) Наречия w/tally (#)

   #/.~ 'abdaaa'
4 1 1

NB. подсчитанные элементы - это нуль строки.

   ~. 'abdaaa'
abd

NB. Итак, если мы подсчитаем цель вместе со строкой

   #/.~ 'abc','abdaaa'
5 2 1 1

NB. Мы получаем дополнительный для каждого из целевых элементов.

   countKey2=: 4 : '<:(#x){.#/.~ x,y'

NB. Это вычитает 1 (<:) из каждого отсчета xs.

   6!:2 '''1'' countKey2 10000000$''1234567890'''
0.0451088
   6!:2 '''1'' countKey2 1e7$''1234567890'''
0.0441849
   6!:2 '''1'' countKey2 1e8$''1234567890'''
0.466857

NB. Негласная версия

   countKey=. [: <: ([: # [) {. [: #/.~ ,

NB. кажется сначала немного быстрее

   6!:2 '''1'' countKey 1e8$''1234567890'''
0.432938

NB. Но повторение времени 10 раз показывает, что они одинаковы.

   (10) 6!:2 '''1'' countKey 1e8$''1234567890'''
0.43914
   (10) 6!:2 '''1'' countKey2 1e8$''1234567890'''
0.43964

Ответ 2

Я думаю, что этот пример, написанный на J, соответствует вашему запросу. Список символов длиннее, чем текст (но оба они остаются короткими для удобства во время разработки.) Я не изучал время, но моя интуиция заключается в том, что он будет быстрым. Сводка выполняется только со ссылкой на символы, которые действительно встречаются в тексте, а длинный набор символов просматривается только для корреляции символов, которые встречаются в тексте.

   c=: 80{.43}.a.
   t=: 'some {text} to examine'

   RawIndicies=: c i. ~.t
   Mask=: RawIndicies ~: #c
   Indicies=: Mask # RawIndicies
   Tallies=: Mask # #/.~ t
   Result=: Tallies Indicies} (#c)$0

   4 20 $ Result
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 4 0
0 0 1 0 0 0 2 1 2 0 0 0 1 3 0 0 0 2 0 0
   4 20 $ c
+,-./0123456789:;<=>
[email protected]
STUVWXYZ[\]^_`abcdef
ghijklmnopqrstuvwxyz

Ответ 3

Dyalog v14 ввел ключевой оператор (⌸):

      {⍺,⍴⍵}⌸'abcracadabra'
a 5
b 2
c 2
r 2
d 1

Функция операнда принимает букву как ⍺ и вхождения этой буквы (вектор индексов) как ⍵.

Ответ 4

"Грубая сила" в J:

count =: (i.~~.) ({,&0) (]+/"[email protected]:=)

Использование:

   'abc' count 'abdaaa'
4 1 0

Не знаете, как это реализовано внутренне, но вот тайминги для разных размеров ввода:

   6!:2 '''abcdefg'' count 100000$''abdaaaerbfqeiurbouebjkvwek''' NB: run time for #t = 100000 
0.00803909
   6!:2 '''abcdefg'' count 1000000$''abdaaaerbfqeiurbouebjkvwek'''
0.0845451
   6!:2 '''abcdefg'' count 10000000$''abdaaaerbfqeiurbouebjkvwek''' NB: and for #t = 10^7
0.862423

Мы не фильтруем дату ввода до "self-classify", поэтому:

   6!:2 '''1'' count 10000000$''1'''
0.244975
   6!:2 '''1'' count 10000000$''1234567890'''
0.673034
   6!:2 '''1234567890'' count 10000000$''1234567890'''
0.673864

Ответ 5

Моя реализация в APL (NARS2000):

(∪w),[0.5]∪⍦w←t∩c

Пример:

      c←'abcdefg'
      t←'abdaaaerbfqeiurbouebjkvwek'
      (∪w),[0.5]∪⍦w←t∩c
a b d e f
4 4 1 4 1

Примечание: показаны только те символы из c, которые существуют в t

Ответ 6

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

Классическим решением является "сортировка, сдвиг и сравнение":

      c←'missippi'
      t←'abcdefghijklmnopqrstuvwxyz'
      g←⍋c
      g
1 4 7 0 5 6 2 3
      s←c[g]
      s
iiimppss
      b←s≠¯1⌽s
      b
1 0 0 1 1 0 1 0
      n←b/⍳⍴b
      n
0 3 4 6
      k←(1↓n,⍴b)-n
      k
3 1 2 2
      u←b/s
      u
imps

И для окончательного ответа:

       z←(⍴t)⍴0
       z
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
       z[t⍳u]←k
       z
0 0 0 0 0 0 0 0 3 0 0 0 1 0 0 2 0 0 2 0 0 0 0 0 0 0

Этот код не работает, но не готов к выпуску. Нужно искать пустые случаи - булевский сдвиг, вероятно, не подходит для всех случаев....

Ответ 7

Моя первоначальная мысль заключалась в том, что это был случай для оператора Find:

T←'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
C←'MISSISSIPPI'
X←+/¨T⍷¨⊂C

Используемые символы:

       (×X)/T
IMPS

Их соответствующие частоты:

       X~0
4 1 2 4

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