topic Re: Keeping only highest values in hash table in SAS Programming

Keeping only highest values in hash table

Georg_UPB — Tue, 17 Dec 2013 16:32:33 GMT

Hi everyone!

When going through dataset "have" shown in the example below I only want to keep the three highest scores:

"want1": three entries with the highest scores would be nice

"want2": entries with the three highest scores would be even nicer

As soon as I try to accomplish this my code gets pretty complicated and its not really working...

As I'm new to hash tables, I have a feeling that there is an easy solution that I'm just missing... Any help is appreciated!!

Data have;

Input Name $ Score;

Datalines;

A.B. 6

C.D. 10

E.F. 5

G.H. 3

I.J. 10

K.L. 9

M.N 3

Run;

Data _Null_;

Set have End=done;

If _n_=1 Then Do;

Declare Hash ht(Ordered:'d');

ht.DefineKey('Score');

ht.DefineData('Name','Score');

ht.DefineDone();

End;

If ht.Num_Items<3 Then Do;

ht.Add();

End;

Else Do;

/* Need something like this:

If ht.Last/Score < Score Then Do;

ht.RemoveLast;

ht.Add;

End;

If done Then ht.Output(Dataset:'So_far');

Run;

Data want1;

Input Name $ Score;

Datalines;

C.D. 10

I.J. 10

K.L. 9

Run;

Data want2;

Input Name $ Score;

Datalines;

C.D. 10

I.J. 10

K.L. 9

A.B. 6

Run;

Re: Keeping only highest values in hash table

AhmedAl_Attar — Tue, 17 Dec 2013 17:19:15 GMT

Do you really need hash for this?

I ask, because you can easily do it using Proc Rank.

proc rank data=have out=want descending ties=dense;

var score;

ranks scoreRank;

run;

proc sort data=want;

where scoreRank <= 3;

by descending score ;

run;

proc print data=want; run;

Re: Keeping only highest values in hash table

Georg_UPB — Tue, 17 Dec 2013 17:23:38 GMT

Actually, dataset "have" is so large, that I'm going through it via "File" & "Input" without creating output.

So, unfortunately, "Proc Rank" is not an option...

Re: Keeping only highest values in hash table

AhmedAl_Attar — Tue, 17 Dec 2013 18:27:37 GMT

How about this?

Data have/view=have;

infile "My Documents/sample_have.txt";

Input Name $ Score;

Run;

proc rank data=have out=want(where=(scoreRank <= 3)) descending ties=dense;

var score;

ranks scoreRank;

run;

Re: Keeping only highest values in hash table

Georg_UPB — Tue, 17 Dec 2013 18:45:57 GMT

Thank you very much for this solution!

Since I became really fond of hash tables, I'll just wait a little longer to see if there's also a nice solution that takes advantage of them before I mark your answer and close the topic.

The real dataset "have" requires some more grooming that can be easily done using hash tables... There's only the problem of extracting data with certain features (highest values etc.) which I thought could be accomplished by having the hash table sortered in descendant order.

Re: Keeping only highest values in hash table

Astounding — Tue, 17 Dec 2013 19:04:06 GMT

The way you have described it, it seems like you need to find the 3 highest scores, and the names associated with those scores. I would think that arrays would be a much better bet. For example:

data want;

array scores {3} score1-score3;

array names {3} $8 name1-name3;

do until (done);

set have end=done;

if score > score1 then do;

score3=score2;

score2=score1;

score1=score;

name3=name2;

name2=name1;

name1=name;

end;

else if score > score2 then do;

score3=score2;

score2=score;

name3=name2;

name2=name;

end;

else if score > score3 then do;

score3=score;

name3=name;

end;

output;

stop;

keep name1-name3 score1-score3;

run;

Because of the DO loop, there is no need to retain any of the variables.

If you need this information for processing another data set, you could use _TEMPORARY_ arrays instead of permanent. _TEMPORARY_ array elements do not get erased.

You could in theory replace the OUTPUT and STOP statements with a SET statement that reads another data set and processes observations based on NAME1-NAME3 and SCORE1-SCORE3. In that case, however, you would have to make sure that either these variables are retained or that you switch to _TEMPORARY_ arrays.

I'm not sure if you were hoping to get practice with hash tables here instead. But I would think that arrays are at least a good approach to the problem you described.

Good luck.

Re: Keeping only highest values in hash table

Georg_UPB — Tue, 17 Dec 2013 19:26:50 GMT

Thank you very much!

Arrays are also a very nice solution. Only the fact that "have" has 96 variables might cause some trouble, but otherwise this should work nicely.

Hash tables are an ideal solution for the operations I need to perform on "have". It's all working perfectly fine and very fast...

...up to the point that I don't want to populate my hash table with ALL entries, but only want to keep the nth highest values regarding certain fields...

Re: Keeping only highest values in hash table

Astounding — Tue, 17 Dec 2013 20:03:29 GMT

OK, the plot always thickens. In that case, don't bother saving NAME1-NAME3. Instead, save OBSNO1-OBSNO3, the observation number from HAVE. It should be a simple matter afterwards to retrieve just those three observations using SET and POINT=. I'd need further details of how you intend to use those observations to consider whether it makes sense to load them into a hash table at that point.

Re: Keeping only highest values in hash table

Haikuo — Tue, 17 Dec 2013 21:05:53 GMT

I concur 's sentiment and comment. From the nature of a Hash table, as long as your RAM can hold it, the bigger the table, the better benefits you get from it. Only a few highest scores in the a Hash table seems to be an overkill of using it. But without knowing the whole picture, it is too soon to call. Technical speaking it is of course doable using Hash table:

Data have;

Input Name $ Score;

Datalines;

A.B. 6
C.D. 10
E.F. 5
G.H. 3
I.J. 10
K.L. 9
M.N 3

Run;

/*Want1*/

Data _Null_;

Set have End=done;

If _n_=1 Then Do;

Declare Hash ht(Ordered:'d', multidata:'y');

ht.DefineKey('_Score');

ht.DefineData('_Name','_Score');

ht.DefineDone();

declare hiter hi('ht');

End;

if _n_ <= 3 then do; _name=name;_score=score; rc=ht.add();end;

else do;

rc=hi.last();

if score > _score then do;

_ss=_score;

_score=score;

_name=name;

rc=ht.add();

rc=hi.first();

rc=ht.remove(key:_ss);

end;

If done Then ht.Output(Dataset:'ties_count');

Run;

/*Want2*/

Data _Null_;

Set have End=done;

If _n_=1 Then Do;

Declare Hash ht(Ordered:'d', multidata:'y');

ht.DefineKey('_Score');

ht.DefineData('_Name','_Score');

ht.DefineDone();

declare hiter hi('ht');

End;

if _n_ <= 3 then do; _name=name;_score=score; rc=ht.add();end;

else do;

if ht.find(key:score) = 0 then do; _name=name;_score=score; rc=ht.add();end;

else do;

rc=hi.last();

if score > _score then do;

_ss=_score;

_score=score;

_name=name;

rc=ht.add();

rc=hi.first();

rc=ht.remove(key:_ss);

end;

If done Then ht.Output(Dataset:'ties_not_count');

Run;

Haikuo

Re: Keeping only highest values in hash table

Vince28_Statcan — Tue, 17 Dec 2013 21:07:59 GMT

Solution using hash tables power to ease things up...

You've gone the right way using ordering, however, you misunderstood how your datarows are appended to the hash object when you don't use a dataset: statement. You would need to use a hash iterator object to retrieve first or last 3 hash object items after all of it has been loaded and sorted.

Here is a simple hash solution that still uses data step to output. You could use hash object output but you would need to create 2 or 3 hashes for simplicity or do some hardcore .remove() implementation.

Data have;
Input Name $ Score;
Datalines;
A.B. 6
C.D. 10
E.F. 5
G.H. 3
I.J. 10
K.L. 9
M.N 3
;
Run;

data want1 want2;
    if 0 then set have; /* avoid length statements */
    If _n_=1 Then Do;
        Declare Hash ht(dataset: 'have', Ordered:'d', multidata: 'Y'); /* load*/
        Declare Hiter hi('ht'); /* hash iterator object declared on hash object HT */
        ht.DefineKey('Score');
        ht.DefineData('Name','Score');
        ht.DefineDone();
    End;

     /* to achieve want1 and want2 logic */
     i=0; j=0;
     do while (j<3);
         hi.next(); /* loop through sorted data using iterator. If iterator has not been used before, then hi.next() is equivalent to hi.first() */
          if i<3 then output want1;
          output want2;
          i+1;
          if last_score NE score then j+1;
          last_score=score;
     end;
     drop i j last_score;
run;

I've put the interesting hash elements in bold the rest is similar logic that you would hard code if you used sorted data. Please note the use of multidata:'y' option as otherwise only CD or IJ could exist within the hash object as their KEY is identical.

Re: Keeping only highest values in hash table

Georg_UPB — Wed, 18 Dec 2013 11:52:58 GMT

Thank you very much!

That's exactly what I was looking for!

Re: Keeping only highest values in hash table

Georg_UPB — Wed, 18 Dec 2013 12:00:44 GMT

Thanks for pointing out this alternative!

Considering the size of the "real" have-dataset, I'm trying to populate the hash table with as few data as possible.

Re: Keeping only highest values in hash table

Vince28_Statcan — Wed, 18 Dec 2013 13:05:14 GMT

I see. Well obviously, my solution causes a single pass on the data instead of two cutting I/O by ~half (well only input but still a large chunk of your total I/O). However loading a full hash object isn't always manageable.

It is possible however to manage to output each want1 and want2 in a single read of the data using 3 hash objects each with at most 4 distinct key values at any given time so reasonably little total memory space saving a giant input operation. I will try to come provide the additionnal example during my lunch break as the logic is slightly less natural at least for my hash habits to spare a small break for it. It won't necessarily be a giant breakthrough but if I think it's a worthwhile self-learning I would assume it can benefit to others as well!

Vincent

Re: Keeping only highest values in hash table

Vince28_Statcan — Wed, 18 Dec 2013 18:39:30 GMT

As mentionned, here's an alternative that will produce both output within a single pass on the data effectively saving you a large I/O since the reason why you didn't load the entire table in a hash was for memory issue.

data _null_;
    if 0 then set have; /* avoid length statements */
    If _n_=1 Then Do;
        Declare Hash ht1(Ordered:'d', multidata: 'Y', hashexp: 2); /* load*/
        Declare Hiter hi1('ht1'); /* hash iterator object declared on hash object HT */
        ht1.DefineKey('Score');
        ht1.DefineData('Name','Score');
        ht1.DefineDone();

declare hash ht2(ordered:'d', multidata: 'Y', hashexp: 2);
declare hiter hi2('ht2');
        ht2.DefineKey('Score');
        ht2.DefineData('Name','Score');
        ht2.DefineDone();

declare hash kt2(ordered: 'd', hashexp: 2);
declare hiter ki2('kt2');
        kt2.DefineKey('Score');
        kt2.DefineData('Score');
        kt2.DefineDone();
    End;

set have end=done;
ht1.add();
kt2.replace();
ht2.add();

if ht1.num_items>3 then do;
hi1.last();
rc=hi1.next();
ht1.remove();
end;

if kt2.num_items>3 then do;
ki2.last();
rc=ki2.next();
kt2.remove();
ht2.remove();
end;

if done then do;
ht1.output(dataset: "want1");
ht2.output(dataset: "want2");
end;
run;

On a side note, I was very disappointed to realize that there is no documented method or trick to set the hash iterator pointer to NULL after using it to retrieve the last or first item for the purpose of removing data. Anyone knows a trick that is more straight forward, especially when it comes to reading the code, other than having to use next() after a last() to clear the pointer without changing PDV values since you ought to reuse the same keys? The approach above saves from having to declare and call missing every data step loop on a full subset of variables with the same name as the set itself and it solely uses the sortation within the hash and an iterator to remove data but because there exists no way to set an iterator pointer to NULL, I had to waste PDV space and a bunch of useless iteration for RC=iterator.next() as without the RC=, it creates an error (data step still processes). Plus, it does not feel natural to have to tell a pointer on the known last element of a sequence to point to the next element so as to clear it from locking the removal of data/key elements.

Anyway end of the rant about iterator having no method to change the pointer position without affecting PDV other than next on a last or prev on a first.

Re: Keeping only highest values in hash table

Georg_UPB — Thu, 19 Dec 2013 18:01:33 GMT

Thank you very much for taking the time! I learnt a lot from your examples!

Re: Keeping only highest values in hash table

Haikuo — Thu, 19 Dec 2013 19:59:56 GMT

I was quite puzzled by your comments regarding on "I/O" issues until I saw this post of yours. I was thinking OP wants either 'nice' or 'nicer', but not both, hence my solution. If wanting both, I would opt using my /*Want2*/ with a little tweak, such as using removedup() instead of remove() method, and then do a subset using "obs=3" to get /*want1*/, paying little to zero extra to 'I/O', but the benefit is obvious: 1. Avoiding strenuously Hash coding with multiple Hash objects. 2. Remove() method is not quite ready for dup-keys in this case, try following data you will know what I mean.

Data have;

Input Name $ Score;

Datalines;

A.B. 11

C.D. 9

E.F. 5

G.H. 3

M.N 3

I.J. 10

Run;

Haikuo

Re: Keeping only highest values in hash table

Vince28_Statcan — Fri, 20 Dec 2013 16:58:47 GMT

I did indeed simply assume that he might want to achieve both and not either or hence programming both within a single data step to save what is the longest processing element which is to input the data through the set statement.

I don't think the output method supports dataset option like OBS=3 for output so you'd need to replace data _null_ with data want1 and use the iterator on the 2nd hash object to just retrieve the top three values. In fact, this would also solve the bug you've pointed out with my want1 output. However, I still do think there's a lot fo learn playing with hashing around and the 2-hash solution for want2. It also solves the bug pointed out by your own dataset for your want2 output and detailed below.

The issue with not using double hash object for WANT2 is that there does not exist a num_key property to hash objects for multidata. The data set you've examplified above also fails for your want2 because the threshold to adding new keys is _N_=3 so if there are only 1 or 2 keys across the first 3 lines of the input dataset, the output will only have one or two keys as well (and however many records share these keys). Still, it means that you have to consider the odd cases of your data in your "initialization phase" of the object. For most scenarios andi n particualr the one examplified here it is fairly simple, you can just create a new counter variable and increment it if find() fails on the hash prior to addition and then repalce the _N_ by that new counter variable instead.

The main reason I went with other approach was that it is completely independant from initialization. It uses NUM_ITEMS on the "KT" (key table) hash as a mean to mimic a missing NUM_KEYS property on the object I really care for. If NUM_KEYS property existed, it could've been done in a single hash as well but still using the sorting power of the hash to avoid having to manually code a bunch of additionnal variables to keep track of what to add/remove. You simply systematically add to your hash object and remove the last key (and all data associated to the key) if the NUM_KEYS is above your set threshold. This is also one of the beauty of hash object if you ever have to manipulate timestamp data from a system (like a voice recognition system or electronic questionaire or transaction records etc). You can use hash of hashes to rebuild the sequence of events regardless of any existing sortation and the internal instances of the hashes act as BY-groups sorted by the timestamp so you can iterate through and go back and forth if need be for decision logic and output a single row all within a single data step instead of a couple sorts.

Anyway I'm digressing because I did have to work with odd sortation masive call system data not so long ago where if I had had the hash knowledge I have now would've made my life so much easier (and I still have a lot of twists to learn).

But for all I know, even though the hash object has significantly improved in 9.2 from all documentation I could find, it is still missing quite a few tools.

1. A way to clear the hash iterator pointer so as to not lock remove() from happening

2. A hash iterator tool that allows to remove the current element (not the entire key but just the data element - similar to removedup but less tedious to use - it would also be extremely useful for traversing through the hash object and removing rows after sortation or other constructs have happened)

3. A NUM_KEYS property

Some might exist and are undocumented but I haven't found any paper discussing any such issues.

Nonetheless, very interesting discussion so far

Re: Keeping only highest values in hash table

Georg_UPB — Mon, 23 Dec 2013 01:25:56 GMT

Turned out that we actually needed just the n highest scores ("want2"), but we needed them for every name (or ID). This is the solution I came up with. Unfortunately, it needs not one but two additional tables, but it's working and it's really fast... However, any suggestions are always welcome!

Thanks again for your help!

%Let n_highest=3;

Data have;

Input ID $ Score;

Datalines;

A.B. 10

A.B. 5

A.B. 8

A.B. 10

A.B. 7

K.L. 9

K.L. 2

K.L. 9

Run;

Data _null_;

If 0 Then Set have;

If _n_=1 Then Do;

Declare Hash extra_tab1(Ordered:'a');

extra_tab1.DefineKey('ID');

extra_tab1.DefineData('ID','lowest','no');

extra_tab1.DefineDone();

Declare Hash extra_tab2(Ordered:'a');

extra_tab2.DefineKey('ID','Score');

extra_tab2.DefineData('ID','Score');

extra_tab2.DefineDone();

Declare Hiter extra_tab2_hit('extra_tab2');

Declare Hash tab(Ordered:'a',Multidata:'y');

tab.DefineKey('ID','Score');

tab.DefineData('ID','Score');

tab.DefineDone();

End;

Set have End=Done;

If extra_tab1.Find() ne 0 Then Do;

no=1;

lowest=Score;

extra_tab1.Add();

extra_tab2.Add();

tab.Add();

End;

Else If no<&n_highest. Then Do;

If extra_tab2.Find() ne 0 Then Do;

no=no+1;

lowest=Min(lowest,Score);

extra_tab1.Replace();

extra_tab2.Add();

End;

tab.Add();

End;

Else If Score>=lowest Then Do;

tab.Add();

If extra_tab2.Find() ne 0 Then Do;

extra_tab2.Add();

extra_tab2_hit.SetCur(Key:ID,Key:lowest);

extra_tab2_hit.Next();

_lowest_new=Score;

extra_tab2.Remove(Key:ID,Key:lowest);

tab.Remove(Key:ID,Key:lowest);

lowest=_lowest_new;

extra_tab1.Replace();

End;

If Done Then Do;

extra_tab1.Output(Dataset:"extra_tab1");

extra_tab2.Output(Dataset:"extra_tab2");

tab.Output(Dataset:"want2");

End;

Run;

Re: Keeping only highest values in hash table

Vince28_Statcan — Mon, 23 Dec 2013 17:25:58 GMT

I believe it could be reduced in #hash, #of statements and logic by using hash of hashes but it adds an additionnal layer of complexity for code transferability (e.g. you leave your current position and someone has to pickup from it, if he's not already familliar with the hash object he will struggle far more figuring out what the code does with hash of hashes than in the current implementation).

I'll gladly take a stab at it and provide the code if you request it. But otherwise I'll assume it is not needed. I don't think it would be significantly faster than the current implementation either.

I was actually amazed when I first read Black Belt Hashigana by Paul Dorfman about hash of hashes.

Vince

*edit* In practice, there would actually be n+1 hash objects where n is the number of distinct IDs but programatically speaking, they would just be new instances of a single hash so there would only need to be 2 hash objects defined. One with the current approach of instanciating upon declaration (followed with (), empty or with options like dataset: or sorted: ). The other ones would be built through a loop. The conditionnal logic would also be simpler with hash of hashes. Only the gist of understanding how multiple instances of a hash object all with the same name are handled is what would make the code difficult to understand.

*edit* Furthermore, in the perspective of wanting to use hash objects with complex conditional searches and/or with reduced memory usage, hash of hashes allow you to keep a by-variable only once in memory instead of however many multidata rows exist. It is really only worthwhile if you have big multidata groups and/or may want to search according to different keys based on the first key search success.

Re: Keeping only highest values in hash table

Georg_UPB — Tue, 24 Dec 2013 02:49:17 GMT

I'm always on the look out and would highly appreciate to see another solution!