10

2 つのリストがあるとします。1 つはテキストt、もう 1 つは文字のリストですc。各文字がテキストに何回出現するかを数えたい。

これは、次の APL コードで簡単に実行できます。

+⌿t∘.=c

ただし遅いです。外積を取り、各列を合計します。

これは、n と m が と のサイズである O(nm) アルゴリズムtですc。

もちろん、t文字ごとに読み取り、この問題を O(n+m) で解決する手続き型プログラムを APL で作成できます (完全なハッシュを想定)。

ループ(または条件付き)なしで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 は交差操作を実行する時間です。

ただし、誰かが巨大なテキスト ファイルを渡した場合に備えて、サブ 2 次アルゴリズムが引き続き推奨されます。

4

7 に答える 7

8

注意。「キー」(/.) 副詞とタリー (#) 動詞カウントの使用

   #/.~ 'abdaaa'
4 1 1

注意。カウントされるアイテムは、文字列のこぶです。

   ~. 'abdaaa'
abd

注意。したがって、文字列と一緒にターゲットを数えると

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

注意。対象アイテムごとに 1 つ余分に取得します。

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

注意。これにより、x の各カウントから 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

私の最初の考えは、これはFind演算子のケースであるということでした:

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

使用される文字は次のとおりです。

       (×X)/T
IMPS

それぞれの周波数は次のとおりです。

       X~0
4 1 2 4

おもちゃのケースしか使ったことがないので性能はわかりませんが、直感的には社外品より安いはずです。何かご意見は？

于 2015-04-24T11:53:00.120 に答える
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 に答える