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

Question

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

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

+⌿t∘.=c

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

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

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

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

Редактировать: На практике я делаю это, когда текст намного короче списка символов (символы не являются 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 - время выполнения операции пересечения.

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

Answer 1

NB.Использование наречий «ключ» (/.) С глаголом (#) насчитывает

   #/.~ 'abdaaa'
4 1 1

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

   ~. 'abdaaa'
abd

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

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

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

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

Примечание.Это вычитает 1 (<:) из каждого подсчета xs. </p>

   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=. [: <: ([: # [) {. [: #/.~ ,

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

   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

Answer 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:;<=>
?@ABCDEFGHIJKLMNOPQR
STUVWXYZ[\]^_`abcdef
ghijklmnopqrstuvwxyz

Answer 3

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

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

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

Answer 4

Первоначально я думал, что это относится к оператору Find :

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

Используются следующие символы:

       (×X)/T
IMPS

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

       X~0
4 1 2 4

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

Answer 5

Как отмечено в других ответах, ключевой оператор делает это напрямую. Однако классический способ решения этой проблемы с помощью 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

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

Answer 6

Моя реализация в 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

Answer 7

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

count =: (i.~~.) ({,&0) (]+/"1@:=)

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

   '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

Мы не фильтруем введенную дату до «самостоятельной классификации», поэтому:

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