title: How to count the frequency of a element in APL or J without loops
body: <p>Assume I have two lists, one is the text <code>t</code>, one is a list of characters <code>c</code>. I want to count how many times each character appears in the text.</p>
  
  <p>This can be done easily with the following APL code.</p>
  
  <pre><code>+⌿t∘.=c
  </code></pre>
  
  <p>However it is slow. It take the outer product, then sum each column.</p>
  
  <p>It is a O(nm) algorithm where n and m are the size of <code>t</code> and <code>c</code>.</p>
  
  <p>Of course I can write a procedural program in APL that read <code>t</code> character by character and solve this problem in O(n+m) (assume perfect hashing).</p>
  
  <p>Are there ways to do this faster in APL without loops(or conditional)? I also accept solutions in J.</p>
  
  <p><strong>Edit:</strong>
  Practically speaking, I'm doing this where the text is much shorter than the list of characters(the characters are non-ascii). I'm considering where text have length of 20 and character list have length in the thousands.</p>
  
  <p>There is a simple optimization <em>given n is smaller than m</em>.</p>
  
  <pre><code>w  ← (∪t)∩c
  f ←  +⌿t∘.=w
  r ← (⍴c)⍴0
  r[c⍳w] ← f
  r
  </code></pre>
  
  <p>w contains only the characters in t, therefore the table size only depend on t and not c. This algorithm runs in O(n^2+m log m). Where m log m is the time for doing the intersection operation. </p>
  
  <p>However, a sub-quadratic algorithm is still preferred just in case someone gave a huge text file.</p>