Re: Ascend and data structure lookups.

I’m surprised by two aspects of your timings Alan.

First that there was not a greater differential between the binary and linear searches. Depending on the algorithm used there would potentially be a maximum of some 24 comparisons for the binary search and an average of 1,150 for the linear.

I’m even more surprised by the bsearch result though. I’d have expected that to be slower than the native RPG lookup. Maybe Barbara has some ides as to why this is.

And I’m 100% in agreement that the ascend/descend keywords should be available of DS arrays.

On Nov 28, 2015, at 2:25 AM, Alan Campin <alan0307d@xxxxxxxxx> wrote:

I have resolved the issue. Did a series of timing tests to solve the issue.

First determined that the following was using a binary lookup.

dcl-ds ExcTariffDs Based(ptrExcTariffDs);

ExcTariffArr Dim(32766) Ascend;

Exchange Zoned(6:0) Overlay(ExcTariffArr:*Next);

Tariff Char(3) Overlay(ExcTariffArr:*Next);

end-ds;

Doing 100,000 loops doing 5 lookups over 2,300 items loaded in a sorted
order. It took 119 microseconds per loop without the ASCEND keyword. Put
the ASCEND keyword on the declaration and it took 5 microseconds per loop
so clearly it is doing a binary search.

I also, determined that the following does not do a binary lookup.
Hopefully IBM will be providing a way to specify the ASCEND keyword on a
data structure with the DIM keyword. It took 120 microseconds per loop.

dcl-ds ExcTariffDs Qualified Dim(32766) Based(ptrExcTariffDs);

Exchange Zoned(6:0);

Tariff Char(3);

end-ds;



Idx - %Lookup(971153: ExcTariffDs.Exchange:1:LoadedCount);

// four more lookup.


I also did a binary search using the "bsearch" C Api and it took 3
microseconds per loop so the C api seems to be the fastest.


Partial code


dcl-pr FindBinaryApi Pointer
ExtProc('bsearch');
PR_PtrLookForValue Pointer
Value;
PR_PtrArrayElement Pointer
Value;
PR_NumberOfElements Uns(10)
Value;
PR_SizeOfEachElement Uns(10)
Value;
PR_PtrCompareProcedure Pointer(*Proc)
Value;

end-pr;



dcl-ds TD_ExcTariffDs Qualified
Template;
Exchange
Zoned(6:0);
Tariff
Char(3);

end-ds;



dcl-ds ExcTariffDs LikeDs(TD_ExcTariffDs)
Dim(32766)
Based(ptrExcTariffDs);



dcl-ds LookFor LikeDs(TD_ExcTariffDs);

LookFor.Exchange = InLookFor;
Return FindBinaryApi(%Addr(LookFor):
ptrExcTariffDs:
g_LoadedCount:
%Size(TD_ExcTariffDs):
%PAddr('BSEARCHCOMPARE'));


end-proc;


* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
* BSearchCompare
* Binary Search Compare Routine.
* In - Pointer to Look for Value Mapped to Look For
* Pointer to Array Element Mapped to Array Element
* In/Out - None
* Out - None
* Returns - Result of Compare
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
dcl-proc BSearchCompare;
dcl-pi *N Int(10);
InLookFor LikeDs(TD_ExcTariffDs) Const;
InArrayElement LikeDs(TD_ExcTariffDs) Const;
end-pi;

dcl-c LESS_THAN -1;
dcl-c EQUAL_TO 0;
dcl-c GREATER_THAN 1;


// Note: Values are passed as pointers by value so
// changing to by const is same thing.
Select;
When InLookFor.Exchange < InArrayElement.Exchange;
Return LESS_THAN;
When InLookFor.Exchange > InArrayElement.Exchange;
Return GREATER_THAN;
When InLookFor.Exchange = InArrayElement.Exchange;
Return EQUAL_TO;
EndSl;

end-proc;





On Fri, Nov 27, 2015 at 5:21 PM, Jon Paris <jon.paris@xxxxxxxxxxxxxx> wrote:

Yup - Ascend/Descend is a promise by _YOU_ that the data will be in
sequence. Not by IBM.

On Nov 26, 2015, at 6:08 PM, Booth Martin <booth@xxxxxxxxxxxx> wrote:

Thank you for the response. It cleared my confusion. My confusion laid

with the ASCEND/DESCEND keyword. It never dawned on me that IBM would
allow an ASCEND/DESCEND array to be populated in any order other than as
defined.

On 11/26/2015 8:32 AM, Jon Paris wrote:

No idea where you got that idea Booth. It has always worked the same

way as LOOKUP _except_ when Ascend/Descend is specified and then it
switches to binary search.

See this

http://www.ibmsystemsmag.com/ibmi/developer/rpg/iSeries-EXTRA--Look-Before-You--Lookup/
from 2002.

--
This is the RPG programming on the IBM i (AS/400 and iSeries) (RPG400-L)

mailing list

To post a message email: RPG400-L@xxxxxxxxxxxx
To subscribe, unsubscribe, or change list options,
visit: http://lists.midrange.com/mailman/listinfo/rpg400-l
or email: RPG400-L-request@xxxxxxxxxxxx
Before posting, please take a moment to review the archives
at http://archive.midrange.com/rpg400-l.

Jon Paris

www.partner400.com
www.SystemiDeveloper.com

--
This is the RPG programming on the IBM i (AS/400 and iSeries) (RPG400-L)
mailing list
To post a message email: RPG400-L@xxxxxxxxxxxx
To subscribe, unsubscribe, or change list options,
visit: http://lists.midrange.com/mailman/listinfo/rpg400-l
or email: RPG400-L-request@xxxxxxxxxxxx
Before posting, please take a moment to review the archives
at http://archive.midrange.com/rpg400-l.

--
This is the RPG programming on the IBM i (AS/400 and iSeries) (RPG400-L) mailing list
To post a message email: RPG400-L@xxxxxxxxxxxx
To subscribe, unsubscribe, or change list options,
visit: http://lists.midrange.com/mailman/listinfo/rpg400-l
or email: RPG400-L-request@xxxxxxxxxxxx
Before posting, please take a moment to review the archives
at http://archive.midrange.com/rpg400-l.

Jon Paris

www.partner400.com
www.SystemiDeveloper.com