topic Re: a queueing model in SAS Procedures

a queueing model

torestin — Mon, 11 Nov 2019 10:41:58 GMT

Hi there,

i am trying to create a queuing model say something is going to be sold to the first person through the door so long as they satisfy certain income criteria. So it would go something like this a-> person a; b-> person d; e->person b. For each product in list a, it go to the front of the remaining queue and pick the eligible purchaser. My code is pasted below.

The issue though is that it seems to move on from ineligible purchasers rather than keeping them in a queue. As you can see below, the 5th customer has too much income for the 5th product, but should have stayed in the queue and takes up the 6th offering. instead, it just skips ahead to the 6th customer.

Does anyone know what went wrong and how I can fix it?

thanks

Data market;
input UB LB;
datalines;
137454.23 99272.50
127407.23 92016.34
134738.07 97310.83
118503.53 85585.88
117691.52 84999.43
126468.91 91338.66
138833.30 100268.50
;;;;
run;

data customers;
input pay;
datalines;
117605
120194
114285
92316
125917
106480
94244
127482
94744
106371
122085
100327
107315
115530
116100
100279
94117
111069
98615
115879
124773
118694
111970
118629
129623
121400
100992
129743
93083
90643
;;;;
run;

Data matching;
set market;
do i = 1 to 7
set customers;

if LB<pay<UB And control= . then do;
control=1;
output;
leave;
end;

end;
run;

Results:

137454.2	99272.5	1	117605	1
127407.2	92016.34	1	120194	1
134738.1	97310.83	1	114285	1
118503.5	85585.88	1	92316	1
117691.5	84999.43	2	106480	1
126468.9	91338.66	1	94244	1
138833.3	100268.5	1	127482	1

Re: a queueing model

ChrisNZ — Fri, 15 Nov 2019 22:40:16 GMT

1. Why 7 in this line of code?

do i = 1 to 7

2. The problem you ignore, if I understand correctly, is that you need to remove customers as they are used.

If true, a hash table would serve you better than reading a static customer table.

Re: a queueing model

torestin — Sat, 16 Nov 2019 10:17:35 GMT

hey thanks for that.

1) actually i am a bit lost about why I put the loop there in the first place now! but it's probably there to enable the leave statement...

2) what I was trying to do was actually to remove both the qualifying range and the customer from the respective sets. So it reads product 1 from the market set, picks out customer 1 from the customer set removes it, then move on to product 2, picks out customer 3, product 3/customer 2, etc. which iterates down the existing queue. I thought the hash table would only give me the match, or non-match - eg if customer 8 cannot find any matching product - but won't do the double elimination?

Re: a queueing model

ChrisNZ — Tue, 19 Nov 2019 09:38:59 GMT

If you go through the products sequentially (SET statement) you don't need to remove them. just remove the customers from the hash table as you find a match when you iterate the hash table,

Re: a queueing model

torestin — Wed, 20 Nov 2019 08:32:58 GMT

right...so this is how i thought hash would work: I need to insert a key/item into both set so they have something to match, and then I see if the condition is satisfied.

However, it now says pay is uninitiated so doesn't seem to have read the pay values into the hash table. Where did I go wrong?

Data market;
input control UB LB;
datalines;
1 137454.23 99272.50
1 127407.23 92016.34
1 134738.07 97310.83
1 118503.53 85585.88
1 117691.52 84999.43
1 126468.91 91338.66
1 138833.30 100268.50
;;;;
run;

data customers;
input control pay;
datalines;
1 117605
1 120194
1 114285
1 92316
1 125917
1 106480
1 94244
1 127482
1 94744
1 106371
1 122085
1 100327
1 107315
1 115530
1 116100
1 100279
1 94117
1 111069
1 98615
1 115879
1 124773
1 118694
1 111970
1 118629
1 129623
1 121400
1 100992
1 129743
1 93083
1 90643
;;;;
run;

Data M;

If _n_=1 then do;

Declare Hash m(dataset:"customers");

m.definekey('control');

m.definedata('pay');

m.definedone();
end;

Set market;
if m.find()=0 then do;

If LB<pay<UB then do;

Output;

m.remove();

end;
End;

Run;

Re: a queueing model

PeterClemmensen — Wed, 20 Nov 2019 08:41:24 GMT

@torestin what does your desired result from this data look like?

Re: a queueing model

torestin — Wed, 20 Nov 2019 09:11:44 GMT

The desired result would look like this:

product Customer pay matching result

UB LB

137454.2 99272.5 117605 137454.2 99272.5 117605

127407.2 92016.34 120194 127407.2 92016.34 120194

134738.1 97310.83 114285 134738.1 97310.83 114285

118503.5 85585.88 92316 118503.5 85585.88 92316

117691.5 84999.43 125917 117691.5 84999.43 106480

126468.9 91338.66 106480 126468.9 91338.66 125917

138833.3 100268.5 94244 138833.3 100268.5 94244

so that the fifth product is matched with the 6th customer, but the 5th customer (pay) 125917 remains in queue and picks up the 6th product, instead of being skipped altogether

Re: a queueing model

PeterClemmensen — Wed, 20 Nov 2019 11:26:01 GMT

@torestin I like the idea of using a hash object to implement this. You can do something like this

data want;
    format UB LB pay;
    keep   UB LB pay;
    if _N_=1 then do;
        declare hash h(ordered:'Y');
        h.definekey('k');
        h.definedata('k', 'pay');
        h.definedone();
        declare hiter hi('h');
    end;

    do k=1 by 1 until (lr1);
        set customers end=lr1;
        h.add();
    end;

    do until (lr2);
        set market end=lr2;

        do until (LB <= pay <= UB);
            rc=hi.next();
        end;

        output;

        _k=k;
        rc=hi.last();
        rc=hi.next();
        rc=h.remove(key: _k);
    end;
run;

Result:

UB        LB       pay
137454.23 99272.5  117605
127407.23 92016.34 120194
134738.07 97310.83 114285
118503.53 85585.88 92316
117691.52 84999.43 106480
126468.91 91338.66 125917
138833.3  100268.5 127482

Re: a queueing model

PeterClemmensen — Thu, 21 Nov 2019 11:35:18 GMT

@torestin did this work for you?

Re: a queueing model

torestin — Thu, 21 Nov 2019 21:12:08 GMT

Hey thanks for that. Yup it works...the only snag is that it seems to get stuck with larger dataset, I was going to do some investigation before coming back.

Re: a queueing model

PeterClemmensen — Thu, 21 Nov 2019 21:13:46 GMT

When you say 'get stuck' what do you mean?

Re: a queueing model

torestin — Thu, 21 Nov 2019 21:17:57 GMT

it took overnight to do a match (400 in products; 2000 pop) and never actually finished it and i had to stop it. Log showed it read both and then nothing. So I am not sure if it actually started execute the hash table. (I am also using the university edition so maybe some restrictions on that?)

Re: a queueing model

PeterClemmensen — Thu, 21 Nov 2019 21:33:51 GMT

Investigating my code a bit deeper, I think a problem may arise if no customer satisfies the range being considered. This would send the code into an infinite loop. Consider the situation and the code below

Data market;
input UB LB;
datalines;
137454.23 99272.50
127407.23 92016.34
134738.07 97310.83
118503.53 85585.88
117691.52 84999.43
126468.91 91338.66
138833.30 100268.50
;;;;
run;

data customers;
input pay;
datalines;
117605
120194
114285
1
1
1
1
1
1
1
1
1
1
1
;;;;
run;

data want;
    format UB LB pay;
    keep   UB LB pay;
    if _N_=1 then do;
        declare hash h(ordered:'Y');
        h.definekey('k');
        h.definedata('k', 'pay');
        h.definedone();
        declare hiter hi('h');
    end;

    do k=1 by 1 until (lr1);
        set customers end=lr1;
        h.add();
    end;

    do until (lr2);
        set market end=lr2;

        do until (LB <= pay <= UB | rc ne 0);
            rc=hi.next();
        end;
        if rc=0 then do;
           output;
           _k=k;
           rc=hi.last();
           rc=hi.next();
           rc=h.remove(key: _k);
        end;
        else do;
           pay=.;
           output;
           rc=hi.last();
           rc=hi.next();       
        end;

    end;
run;

Re: a queueing model

ChrisNZ — Thu, 21 Nov 2019 21:50:33 GMT

@PeterClemmensen

Can't test now, so maybe a silly question.

Why not

        if rc then pay=.;
        else h.remove();
        output;
        rc=hi.first();

Re: a queueing model

PeterClemmensen — Thu, 21 Nov 2019 22:07:22 GMT

@ChrisNZ as I understand it, I can't use the Remove() Method, when the object is locked by an iterator?

Feel free to test my code and find a better way. There is definitely a better way. I'm learning about stacks and queues in SAS myself, so any thoughts are greatly appreciated. I mainly used @hashmans book on the topic.

Btw, now that I tagged him, he will probably come around and write a better solution in 3 lines 😉 At least, I'll learn something...

Re: a queueing model

ChrisNZ — Thu, 21 Nov 2019 22:21:13 GMT

You couldn't use a better source than this book!

You are right, you need to move the iterator:

If an associated hash iterator is pointing to the keyvalue, then the REMOVE method will not remove the key or data from the hash object. An error message is issued.

All good, it makes perfect sense now! 🙂

Re: a queueing model

hashman — Fri, 22 Nov 2019 02:37:33 GMT

@PeterClemmensen:

Methinks your solution is fine. This:

rc=hi.last(); rc=hi.next();

is also the right thing to do if you just want a simple means to make sure you don't get the iterator locking error.

The only slight inaccuracy in " the object is locked by an iterator" is that the iterator locks not the whole table but all the items within the same-key group where the iterator currently dwells. Of course, when you want to purge the whole thing with CLEAR, i.e. every key group,the iterator pointer must be moved completely out of the table before calling CLEAR - and the two calls above (or first/prev - doesn't matter) are the simplest and fastest way of achieving it. You can figure it all out mighty quickly by playing a little bit with this piece of code:

data _null_ ;                                                                                                                                                                                                                                                   
  dcl hash h (multidata:"y", ordered:"a") ;                                                                                                                                                                                                                     
  h.definekey ("k") ;                                                                                                                                                                                                                                           
  h.definedone () ;                                                                                                                                                                                                                                             
  dcl hiter ih ("h") ;                                                                                                                                                                                                                                          
  do k = 1, 2, 2, 3, 3, 3 ;                                                                                                                                                                                                                                     
    h.add() ;                                                                                                                                                                                                                                                   
  end ;                                                                                                                                                                                                                                                         
  do i = 1 to 3 ;                                                                                                                                                                                                                                               
    _n_ = ih.next() ;                                                                                                                                                                                                                                           
  end ;                                                                                                                                                                                                                                                         
  h.remove (key:1) ; * works ;                                                                                                                                                                                                                                    
* h.remove (key:2) ; * fails ;                                                                                                                                                                                                                                    
  h.remove (key:3) ; * works ;                                                                                                                                                                                                                                    
run ;

You'll invariably see that getting the iterator out of a same-key group frees it for removal. Note that ordering the table is a must, as otherwise you cannot control when the iterator gets out of the same-key group. And, as said above, getting it out of the table altogether (above, it would happen if the upper bound of the DO I loop were 7) frees them all. But if the latter is the goal, why enumerate the whole table (as astonishingly ill-advised in one of SAS Support tech notes, especially if the table is big) if you can just use the pair of last/next or first/prev.

Kind regards

Paul D.

Re: a queueing model

PeterClemmensen — Fri, 22 Nov 2019 14:13:39 GMT

@hashman Thank you for the explanation. Makes sense.

Do you happen to have a link to that SAS Support tech note?

Re: a queueing model

hashman — Fri, 22 Nov 2019 18:21:35 GMT

@PeterClemmensen:

http://support.sas.com/kb/42/525.html

Kind regards

Paul D.