topic Re: sort table and binary search in Application Development and Automation Discussions

sort table and binary search

raffinkira — Fri, 27 Jun 2014 01:35:22 GMT

If I just need to READ TABLE once for searching in an internal table.

Do I need to sort it first and then do binary search.

Someone told me that sort a table also takes time so that it is equal to READ TABLE directly if you just need to search once.

Re: sort table and binary search

VenkatRamesh_V — Fri, 27 Jun 2014 01:52:02 GMT

Hi, Ming

It Depends on your Internal table contents, if content is more its better to use hashed Internal table

if content is less you can you sorted table.

if you need to use read table for checking ? you can you transporting no fields,

Binary search is fastest way to find the record exits in itab then without binary search.

Regards,

Venkat.

Re: sort table and binary search

former_member730258 — Fri, 27 Jun 2014 03:34:25 GMT

if you know the unique keys then declare internal table as hashed then use keys to search. otherwise, sort then read.. binary search is best practice.

or if you're populating the table from SELECT then you may try to consider SELECT SINGLE or SELECT.. UP TO n ROWS.

Re: sort table and binary search

bishwajit_das — Fri, 27 Jun 2014 04:46:11 GMT

Hi,

It not required to SORT and BINARY SEARCH for a single READ of an internal table.

But if you are using READ statement inside a LOOP , then its preferred.

Anyways for your satisfaction you can put TIMESTAMP for SORT & SEARCH with READ, and TIMESTAMP for only READ, then you may get a better clarification of your answer.

Regards,

Bishwajit

Re: sort table and binary search

Former Member — Fri, 27 Jun 2014 07:27:09 GMT

If you read a table just once it realy doesnt matter what kind of read you use...

Maybe the question is how often you read it per day and not how often its read in your programm.

the performance depends on

how many records you have
how you insert the rows
what type of table you use
if you got duplicates in your table
how you read your table

check this blog

regards

Stefan Seeburger

Re: sort table and binary search

matt — Sun, 29 Jun 2014 05:56:44 GMT

First of all, a SORT is a very fast algorithm. A read of a STANDARD table is always sequential. Therefore SORT, followed by BINARY SEARCH may be quicker than a simple READ, depending on where the record is in the table.

Second, define the table as HASHED or SORTED. Don't use READ/BINARY SEARCH at all.

Do not use a single READ. The reason is that while using a HASHED or SORTED table has an overhead, after that you get performance gains. If the table is only read once, then the overhead isn't going to affect the overall run time of the program. But programs change. While now it only does one read, in the future it may do many. So future proof your program now by defining the table properly, with the correct key.

Re: sort table and binary search

matt — Sun, 29 Jun 2014 05:58:38 GMT

That blog relates to database reads - not to internal table reads.

Re: sort table and binary search

matt — Sun, 29 Jun 2014 06:00:30 GMT

Close. If you know the unique keys then declare the internal tables as hashed then use keys to search. Otherwise use a SORTED TABLE is best practice.

The only time to use SORT/READ/BINARY SEARCH is if the sort order is descending.

Also, UP TO 1 ROWS and SELECT SINGLE produce identical SQL on the database. Therefore use the latter (SELECT SINGLE) as it is clearer and simpler.

Re: sort table and binary search

matt — Sun, 29 Jun 2014 06:02:07 GMT

No. The fastest way to read tables is to define them correctly, as HASHED or SORTED with the right key in the first place. Then use READ... TABLE KEY...

Re: sort table and binary search

SuhaSaha — Sun, 29 Jun 2014 08:54:30 GMT


The only time to use SORT/READ/BINARY SEARCH is if the sort order is descending.

Afaik the prerequisite for BINARY SEARCH is that the key-fields should be sorted in ascending order.

Re: sort table and binary search

matt — Sun, 29 Jun 2014 11:40:41 GMT

You are absolutely correct. I'd forgotten that. So really, there is really very little reason to use BINARY SEARCH.

Re: sort table and binary search

former_member187859 — Mon, 30 Jun 2014 07:14:02 GMT

Hi Matthew,

I agree with all of the architecture points you've made in this thread. Always better to set yourself up and future proof your code by designing with hashed or sorted tables in mind.

One small thing: in my thinking, a SORT plus a BINARY SEARCH can never be faster than a sequential READ of a table. The worst case for a READ (no found record) is O(n), whereas the best case for any SORT (data is already sorted) algorithm is O(n), and then you have a leftover best case of O(1) for BINARY SEARCH (you hit the data you want on the first binary operation).

I think if someone is absolutely stuck in not being able to use hashed or sorted tables, then for one READ operation it's quicker just to do the sequential read. But that should be a pretty rare case.

Paul

Re: sort table and binary search

matt — Mon, 30 Jun 2014 07:26:28 GMT

If I create a class in Java that behaves like an internal table, and I implement quicksort (or whatever) in a method just using Java and no other libraries, and a "read binary search" method, then you're right. However, sorting is so useful, that on many architectures it's implemented at a very low level - even chip level. It's also a readily parallelisable algorithm.

So, all things being equal, of course you are right. But in practice, it may turn out somewhat different.

However, the reason to use the correct data structures is that while today it's just one read, you never know when it's going to be a million reads. And if it's just one read, the additional overhead of a HASHED table is not going to affect overall performance.

I'd also say that if a developer is stuck and unable to work out how to use HASHED and SORTED tables, that maybe they should consider another career?

Re: sort table and binary search

jrg_wulf — Mon, 30 Jun 2014 08:16:24 GMT

Hi Mathew,

i do almost, but not quite, agree with your statements.

I's absolutely true when we're talking about programming from scratch.

There are of course, especially when you venture into the abyss of existing HR-reports and their descendants, loads of szenarios, where you have to deal with predefined tables (e.g. infotype-tables), which, although ancient and outdated, do have their benefits.

And sometimes you don't need to redesign a complete program, but just readjust a tiny bit.

In these cases, when you're not free to declare a table hashed or sorted, sort and binary search are valuable language constructs.

I can't imagine any scenario, where you would populate an internal table, that is big enough to even consider the use of sort/binary search and then only have one single read access. Thus i have to assume, that the table in question is populated and used somewhere else and therfore the table-type is not free to alter for the read acces here.

So the answer to the original question depends on the number of entries in said table.

You would need a lot of entries to gain a substantial benefit in run-time by sorting and reading with binary search. On the other hand, considering a potential scenario, where the table is "owned" by other program parts, you could risk unwanted side effects.

As long as i'm not in posession of all the facts and unless we talk about big numbers, i'd opt for the sequential access. Don't change, just read.

Best regards - Jörg