Exercise 12 Index   <<   >>


 

The small-range algorithm for x⍳y involves initializing a table. Show how to avoid initializing this table (when translated into C) while retaining the O(1) access time.





















Aho, Hopcroft, and Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974; Exercise 2.12.

Develop a technique to initialize an entry of a matrix to zero the first time it is accessed, thereby eliminating the O(‖V‖2) time to initialize an adjacency matrix.

[Hint: Maintain a pointer in each initialized entry to a back pointer on a stack. Each time an entry is accessed, verify that the contents are not random by making sure the pointer in that entry points to the active region on the stack and that the back pointer points to the entry.]

















 z←x xiySD y;⎕io;i;j;max;min;n;t
⍝ 2-byte integer version of x⍳y; written for easy translation into C
 ⎕io←0
 n←≢x
 min←¯32768
 max← 32767
 t←?65536⍴2e9                        ⍝ table of indices with garbage
 z←?(≢y) ⍴2e9                        ⍝ eventual result  with garbage
 :For i :In ⌽⍳n ⋄ t[x[i]-min]←i ⋄ :EndFor
 :For i :In ⍳≢y
   :If (0≤j)∧j<n ⊣ j←t[y[i]-min] ⋄ :AndIf x[j]=y[i]
     z[i]←j
   :Else
     z[i]←n
   :EndIf
 :EndFor



_____________________

   x←?1000⍴2e4
   y←?2000⍴2e4

   (x xiySD y) ≡ x ⍳ y
1