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

Предположим, у меня есть два списка, один текст 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 - время выполнения операции пересечения.

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

Источник

7 ответов

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

   #/.~ 'abdaaa'
4 1 1

NB. подсчитанные элементы являются частью строки.

   ~. 'abdaaa'
abd

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

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

NB. Мы получаем дополнительный по каждому предмету.

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

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

   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
Источник

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

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

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

Источник

Я думаю, что этот пример, написанный на 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
Источник

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

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

Источник

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

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

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

       (×X)/T
IMPS

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

       X~0
4 1 2 4

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

Источник

"Грубая сила" в 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
Источник

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

Источник
Другие вопросы по тегам