@PGStats,
Sure, eager to oblige:
data eq (keep = ID X Y) ;
retain r "integer" ;
call streaminit (7) ;
array yy [4] _temporary_ (. 0 1 2) ;
do ID = 1 to 5E6 ;
do _n_ = 1 to rand (r, dim (yy)) ;
Y = yy (rand (r, dim (yy))) ;
X = rand (r, 99) ;
output ;
end ;
end ;
run ;
data kxarr (keep = ID x y) ;
array _f [-1:2] ;
array _v [-1:2] (. 0 1 2) ;
do until (last.id) ;
set eq ;
by ID ;
output ;
if nmiss (y) then _f[-1] = 1 ;
else if y in (0:2) then _f[ y] = 1 ;
end ;
x = 0 ;
do j = lbound (_f) to hbound (_f) ;
if _f[j] then continue ;
y = _v[j] ;
output ;
end ;
run ;
data hash ;
if _n_ = 1 then do ;
dcl hash h () ;
h.definekey ("y") ;
h.definedone () ;
end ;
do until (last.id) ;
set eq ;
by ID ;
output ;
h.ref() ;
end ;
x = 0 ;
do y = . , 0 to 2 ;
if h.check() ne 0 then output ;
end ;
h.clear() ;
run ;
Results (in seconds):
1. Key-indexed array: 3.96
2. Hash object: 12.66
A pretty stark difference, isn't it? Sure, but it stands to reason: Key-indexing, within its range limitations, is the fastest search algorithm there is because:
- There's no hash function overhead.
- A value is simply assigned to the array cell whose index is equal to the key-value.
- There's no need to search before "inserting" the value - it merely overwrites what's there.
- There's no cost of run-time memory allocation, as it is allocated at compile time.
- There's practically no cost cleaning it up after each BY group.
As opposed to that, the hash table needs to:
- Compute the hash function.
- Search the table to see if the value is already in the table and make a decision based on this finding and the specs.
- Traverse an AVL tree before inserting the value. Though pretty fast, it's not nearly as fast as just sticking it into an array.
- Allocate memory at run time for each new key-value being added.
- Wipe the contents of the table out after each BY group. Again, it costs much more than setting the array values to missing.
Can the hash table be made perform better? Sure it can. Here the heaviest burden comes from the excessive clean-up since under this particular arrangement the BY-groups are very numerous and the CLEAR method gets called as many times as there are distinct IDs. However, the groups are small and the hash memory footprint isn't an issue, so to improve performance, we can add ID to the key portion and clean the table after each Nth BY group. The value of N needs to be chosen optimally: If we set it too high, we'll increase the time needed for memory allocation, as a fuller table requires more time for that, plus letting the table get too big between the successive Ns means more cleaning effort. It's sort of like striking a balance between cleaning a house way too often and way too rarely: If we clean every minute, we will do nothing but clean; and if we do it every few months ... you get the picture. Having tinkered a little before posting, I found the optimal value to be N~50 and also zeroed in on hashexp:9 (instead of the default 8). Thus, the code needs only minor changes (in red bold):
data hash ;
if _n_ = 1 then do ;
dcl hash h (hashexp:9) ;
h.definekey ("ID", "y") ;
h.definedone () ;
end ;
do until (last.id) ;
set eq ;
by ID ;
output ;
h.ref() ;
end ;
x = 0 ;
do y = . , 0 to 2 ;
if h.check() ne 0 then output ;
end ;
if not mod (_n_, 50) then h.clear() ;
run ; Simply reducing the clean-up frequency in this manner reduces the hash run time to 7 seconds flat. While still a far cry from the key-index's 3.96 seconds (for the reasons we can't control), it's a huge improvement against 12.66.
The advantage of the hash object lies in is its much wider applicability. If instead of tracking Y ranging from -1 to 2 we had to track, say, Y1-Y10 with a integer value range exceeding ~1E8 (let alone if they were character variable longer than $3), we wouldn't be able to key-index within reasonable memory constraints, while the hash table would still work - we would only have to augment it accordingly.
Best
Paul D.
