CA Easytrieve binary search algorithm example

Document ID:  TEC1293468
Last Modified Date:  07/17/2017
{{active ? 'Hide' : 'Show'}} Technical Document Details

Products

  • CA Easytrieve Report Generator

Releases

  • CA Easytrieve Report Generator:Release:6.4
  • CA Easytrieve Report Generator:Release:11.6

Components

  • CA EASYTRIEVE PLUS REPORT GEN:EZTRVE
  • CA Easytrieve Plus Report Generator:EZTPLS
Introduction:

Although every application developer is aware of the huge advantage of the binary search algorithm in opposite to the linear search algorithm, it can always happen that the possibility has been overseen, which offers probably a huge possibility of improvement and to make your program much more efficient.

But, as you know, in order to use the binary search algorithm, the records must be sorted.

Instructions:

In order to compare both algorithms, the search loops are being called 2000 times in the following sample.  

The first line is showing the result when using the linear search algorithm, and the 2nd line is showing the result when using the binary search algorithm - compare TOT-CPU please:

 

STEPNAME STEP   PGM=   CCODE  EST-COST   EXCPS     ELAPSED     TOT-CPU

EZTPGM      1 EB6L2KP  0000      $5.89     958 00:00:02.27 00:00:01.34

EZTPGM      1 EB6B2KP  0000      $4.79     958 00:00:00.47 00:00:00.03

...

 

Here are the source samples - first the linear search:

...

PARM LINK(EB6L2KP R)                                                   

*----------------------------------------------------------------------*

*   DEFINITIONS                                                        *

*----------------------------------------------------------------------*

FILE FILE1                                                             

  FILE-CODE                      1     8   N                           

  FILE-DESC                      *    40   A                           

*                                                                      

TABLE1-ELEMENTS                  W    48   A  OCCURS 30000             

  TABLE-CODE TABLE1-ELEMENTS           8   N                            

  TABLE-DESC TABLE1-ELEMENTS    +8    40   A                           

*                                                                      

DEFINE SRCH-VALUE    W  08 N VALUE 15001                               

DEFINE CNTR1         W  08 N VALUE 1                                   

DEFINE CNTR2         W  08 N VALUE 1                                   

*                                                                      

*----------------------------------------------------------------------*

*   WRITE (SORTED) RECORDS FROM FILE1 TO WORK TABLE                    *

*----------------------------------------------------------------------*

JOB INPUT FILE1                                                        

                                                                       

  TABLE-CODE(CNTR1) = FILE-CODE                                        

  TABLE-DESC(CNTR1) = FILE-DESC                                        

  CNTR1 = CNTR1 + 1                                                     

                                                                       

*----------------------------------------------------------------------*

*   LINEAR SEARCH IN WORK TABLE                                        *

*----------------------------------------------------------------------*

JOB INPUT NULL                                                         

                                                                       

  CNTR1 = 0                                                             

  DO UNTIL CNTR1 = 2000                                                

     DO WHILE CNTR2 LT 30001                                           

        IF TABLE-CODE(CNTR2) = SRCH-VALUE                              

           DISPLAY 'SEARCH VALUE HAS BEEN LOCATED: '                   

           DISPLAY TABLE-DESC(CNTR2)                                   

           CNTR2 = 30001                                               

        END-IF                                                          

        CNTR2 = CNTR2 + 1                                              

     END-DO                                                            

     CNTR2 = 1                                                         

     CNTR1 = CNTR1 + 1                                               

  END-DO                                                             

                                                                     

STOP                                                                 

...

 

And the binary search sample:

 

...

PARM LINK(EB6B2KP R)                                                   

*----------------------------------------------------------------------*

*   DEFINITIONS                                                        *

*----------------------------------------------------------------------*

FILE FILE1                                                             

  FILE-CODE                      1     8   N                           

  FILE-DESC                      *    40   A                           

*                                                                      

TABLE1-ELEMENTS                  W    48   A  OCCURS 30000             

  TABLE-CODE TABLE1-ELEMENTS           8   N                           

  TABLE-DESC TABLE1-ELEMENTS    +8    40   A                           

*                                                                      

DEFINE SRCH-VALUE    W  08 N VALUE 15001                               

DEFINE CNTR1         W  08 N VALUE 1                                   

DEFINE CNTR2         W  08 N VALUE 1                                   

DEFINE FOUND         W  01 N VALUE 0                                    

DEFINE TOP           W  08 N VALUE 30000                               

DEFINE BOT           W  08 N VALUE 1                                   

DEFINE MID           W  08 N VALUE 1                                   

*                                                                       

*----------------------------------------------------------------------*

*   WRITE (SORTED) RECORDS FROM FILE1 TO WORK TABLE                    *

*----------------------------------------------------------------------*

JOB INPUT FILE1                                                        

                                                                       

  TABLE-CODE(CNTR1) = FILE-CODE                                        

  TABLE-DESC(CNTR1) = FILE-DESC                                        

  CNTR1 = CNTR1 + 1                                                    

                                                                       

*----------------------------------------------------------------------*

*   BINARY SEARCH IN WORK TABLE                                        *

*----------------------------------------------------------------------*

JOB INPUT NULL                                                          

                                                                       

  CNTR1 = 0                                                            

  DO UNTIL CNTR1 = 2000                                                

     DO WHILE FOUND = 0 AND TOP >= BOT                                 

                                                                       

        MID = (TOP + BOT) / 2                                          

                                                                        

        IF SRCH-VALUE = TABLE-CODE(MID)                                

           DISPLAY 'SEARCH VALUE HAS BEEN LOCATED: '                 

           DISPLAY TABLE-DESC(MID)                                   

           FOUND = 1                                                 

        ELSE                                                         

          IF SRCH-VALUE < TABLE-CODE(MID)                            

             TOP = MID - 1                                            

          ELSE                                                       

             BOT = MID + 1                                           

          END-IF                                                     

        END-IF                                                        

                                                                     

     END-DO                                                          

     FOUND = 0                                                        

     CNTR2 = 1                                                       

     CNTR1 = CNTR1 + 1                                               

  END-DO                                                             

                                                                     

STOP                                                                 

...

 

FILE1:

 

****** ********************************* Top of Data **********************************

000001 00000001DESCRIPTION OF LINE 00000001                                            

000002 00000002DESCRIPTION OF LINE 00000002                                           

000003 00000003DESCRIPTION OF LINE 00000003                                           

- - -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -   29994 Line(s) not Displayed

029998 00029998DESCRIPTION OF LINE 00029998                                           

029999 00029999DESCRIPTION OF LINE 00029999                                           

030000 00030000DESCRIPTION OF LINE 00030000                                            

****** ******************************** Bottom of Data ********************************

 

Additional Information:

from https://docops.ca.com/ca-easytrieve/11-6/en/programming/code-programs/code-efficient-programs :

...

Table Processing

Avoid using very large tables, because they take more time to search and require more storage than small tables.

Note: CA Easytrieve® automatically converts a SEARCH of an INDEXED table file into a keyed read when the ARG field is also the file's key. This results in much faster access and reduced storage requirements.

...

Please help us improve!

Will this information enable you to resolve your issue?

Please tell us what we can do better.

{{feedbackText.length ? feedbackText.length : '0'}}/255

{{status}}

Not what you were looking for?

Search Again >

Product Information

Support by Product >

Communities

Join a Community >

Chat with CA

Just give us some brief information and we'll connect you to the right CA ExpertCA sales representative.

Our hours of availability are 8AM - 5PM CST.

All Fields Required

connecting

We're matching your request.

Unfortunately, we can't connect you to an agent. If you are not automatically redirected please click here.

  • {{message.agentProfile.name}} will be helping you today.

    View Profile


  • Transfered to {{message.agentProfile.name}}

    {{message.agentProfile.name}} joined the conversation

    {{message.agentProfile.name}} left the conversation

  • Your chat with {{$storage.chatSession.messages[$index - 1].agentProfile.name}} has ended.
    Thank you for your interest in CA.


    Rate Your Chat Experience.

    {{chat.statusMsg}}

agent is typing