APL Hashing Model

APL and J Hashing Models
Roger Hui
 

 z←x xiy y;⎕io;h;hf;i;j;m;n;q
⍝ model of x⍳y using hashing; written to be easily translated into C

 ⎕io←0
 hf←{123457×⍵}                            ⍝ hash function
 n←≢y
 m←≢x
 q←2*1+⌈2⍟m                               ⍝ size of hash table
 h←q⍴m                                    ⍝ hash table; m means "free"
 z←n⍴m                                    ⍝ initialize to "not found"

 :For i :In ⍳m                            ⍝ index for each x
     j←q|hf x[i]                          ⍝ index into hash table
     :While m>h[j] ⋄ :AndIf x[h[j]]≠x[i]  ⍝ i.e. stop on finding m or an equal entry
         j←q|1+j                          ⍝ the next hash table entry
     :End
     :If m=h[j] ⋄ h[j]←i ⋄ :End           ⍝ new hash entry
 :End

 :For i :In ⍳n                            ⍝ index for each y
     j←q|hf y[i]                          ⍝ where to start looking in hash table
     :While m>h[j] ⋄ :AndIf x[h[j]]≠y[i]  ⍝ i.e. stop on finding m or an equal entry
         j←q|1+j                          ⍝ the next hash table entry
     :End
     z[i]←h[j]                            ⍝ here, either m=h[j] or x[h[j]]=y[i]
 :End
xiy=: 4 : 0
NB. model of x i. y using hashing; written to be easily translated into C 


 hf=.123457&*                                  NB. hash function
 n=.#y  
 m=.#x
 q=.2^1+>.2^.m                                 NB. size of hash table
 h=.q$m                                        NB. hash table; m means "free"
 z=.n$m                                        NB. initialize to "not found"

 for_i. i.m do.                                NB. index for each x
     j=.q|hf i{x                               NB. index into hash table
     while. (m>j{h)*.((j{h){ ::0:x)~:i{x do.   NB. i.e. stop on finding m or an equal entry
         j=.q|1+j                              NB. the next hash table entry
     end.
     if. m=j{h do. h=. i j}h end.              NB. new hash entry
 end.

 for_i. i.n do.                                NB. index for each y
     j=.q|hf i{y                               NB. where to start looking in hash table
     while. (m>j{h)*.((j{h){ ::0:x)~:i{y do.   NB. i.e. stop on finding m or an equal entry
         j=.q|1+j                              NB. the next hash table entry
     end.
     z=. (j{h) i}z                             NB. here, either m=j{h or ((j{h){x)=i{y
 end. 

 z
)

      x←14 16 8 6 5 8 6 16 16 19 13 12 3 1 9 12 17
      y←10 13 6 7 18 21 9 3 21 15 17 16 3 13 3 3 1 3 10 6

      x ⍳ y
17 10 3 17 17 17 14 12 17 17 16 1 12 10 12 12 13 12 17 3
      x xiy y
17 10 3 17 17 17 14 12 17 17 16 1 12 10 12 12 13 12 17 3
      x (⍳ ≡ xiy) y
1

      x ⍳ x
0 1 2 3 4 2 3 1 1 9 10 11 12 13 14 11 16
      x xiy x
0 1 2 3 4 2 3 1 1 9 10 11 12 13 14 11 16
      x (⍳ ≡ xiy) x
1


   x=: 14 16 8 6 5 8 6 16 16 19 13 12 3 1 9 12 17
   y=: 10 13 6 7 18 21 9 3 21 15 17 16 3 13 3 3 1 3 10 6

   x i. y
17 10 3 17 17 17 14 12 17 17 16 1 12 10 12 12 13 12 17 3
   x xiy y
17 10 3 17 17 17 14 12 17 17 16 1 12 10 12 12 13 12 17 3
   x (i. -: xiy) y
1
   
   x i. x
0 1 2 3 4 2 3 1 1 9 10 11 12 13 14 11 16
   x xiy x
0 1 2 3 4 2 3 1 1 9 10 11 12 13 14 11 16
   x (i. -: xiy) x
1

 z←x xiySRloop y;⎕io;i;max;min;n;t
⍝ small-range version of x⍳y; written to be easily translated into C
 ⎕io←0
 n←≢x
 min←⌊/x,y
 max←⌈/x,y
 t←(1+max-min)⍴n                              ⍝ initialize table of indices
 z←(≢y)⍴0                                     ⍝ eventual result
 :For i :In ⌽⍳n ⋄ t[x[i]-min]←i    ⋄ :EndFor  ⍝ populate table of indices
 :For i :In ⍳≢y ⋄ z[i]←t[y[i]-min] ⋄ :EndFor  ⍝ read off index for each item of y
xiySRloop=: 4 : 0
NB. small-range version of x⍳y; written to be easily translated into C

 n=. #x
 min=. <./x,y
 max=. >./x,y
 t=. (1+max-min)$n                            NB. initialize table of indices
 z=. (#y)$0                                   NB. eventual result
 for_i. i.-n do. t=. i ((i{x)-min)}t     end. NB. populate table of indices
 for_i. i.#y do. z=. (((i{y)-min){t) i}z end. NB. read off index for each item of y
)



{} dfn (direct function)
right argument in a dfn
assignment (=. and =:)
x[y] x indexed by y
x[y]←z indexed assignment
+ plus and conjugate
× times and signum (*)
* power and exponential (^)
log (^.)
| residue and magnitude
maximum and ceiling (>.)
= equal
not equal (~:)
> greater than
match (-:)
not match and tally (#)
index-of and integers (i.)
reshape and shape ($)
reverse and rotate (|.)
comment (NB.)
statement separator
⎕io index origin
:For etc.   control word


created:  2014-07-31 08:35
updated:2014-09-04 22:55