topic Re: binary search performance in Application Development and Automation Discussions

binary search performance

Former Member — Mon, 13 Aug 2007 10:03:21 GMT

TYPES: begin of t_vbap,

vbeln type vbap-vbeln,

end of t_vbap.

data: i_vbap type table of t_vbap,

w_vbap type t_vbap.

hi all,

i'm curious about using the binary search, i get better performance with linear search compare to binary search with the following testing statement.

anybody can advise what's going wrong on the query statement?

binary search

select vbeln into table i_vbap

from vbap.

sort i_vbap by vbeln.

read table i_vbap into w_vbap

with key vbeln = '0000000419'

binary search.

if sy-subrc = 0.

endif.

linear search

select vbeln into table i_vbap

from vbap.

read table i_vbap into w_vbap

with key vbeln = '0000000419'.

if sy-subrc = 0.

endif.

THanks,

Re: binary search performance

seshatalpasai_madala — Mon, 13 Aug 2007 10:06:12 GMT

Hi,

This can be a case like this

Suppose this is your list.

1 2 3 4 5 6 7 8 9

Binary search will take around 3 to 4 steps to find value '1'.

Where as Linear search will take only 1 step.

Binary search will Devide the result list into TWO in each step and eliminate one HALF based on the Value being searched.

So if you are searching 1 here it will first devided the group into

1 2 3 4 -- 6 7 8 9

SInce 5 is > than 1 it eliminates 6 7 8 9

And then same process till it gets 1.

Regards,

Sesh

Re: binary search performance

Former Member — Mon, 13 Aug 2007 10:19:34 GMT

Of course, if you measure the whole process!

The read itself is muich faster than the read without binary search.

However, the sort is much more expensive than the read.

The advantage of the binary search come in, if you use the read in a loop and

have to read nearly all lines of the internal table:

sort itab2

loop at itab1 into wa1

read itab2 with key k1 = wa1-k1 binary search

endloop

In this construction the read without binarty search would kill your performance when itab2 becomes large.

Say, do 50 to 100 reads to justify one sort!

Siegfried

Re: binary search performance

Former Member — Mon, 13 Aug 2007 10:55:50 GMT

COMPARED TO LINEAR AND BINARY

BINARY IS THE BEST METHOD

IF UR RECORDS ARE TOO LESS THEN LINEAR SEARCH WILL GET FASTER OUTPUT

WHEN THE NUBER OF RECORDS ARE MORE THAN LINEAR SEARCH WILL TAKE SOME TIME

SO ALL WAYS BETTER TO USE BINARY SEARCH

IF THE NUMBER OF RECORDS ARE VERY HIGH T HEN BINARY SEARCH WIL PERFORM VERY FAST THAN LINEAR SEARCH

REWARD IF USEFULL

Re: binary search performance

Former Member — Tue, 14 Aug 2007 05:59:59 GMT

hi,

when compared to linear search , binary search is better performance than linear search in case of large amount of data.

Binary search devides the data into 2 eq parts and start search for the given field value.

Ex..

if we have 100 rec in itab. you are looking for 29th rec.

then Binary search devides into two halfs and search for the value 29 in two halfs.

if it is found in first half (1-50) then it again devides this into another two halfs (1-25 & 26-50) and start processing in the same way..

now the desired rec will be in 2nd half(26-50)

then it omits first half and start search in 2nd half by deviding again into 2 halfs..

like that the process goes until the 29th rec.

if there is less amnt of data its better to go for linear search.

Re: binary search performance

KjetilKilhavn — Tue, 14 Aug 2007 06:59:51 GMT

The binary search (which requires a sorted table) will give you better performance <u>on average</u>. For any one particular (unknown) input you can't say with certainty whether binary or linear search gives the best performance, but on average binary has better performance.

The reason is that the binary search, as mentioned, divides the search range in two for every 'lookup' until it finds a matching record, whereas the linear search trots sequentially along until it finds a match.

The average search time for a linear search will be N/2 where N is the number of entries in the table. A binary search will repeatedly cut the search range in half. The search time is therefore at most Log2(N).

Example: In an internal table with 128 entries the average linear search has to check 64 entries, and in the worst case all 128 entries have to be checked. The binary search will never have to check more than 8 entries for a 128-entry table.

See also <a href="http://en.wikipedia.org/wiki/Binary_search">Wikipedia</a> where the binary search algorithm is well explained.

Wikipedia also mentions that for a small number of entries in the table, linear lookup can exhibit better performance. But then again, when you have a small number of entries there usually will not be a performance problem.

Re: binary search performance

Former Member — Tue, 14 Aug 2007 08:06:37 GMT

Hallo Kjetil,

you are of course right. However, the argument becomes much simpler, if you take the sort into your discussion. For a single read, the costs for the sort can not be justified.

For many reads, the sort can be justified, and one can calculate with average costs, which make binary search better.

The binary search works without sort, but the results will be INCORRECT.

Siegfried

Re: binary search performance

KjetilKilhavn — Tue, 14 Aug 2007 17:31:56 GMT

Ah... of course. I didn't think of that. Hmmm... since a binary sort costs up to (N - 1) * Log2(N) you can read quite a few times before you catch up with the total runtime of sorting and binary reading.

I prefer using sorted buffer tables for those tables where I will be READing entries anyway, so I don't need to sort before reading. It is just as easy, at least if you insert entries whenever they don't already exist. The READ statement gives you the index where the new entry must be inserted, so keeping the table sorted at all times is not difficult.

Re: binary search performance

Former Member — Tue, 21 Aug 2007 11:20:47 GMT

hi chandra ur explanetion obout binary search is very nice

keep it up.

happy coding

cheers,

nagaraju

hcl technologies