j - 如何计算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

注意使用“键”(/。)副词w/tally(＃)动词计数

   #/.~ 'abdaaa'
4 1 1

注意计数的项目是字符串的小数点。

   ~. 'abdaaa'
abd

注意因此，如果我们连同字符串一起计算目标

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

注意我们为每个目标项目额外获得一个。

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

注意这将从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

注意默契版本

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

注意乍一看似乎快一点

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

注意但是重复计时10次表明它们是相同的。

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