10

假设我有两个列表，一个是文本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 是进行交叉操作的时间。

但是，以防万一有人给出一个巨大的文本文件，仍然首选二次算法。

4

7 回答 7

8

注意。使用“键” (/.) 副词 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
于 2011-10-12T19:10:21.727 回答
6
于 2014-08-17T08:56:36.903 回答
5

我认为这个用 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
于 2011-09-02T13:35:17.047 回答
1

如其他答案所述，关键操作员直接执行此操作。然而解决这个问题的经典 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

这段代码不在我的脑海中，还没有准备好投入生产。必须寻找空案例 - 布尔移位可能不适用于所有案例......

于 2014-08-18T11:41:28.810 回答
0

我在 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 中的那些字符

于 2013-04-30T15:48:34.813 回答
0

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
于 2011-09-09T15:49:47.460 回答
0

我最初的想法是这是Find运算符的情况：

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

使用的字符有：

       (×X)/T
IMPS

它们各自的频率是：

       X~0
4 1 2 4

我只跑过玩具箱，所以我不知道性能如何，但我的直觉告诉我，它应该比外部产品更便宜。有什么想法吗？

于 2015-04-24T11:53:00.120 回答