topic Re: Complexity of algorithm in Application Development and Automation Discussions

Complexity of algorithm

Former Member — Sun, 23 Oct 2011 17:04:58 GMT

Hi guys , i'm a newbie in ABAP..

Today when i read optimizer part in SAP , it give me some confuse.

Part1
Entries: 1000 (ITAB1), 300 (ITAB2)
Line width: 100
Both tables sorted by unique key K ascending

LOOP AT ITAB1 INTO WA1.

READ TABLE ITAB2 INTO WA2

WITH KEY K = WA1-K BINARY SEARCH.

IF SY-SUBRC = 0.

" ...

ENDIF.

ENDLOOP.

In documentation , it write the complexity of program Part1 : O ( n * log2n ) . I'm totally agree with that.

Part 2
Entries: 1000 (ITAB1), 300 (ITAB2)
Line width: 100
Both tables sorted by unique key K ascending

DATA: I TYPE I.

I = 1.

LOOP AT ITAB1 INTO WA1.

do.

READ TABLE ITAB2 INTO WA2 INDEX I.

IF SY-SUBRC <> 0. EXIT. ENDIF.

IF WA2-K < WA1-K.

ADD 1 TO I.

ELSEIF WA2-K = WA1-K.

" ...

ADD 1 TO I.

EXIT.

ELSE.

EXIT.

endif.

enddo.

if sy-subrc <> 0. exit. endif.

ENDLOOP.

It said " the complexity of program Part2 is : O ( n1 + n2) . I don't understand with this ( how it can separate loop statment and read statment like that ? )

Anybody can explain it for me ? Thks alot.

Re: Complexity of algorithm

Former Member — Sun, 23 Oct 2011 23:43:01 GMT

Hi,

Please find an example. I hope it helps ..

suppose ITAB1 = ( 1, 2, 3, 4, 5) and ITAB2 = (2, 4)

What would be the total number of loop count in this case:

Following would be the flow:

ITAB1 = 1. I = 1.

ITAB2 = 2.

1 < 2 . (WA1-K < WA2-K) Exit. Enddo. - Total Loop Count 1 + 1 = 2.

ITAB1 = 2. I = 1.

ITAB2 = 2.

2 = 2.

I = 1+ 1 = 2.

EXIT ENDDO. Total Loop Count = 1 + 1 = 2.

ITAB1 = 3. I = 2.

ITAB2 = 4.

3 < 4. (WA1-K < WA2-K) Exit. Enddo. Total Loop Count 1 + 1 = 2.

ITAB1 = 4. I = 2.

ITAB2 = 4.

I = 3.

4 = 4. EXIT. ENDDO. Total Loop Cpunt 1 + 1 = 2.

ITAB1 = 4. I = 3.

READ ITAB2 fails. Exit. Enddo. Exit Outer Loop. Total Loop Cont = 1 + 1 = 2.

So total Loop Count = 2 + 2 + 2 + 2 + 2 = 10 ( which is of the order 5 + 2 = 7).

Similarly if ITAB1 = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) and ITAB2 = (2, 4).

Total loop count in this case will also be 10 which is again of the order 10 + 2 = 12.

Similar will be the scenario in all cases.

Thanks!

Re: Complexity of algorithm

volker_borowski2 — Mon, 24 Oct 2011 07:56:43 GMT

Hi,


 
* Part1

Part one looks to me like the classic Nested Loop Join.

It does not require the outer table to be sorted, and the inner Table needs only

to be sorted to support the binary search of the key.


 
* Part 2
 
Both tables sorted by unique key K ascending

And this is the try for a merge join, but I think the code is not optimized.

Total maximum required readcount being n1+n2 is correct, if the key is unique (might be even better).

But this sample code is doing at least one inner read for each outer key.

So even when itab2 starts with K=10, the first itab2 record will

be re-read for all itab1 values of 1-9

I think the classical mergejoin with unique keys should look like the code below.

It might be worth to discuss putting the smaller table (itab2) to be read first,

depending on the probability that it gets the "not found" first, to save reads on itab1.

This approach has the benefit, that you might be even better than n1+n2, depending on real data,

as one of the tables might run out of big enough keys early.


I_itab1 = 1.
I_itab2 = 1.
need_to_read_itab1 = 1.
need_to_read_itab2 = 1.
do
  IF need_to_read_itab1 = 1.
    READ TABLE ITAB1 INTO WA1 INDEX I_itab1.
    IF SY-SUBRC 0. EXIT. ENDIF.
    need_to_read_itab1 = 0.
  ENDIF.
  IF need_to_read_itab2 = 1.
    READ TABLE ITAB2 INTO WA2 INDEX I_itab2.
    IF SY-SUBRC 0. EXIT. ENDIF.
    need_to_read_itab2 = 0.
  ENDIF.
  
  IF WA2-K < WA1-K.
    ADD 1 TO I_itab2.
    need_to_read_itab2 = 1.
  ELSEIF WA2-K > WA1-K.
    ADD 1 TO I_itab1.
    need_to_read_itab1 = 1.
  ELSE  "got a match, process and re-read both
    " ...
    ADD 1 TO I_itab1.
    ADD 1 TO I_itab2.
    need_to_read_itab2 = 1.
    need_to_read_itab2 = 1.
  endif.
enddo.

Volker

Re: Complexity of algorithm

Former Member — Tue, 25 Oct 2011 04:41:47 GMT

Thks Pranavjeet and Volker Borowski alot , i got it.