如何在没有循环的情况下计算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.使用"key"(/.)副词w/tally(#)动词计数

   #/.~ 'abdaaa'
4 1 1

NB.计算的项目是字符串的结尾.

   ~. 'abdaaa'
abd

NB.所以,如果我们计算目标和字符串

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

NB.我们为每个目标项目额外获得一个.

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

NB.这会从xs的每个计数中减去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

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

操作数函数将一个字母作为，?并将该字母的出现（索引的向量）作为?。