Exercise 10 Index   <<   >>


 

What are some special circumstances worthwhile exploiting in the algorithm in the previous exercise?  


 z←x xiySRloop y;⎕io;i;max;min;n;t
⍝ small-range version of x⍳y; written for easy translation into C
 ⎕io←0
 n←≢x
 min←⌊/x,y
 max←⌈/x,y
 t←(1+max-min)⍴n                              ⍝ table of indices
 z←(≢y)⍴0                                     ⍝ eventual result
 :For i :In ⌽⍳n ⋄ t[x[i]-min]←i    ⋄ :EndFor  ⍝ populate table
 :For i :In ⍳≢y ⋄ z[i]←t[y[i]-min] ⋄ :EndFor  ⍝ read index for y











•   x “the same” as y
 
•   x and y are from a small domain so that the maximal max and min are known and are small (¯128 and 127 for 1-byte ints; ¯32768 and 32767 for 2-byte ints.)
 
•   ?? min is 0