|
|
|
|
|
Written by Rich
|
|
Thursday, 24 May 2007 |
ABAP contains the concept of internal tables. These can be thought of as an array or a multi-dimensional structure. Internal tables can be defined as various types of tables:- Standard
- Sorted
- Hashed
- Index
- Any
These all have their various uses from just storing data extracted from a database to being used as lookup tables. In general, tables are defined like so:
Code: Types: Upload_Table Type Standard table of Upload_row
initial size 0,
So_Line_Item_Table Type Hashed table of So_Line_Item_row
initial size 0
with unique key Vbeln Posnr,
Error_Table Type Sorted table of Results_row
initial size 0
with header line
with non-unique key Error_Code. Note that you can include a header line (ie an in built work area) into the table definition, but my own preference is to use discrete work areas which allow easier use when reading and handling multiple rows from the same table, or updating a table of the same structure from a source table.
Standard Tables
Standard tables are effectively just a list of rows either extracted from a database or compiled during a program run. The order of the rows within a standard table are basically in entry order. Ie the first row inserted into the table occupies the first row, the second the second and so forth. This ordering can be changed using the SORT command to sort the table into any arbitrary order based upon the values of any field in the table structure. A READ TABLE command on a standard table results in a sequential search of the table from start to end until the required record is found. If the table has been sorted using the SORT command then faster binary searches can be used to read the table if required.
Sorted Tables
Sorted tables specify either a unique or a non-unique key. This key is used to impose an ordered sequence on the records that are inserted into the table and can consist of multiple fields from the table structure. Obviously if the key is unique then there can "be only one". In the case of a non-unique key when the table is read using the READ TABLE command, the first occurance of the key is returned. Sorted tables enable the use of a binary search routine enabling faster access to the various rows of the table.
How Does A Binary Search Work
Binary Searches (or more descriptively Binary Chops) work by repeatedly dividing an ordered (sorted) list in two until either the required record is found or the top and bottom of the list meet and the required record is not found.
This can be shown graphically by the following diagram. In this case, the order list consists of the numbers 1 to 36. The number we are looking for is 34. The red blocks show the current range of numbers that are being considered. The grey blocks show the numbers that have already been discarded. The Yellow block shows the mid-point of the search area and finally the green block what we are looking for.
Bear in mind that although we are using numbers here, strings can also be used in the same way. What actually happens is this:
The program calculates the length of the list and from that can calculate the mid point of the list. The value of the mid point record is then compared to the value that is being looked for. If the value is less than the value being looked for then the entire lower half of the list can be discarded (as it’s an ordered list….). Likewise if the value is more then the top half of the list can be discarded. This ‘discarding’ can be achieved by moving the calculated mid-point to either the top or bottom pointers into the list.
The mid-point is then recalculated again and the whole process is run through again. Eventually either the record being looked for will be found or the top and bottom pointers will meet in which case the value being searched for does not exist.
Whilst SAP has kindly provided the tools to perform a binary search, here it is in ABAP along with a comparison of the other binary searches coded by SAP:
Code: ************************************************************************
*
* Program: Z_Binary_Chop
*
* Purpose: A program to demonstrate how a binary chop works
* showing a comparison between a sequential search,
* a programmed binary chop and SAP's internal
* binary chop
*
* Creation Date: 15/04/2004
*
* Requested By:
*
* Reference Doc:
*
* Author: R Harper
*
* Modification History:
*
* Date Reason Transport Who
*
************************************************************************
Report Z_Binary_Chop
Message-id 38
Line-Size 80
Line-Count 0
No Standard Page Heading.
*
Types: Max_Rec type i,
Char_Key(10) type c,
*
Begin of Table_Row,
Key_Value type Char_Key,
End of Table_Row,
*
Value_Table type Standard table of Table_Row
initial size 0,
Sorted_Table type Sorted table of Table_Row
initial size 0
with unique key Key_Value.
*
Parameters: p_NumRec type Max_Rec obligatory,
p_Key type Char_Key obligatory.
*
Start-Of-Selection.
*
Data: t_Standard type Value_Table,
t_Sorted type Sorted_Table.
*
Perform Fill_Tables using p_NumRec Changing t_Standard t_Sorted.
Perform Binary_Chop using p_Key t_Standard.
Skip 1.
Perform Seq_Search using p_Key t_Standard.
Skip 1.
Perform Bin_Search using p_Key t_Standard.
Skip 1.
Perform Sort_Search using p_Key t_Sorted.
*Eject
***********************************************************************
*
* Procedure :Fill_Tables
*
* Purpose :Fills the standard and sorted tables with
* a string starting at 'A' being incremented
* by 'one' each time to the total number of
* records specified
*
* Entry :Total number of records to create
* Entry :Standard type table
* :Sorted type table
*
* Exit :
*
* Called By :Perform Fill_Tables using Number
* changing Standard_Table
* Sorted_table
*
* Calls :
*
* Modification History:
*
* Date Reason Version Who
*
Form Fill_Tables using pu_Max_Recs type Max_Rec
changing t_Stdrd_Table type Value_Table
t_Sortd_Table type Sorted_Table.
*
Data: Begin of w_Char,
Asc type x,
End of w_Char,
w_Key type Table_Row,
w_Ins_Key type Table_Row,
w_Klen type i,
w_Kpos type i.
*
Move 'A' to w_Key.
Do pu_Max_Recs times.
Move w_Key to w_Ins_Key.
Shift w_Ins_Key right deleting trailing ' '.
Append w_Ins_Key to t_Stdrd_Table.
Insert w_Ins_Key into table t_Sortd_Table.
*
* Increment the key....
*
Compute w_Klen = Strlen( w_Key ).
Compute w_Kpos = w_Klen - 1.
Do w_Klen times.
Move w_Key+w_Kpos(1) to w_Char.
Add 1 to w_Char-Asc.
If w_Char <= 'Z'.
Move w_Char to w_Key+w_Kpos(1).
Exit.
Else.
Move 'A' to w_Key+w_Kpos(1).
If w_Kpos = 0.
Concatenate w_Key 'A' into w_Key.
Exit.
EndIf.
EndIf.
Subtract 1 from w_Kpos.
EndDo.
EndDo.
EndForm.
*Eject
***********************************************************************
*
* Procedure :Binary_Chop
*
* Purpose :Performs a programmed binary chop on a
* sorted standard table, displaying the
* number of iterations, time and whether the
* key was found or not
*
* Entry :Key value to search for
* Entry :Table of values to search
*
* Exit :
*
* Called By :Perform Binary_Chop using Search_Key Values
*
* Calls :
*
* Modification History:
*
* Date Reason Version Who
*
Form Binary_Chop using pu_Key type Char_Key
t_Stdrd_Table type Value_Table.
*
Data: w_Bottom type syTabix, " Base record
w_MidPoint type syTabix, " Mid point record
w_Top type syTabix, " Top record
w_Its type i, " # of iterations
w_tvalue type Table_Row,
w_padded type Char_Key,
w_Runtime_start type i,
w_RunTime type i,
w_nr_mid type i.
*
Move pu_Key to w_Padded.
Shift w_Padded right deleting trailing ' '.
Translate w_Padded to upper case.
*
* Calculate the starting point for the search
*
Move 1 to w_Bottom.
Describe table t_Stdrd_Table lines w_Top.
Compute w_MidPoint = w_Bottom + ( ( w_Top - w_Bottom ) / 2 ).
*
Clear w_Its.
Get Run Time Field w_RunTime_start.
Read table t_Stdrd_Table into w_Tvalue index w_MidPoint.
While ( w_Tvalue <> w_Padded ) and ( w_Top <> w_Bottom ).
Write :/ w_Bottom, w_Midpoint, w_Top, w_TValue, w_Padded.
*
* Calculate the next midpoint
*
If w_Tvalue > w_Padded.
Move w_MidPoint to w_Top.
Else.
Move w_MidPoint to w_Bottom.
EndIf.
Compute w_MidPoint = w_Bottom + ( ( w_Top - w_Bottom ) / 2 ).
Read table t_Stdrd_Table into w_Tvalue index w_MidPoint.
*
Add 1 to w_Its.
*
* Sometimes the search will flip between the last two
* locations. Check that we haven't been here before.
*
If W_Midpoint = W_Bottom Or
W_Midpoint = W_Top.
Add 1 To w_Nr_Mid.
If w_Nr_Mid > 1.
Exit.
Endif.
Endif.
EndWhile.
*
Get Run Time Field w_RunTime.
Compute w_RunTime = w_RunTime - w_Runtime_Start.
Write :/ 'Binary Chop searching for ', pu_Key.
If w_Tvalue = w_Padded.
Write:/ ' Found'.
Else.
Write:/ 'Not Found'.
EndIf.
Write: 'After ', w_Its, 'Iterations and ', w_RunTime, 'Microsecs'.
EndForm.
*Eject
***********************************************************************
*
* Procedure :Seq_Search
*
* Purpose :Performs a sequential search on a
* sorted standard table, displaying the
* time and whether the
* key was found or not
*
* Entry :Key value to search for
* Entry :Table of values to search
*
* Exit :
*
* Called By :Perform Seq_Search using Search_Key Values
*
* Calls :
*
* Modification History:
*
* Date Reason Version Who
*
Form Seq_Search using pu_Key type Char_Key
t_Stdrd_Table type Value_Table.
*
Data: w_tvalue type Table_Row,
w_padded type Char_Key,
w_RunTime_Start type i,
w_RunTime type i.
*
Move pu_Key to w_Padded.
Shift w_Padded right deleting trailing ' '.
Translate w_Padded to upper case.
Get Run Time Field w_RunTime_Start.
Read table t_Stdrd_Table
into w_Tvalue
with key Key_Value = w_Padded.
Get Run Time Field w_RunTime.
Compute w_RunTime = w_RunTime - w_RunTime_Start.
Write :/ 'Sequential search for ', pu_Key.
If w_Tvalue = w_Padded.
Write:/ ' Found'.
Else.
Write:/ 'Not Found'.
EndIf.
Write: 'After ', w_RunTime, 'Microsecs'.
EndForm.
*Eject
***********************************************************************
*
* Procedure :Bin_Search
*
* Purpose :Performs a binary search on a
* sorted standard table, displaying time and
* whether the key was found or not
*
* Entry :Key value to search for
* Entry :Table of values to search
*
* Exit :
*
* Called By :Perform Seq_Search using Search_Key Values
*
* Calls :
*
* Modification History:
*
* Date Reason Version Who
*
Form Bin_Search using pu_Key type Char_Key
t_Stdrd_Table type Value_Table.
*
Data: w_tvalue type Table_Row,
w_padded type Char_Key,
w_RunTime_Start type i,
w_RunTime type i.
*
Move pu_Key to w_Padded.
Shift w_Padded right deleting trailing ' '.
Translate w_Padded to upper case.
Get Run Time Field w_RunTime_Start.
Read table t_Stdrd_Table
into w_Tvalue
with key Key_Value = w_Padded
Binary Search.
Get Run Time Field w_RunTime.
Compute w_RunTime = w_RunTime - w_RunTime_Start.
Write :/ 'SAP Binary search for ', pu_Key.
If w_Tvalue = w_Padded.
Write:/ ' Found'.
Else.
Write:/ 'Not Found'.
EndIf.
Write: 'After ', w_RunTime, 'Microsecs'.
EndForm.
*Eject
***********************************************************************
*
* Procedure :Bin_Search
*
* Purpose :Performs a binary search on a
* Sorted table, displaying time and whether
* key was found or not
*
* Entry :Key value to search for
* Entry :Table of values to search
*
* Exit :
*
* Called By :Perform Sort_Search using Search_Key Stable
*
* Calls :
*
* Modification History:
*
* Date Reason Version Who
*
Form Sort_Search using pu_Key type Char_Key
t_Sortd_Table type Sorted_Table.
*
Data: w_tvalue type Table_Row,
w_padded type Char_Key,
w_Runtime_Start type i,
w_RunTime type i.
*
Move pu_Key to w_Padded.
Shift w_Padded right deleting trailing ' '.
Translate w_Padded to upper case.
Get Run Time Field w_RunTime_Start.
Read table t_Sortd_Table
into w_Tvalue
with table key Key_Value = w_Padded.
Get Run Time Field w_RunTime.
Compute w_RunTime = w_RunTime - w_RunTime_Start.
Write :/ 'SAP Sorted search for ', pu_Key.
If w_Tvalue = w_Padded.
Write:/ ' Found'.
Else.
Write:/ 'Not Found'.
EndIf.
Write: 'After ', w_RunTime, 'Microsecs'.
EndForm. To run this program, after you've done the usual copy and paste excercise, enter the number of records that you want in your internal table (300000 will do....), and then enter the key that you wish to find. Keys are generated starting at 'A' then 'B' ..... 'AA', 'AB' etc for a maximum of 10 characters (Rosie.... :- .
Now, when I first ran this and compared the various times, I thought I had made a mistake somewhere as the binary chop that I had coded was just slightly faster (even with the WRITE statement in the middle of it) than SAP's own Binary search. So I spent a few fruitless hours checking it out. No mistake.... or so I thought. Thanks to Rouge for pointing out that each subsequent call to the GET RUNTIME statement takes the run time from the first call, rather than as I interpreted it as every other call reset the counter to zero, and corrrecting a bug whereby the code looped in certain circumstances with a non existant key..
Below is the output from the sorts:
Code: 1 150,001 300,000 HMWG RH
1 75,001 150,001 DFXQ RH
1 37,501 75,001 BCLI RH
1 18,751 37,501 AASE RH
1 9,376 18,751 MVP RH
1 4,689 9,376 FXI RH
1 2,345 4,689 CLE RH
1 1,173 2,345 ASC RH
1 587 1,173 VO RH
1 294 587 KH RH
294 441 587 PY RH
441 514 587 ST RH
441 478 514 RJ RH
441 460 478 QR RH
460 469 478 RA RH
469 474 478 RF RH
Binary Chop searching for RH
Found After 16 Iterations and 660 Microsecs
Sequential search for RH
Found After 165 Microsecs
SAP Binary search for RH
Found After 8 Microsecs
SAP Sorted Binary search for RH
Found After 1,059 Microsecs Hashed Tables
Hashed tables are similar to sorted tables in that an order is imposed on the data being inserted into the table, however this order is the result not of the lexical or alphabetical ordering of the keys, but is essentially a number generated by a algorithm that calculates the row number where the record is to be inserted. Obviously great care has to be used when constructing the algorithm as you could get cases where different keys produce the same record number. Where collisions do occur there are various ways round them from recalculating the hash value using a different algorithm to using the initial value as a starting point in the table and then using a sequential search from that point on.
Due to the fact that generally the number of steps that the hashing algorithm has to take to generate the hash number is the same for any key, the access time for a hashed table is the same for any record in the table, generally only changing if a collision is involved.
The program below handles a demonstration hash table, calculating the relevant hash codes and so forth. The hashing algorithm in the program will return a hash number between 1 and 65336 (ie 0-65535). The algorithm is not particularly elegant and neither is the collision handling procedure. They are primarily there for demonstration purposes.
The program allows you to insert and search for records, whilst displaying a graphic showing the density of the records in the table. This is quite important as a hash table works most efficiently when the table is sparsely populated. The denser the number of occupied records in the table means that the chance of hitting another record becomes quite high.
Notice how fast the table is when there are perhaps 10,000 records in it when compared to how slow it gets when there are 50,000 plus records.
Code: ************************************************************************
*
* Program: Z_Hash_It
*
* Purpose: A short program to show how a hashing algorithm
* works
*
* Creation Date: 15/04/2004
*
* Requested By:
*
* Reference Doc:
*
* Author: R Harper
*
* Modification History:
*
* Date Reason Transport Who
*
************************************************************************
Report Z_Hash_It
Message-id 38
Line-Size 80
Line-Count 0
No Standard Page Heading.
*
Type-Pools: col.
*
Types: Hash_Key(10) type c,
Hash_Code type i,
Collison_Count type i,
*
Begin of Hash_Record,
Key type Hash_Key,
Count type Collison_Count,
End of Hash_Record,
*
Hash_Table type standard table of Hash_Record
initial size 0.
*
Data: t_Hasht type Hash_Table,
g_Key type Hash_Key,
g_Add type i,
g_Msg type NaTxt,
g_Runtime type i.
*
At Line-Selection.
*
Data: w_Num(10) type c.
*
Clear g_Key.
Clear g_Add.
Clear g_Msg.
*
* Search or add a key ??
*
Read Line 1 field value g_Key into g_Key.
If g_Key <> ''.
Perform Search_Insert using g_Key
t_Hasht
changing g_Runtime
g_msg.
EndIf.
*
* More records ?
*
Read Line 3 field value g_Add into w_Num.
If w_Num <> ''.
*
* Remove any commas from the number first
*
Translate w_Num using ', '.
Condense w_Num no-gaps.
Move w_Num to g_Add.
If g_Add > 0.
Perform Populate_Table using t_Hasht
g_Add
changing g_Msg
g_Runtime.
EndIf.
EndIf.
Clear g_Key.
Clear g_Add.
Perform Display_Report using t_Hasht g_Msg g_Runtime.
*
Start-Of-Selection.
*
Clear g_Msg.
Perform Populate_Table using t_Hasht 10000
changing g_Msg
g_Runtime.
Perform Display_Report using t_Hasht g_Msg g_Runtime.
*Eject
***********************************************************************
*
* Procedure: Calculate_Hash
*
* Purpose: Using the table of hash codes created and the
* current key, this routine calculates the hash
* code for the given key by calculating the initial
* record and then checking for collisions. A
* collision is where a key hashes to a specific
* row in the table that is already occupied by a
* different key.
*
* Entry: Key string to generate hash for.
* Table of existing hash records
*
* Exit: Hash code the specified key maps to or
* zero if no available record can be found
*
* Run time of the hash search.
*
* Called By: Perform Calculate_Hash using w_Hash_Key t_Hasht
* Changing w_Hash_Code.
*
* Calls:
*
* Modification History:
*
* Date Reason Version Who
*
Form Calculate_Hash Using pu_Key type Hash_Key
t_Hash_Table type Hash_Table
Changing pc_Hash_Code type Hash_Code
pc_Runtime type i.
*
Data: w_Hash_Record type Hash_Record,
w_Key type Hash_Key,
w_Hash type Hash_Code,
w_Start type i,
w_End type i.
*
* Calculate the initial key and check for a collision. If no
* collision is found then leave the hash as it is, otherwise
* handle the collision.
*
Get Run Time Field w_Start.
Move pu_Key to w_Key.
Translate w_Key to upper case.
Perform Calculate_Initial_Hash using w_Key changing w_Hash.
*
* Check for a collision
*
Read Table t_Hash_Table index w_Hash into w_Hash_Record.
If sy-subrc = 0.
If w_Hash_Record-Key <> w_Key.
Perform Hash_Collision using w_Key w_Hash t_hash_table
changing w_Hash.
EndIf.
EndIf.
*
Get Run Time field w_End.
Compute pc_Runtime = w_End - w_Start.
Move w_Hash to pc_Hash_Code.
EndForm.
*Eject
***********************************************************************
*
* Procedure: Calculate_Initial_Hash
*
* Purpose: This procedure uses the Variable String
* Exclusive-or method to calculate the hash code
* for a variable length string. The table t_Masks
* is used to inject an element of randomness to the
* hash code as hash tables work better when they
* are sparsly populated.
*
* The procedure calculates two hash codes for a
* given string which when multiplied provide an
* address space of 0 to 65535. This is adjusted by
* one to cope with the fact that index 0 on a table
* is an invalid index.
*
* This hashing algorithm can successfully
* distingush similar words, anagrams and
* palindromes.
*
* Entry: Key string to generate hash for.
*
* Exit: Hash code the specified key maps to. This will
* be the initial start point for a sequential
* search if a collision occurs.
*
* Called By: Perform Calculate_Initial_Hash using w_Hash_Key
* Changing w_Hash_Code.
*
* Calls:
*
* Modification History:
*
* Date Reason Version Who
*
Form Calculate_Initial_Hash using pu_string changing pc_hash.
*
* A simple macro to append records to a table. The parameter
* &1 must be a string.
*
Define Load_Table.
Move &1 to w_Mask.
Append w_Mask to t_Masks.
End-Of-Definition.
*
Statics: t_Masks type standard table of X
initial size 0.
*
Data: Begin of w_Char,
Asc type x,
End of w_Char,
*
w_String type Hash_Key,
w_Mask type x,
w_H type x,
w_H1 type x,
w_H2 type x,
w_Hash type i,
w_Pos type i,
w_Len type i.
*
* The t_Masks table contains a series of random numbers between 0 and
* 255. These are used to calculate the hash number for a given
* character. As these need to be identical for each run, they are
* hard coded here.
*
* As these are relevant to this procedure only, rather than make
* global and initialise them once, make them static and still only
* initialise them once.
*
Read table t_Masks index 1 transporting no fields.
If sy-subrc <> 0.
Load_Table: '8C', 'F7', '5F', 'A0', '23', 'BD', 'B7', 'DF',
'D1', 'AA', '45', '73', '97', '12', '1E', 'F2',
'40', 'E0', '93', '32', 'DD', '36', '4E', '0C',
'72', '54', '9E', '5F', 'EF', 'BB', '10', '57',
'62', '92', '3F', 'EF', '6A', '48', 'ED', 'B4',
'EF', '7B', '52', 'CC', '10', '19', 'B3', '38',
'5D', 'C5', '37', '56', '47', '7C', 'F7', 'AA',
'D4', '78', '54', 'DD', '97', '54', '8D', '06',
'E0', '72', '90', '29', '30', '9A', '11', 'FD',
'F0', 'E3', 'DA', 'F3', '62', 'D7', '62', '73',
'D7', 'D2', 'A0', '69', '23', 'AB', '21', '00',
'4E', '96', '59', 'AD', '8C', '49', '36', '70',
'6F', '5E', 'FB', '57', '5C', 'F9', '4C', '43',
'3B', 'AA', '85', 'EE', '73', '95', '50', '2D',
'16', 'D0', '77', '73', '58', '0C', 'F6', '97',
'46', '78', '55', 'D7', 'B5', 'E2', '35', '1C',
'78', '1F', '28', '7F', 'D6', 'AE', 'C6', '0D',
'3A', '98', 'FD', 'C7', '2D', '9A', 'A8', 'ED',
'82', '86', '63', '7D', 'D0', 'E7', '9E', 'F6',
'25', 'E4', 'F1', '61', 'F9', '67', 'AF', '92',
'61', '7D', 'BE', 'AC', '85', '00', 'A6', 'E3',
'54', '74', 'E7', '86', '77', '30', '90', '3C',
'83', 'BE', '0D', '8D', '72', '84', '41', 'A5',
'54', 'A3', 'D4', '55', '42', '1F', 'CF', '5B',
'94', '40', '66', 'E3', '53', '39', '14', '4D',
'F1', '08', 'EE', '31', '38', '9D', '30', 'A1',
'81', '3E', '1D', 'AE', '26', '2A', '06', '2D',
'3A', '7D', 'A8', 'BA', '77', '53', 'BA', 'FE',
'77', '30', 'C7', '2E', '27', 'A0', '3A', 'D4',
'79', '1A', 'B7', 'D2', '5A', '2A', 'B2', 'A4',
'E4', 'CF', '3A', 'E5', 'D4', '22', '15', '15',
'3E', '39', '12', '99', '7F', '4B', '9B', '03'.
EndIf.
Move pu_String to w_String.
Compute w_Len = Strlen( w_String ) - 1.
Clear w_hash.
If w_Len <> 0.
Translate w_String to Upper Case.
Move w_String+0(1) to w_Char.
Move w_Char-Asc to w_H1.
Compute w_H2 = w_H1 + 1.
Move 1 to w_Pos.
Do w_Len times.
Move w_String+w_Pos(1) to w_Char.
Move w_Char-Asc to w_H.
Compute w_H1 = w_H1 Bit-Xor w_H.
Read Table t_masks Index w_H1 into w_H1.
Add 1 to w_h.
Compute w_H2 = w_H2 Bit-Xor w_H.
Read Table t_masks Index w_H2 into w_H2.
Add 1 to w_Pos.
EndDo.
EndIf.
Compute w_Hash = 1 + ( w_H1 * 256 ) + w_H2.
Move w_Hash to pc_hash.
EndForm.
*Eject
***********************************************************************
*
* Procedure: Display_Report
*
* Purpose: Provides the input fields and a graphical display
* showing the distribution of the records inserted
* in the table in # Occupied rows per 100 rows.
*
* The report also has two input fields, a key
* value field and a 'More Rows' field.
*
* Entering a value in the key value field and
* clicking the line-select button at the top of
* report searches for and adds or displays the
* record.
*
* Entering a number in the 'More Rows' field
* populates that many more rows.
*
* Entry: Table of hashed keys.
* Any message to print.
* Last Hash search runtime
*
* Exit: As above
*
* Called By: Perform Display_Report using t_Hash_Table.
*
* Calls:
*
* Modification History:
*
* Date Reason Version Who
*
Form Display_Report using t_Hash_Table type Hash_Table
pu_Msg type NaTxt
pu_Runtime type i.
*
Define Output_Block.
*
* Need a new line ?
*
If w_Column > 75.
Write sy-vline.
Write :/c_Graphic_Start sy-vline no-gap.
Compute w_Column = c_Graphic_Start + 1.
EndIf.
Format Color = w_Block_Col.
Write '*' no-gap.
Format Reset Intensified on.
Add 1 to w_Column.
End-Of-Definition.
*
Constants: c_Graphic_Width type i value 73,
c_Graphic_Start type i value 4,
c_Block_Size type i value 100,
c_Max_Colours type i value 7,
c_Colour_Mod type i value 8.
Data: w_Hash_Record type Hash_Record,
w_Rec_Count type i,
w_Occupied type i,
w_Col_Size type i,
w_Col type i,
w_Block_Col type i,
w_Column type i,
w_Blocks_Left type i,
w_Start type i,
w_End type i,
w_Cur_Col type i.
*
Subtract 1 from sy-lsind.
Write :/ 'Enter Key :',g_Key input on. Hide g_Key.
Skip 1.
Write :/ 'Add More Rows:',g_Add input on. Hide g_Add.
Skip 1.
If pu_Msg <> ''.
Write :/ pu_Msg.
Skip 1.
EndIf.
*
Write:/ 'Longest Search Time:', pu_Runtime, 'Msecs'.
Skip 1.
*
* Display a schematic of the t_hash table where one block on the
* screen represents the percentage of occupied rows in that block
* of 100 records
*
* 7 colours by 2 intensities.....
*
Compute w_Col_Size = Trunc( c_Block_Size / c_Max_Colours ).
*
Move 0 to w_Rec_Count.
Move 0 to w_Occupied.
Write :/c_Graphic_Start sy-uline+0(c_Graphic_Width).
Write :/c_Graphic_Start sy-vline no-gap.
Compute w_Column = c_Graphic_Start + 1.
Loop at t_Hash_Table Into w_Hash_Record.
If w_Rec_Count = c_Block_Size.
*
* Decide the colour to use for this block
*
Compute w_Block_Col = w_Occupied Div w_Col_Size.
Compute w_Block_Col = w_Block_Col Mod c_Colour_mod.
Output_Block.
Move 0 to w_Rec_Count.
Move 0 to w_Occupied.
EndIf.
Add 1 to w_Rec_Count.
If w_Hash_Record-Key <> ''.
Add 1 to w_Occupied.
EndIf.
EndLoop.
*
* Finish off the last block and then pad to 65535.
*
Output_Block.
Describe table t_Hash_Table lines w_Blocks_Left.
Compute w_Blocks_Left = Trunc( ( 65535 - w_Blocks_Left )
div c_Block_Size ).
Move 0 to w_Block_Col.
Do w_Blocks_Left Times.
Output_Block.
EndDo.
Write at 76 sy-vline.
Write :/c_Graphic_Start sy-uline+0(c_Graphic_Width).
Skip 1.
Write :/ 'Key:'.
Move 0 to w_Start.
Move -1 to w_Cur_Col.
Do 100 times.
Compute w_Col = sy-Index Div w_Col_Size.
If w_Col <> w_Cur_Col.
If w_Cur_Col <> -1.
Compute w_Block_Col = w_Cur_Col Mod c_Colour_Mod.
Compute w_End = sy-Index - 1.
Format Color = w_Block_Col.
Write :/ 'Occupied: From',w_Start,
'to', w_End,
'of the last', c_Block_size.
Move sy-Index to w_Start.
EndIf.
Move w_Col to w_Cur_Col.
EndIf.
EndDo.
Compute w_Col = 100 Div w_Col_Size.
Compute w_Block_Col = w_Col Mod c_Colour_Mod.
Compute w_End = 100.
Format Color = w_Block_Col.
Write :/ 'Occupied: From',w_Start,
'to', w_End,
'of the last', c_Block_size.
Endform.
*Eject
***********************************************************************
*
* Procedure: Hash_Collision
*
* Purpose: This procedure handles the situation where one
* key hashes to the row number of a different key.
*
* In this case the initial hash code is used as a
* starting place, the table being searched
* in sequential fashion from that point onwards
* until either the key is found or a blank record
* is found.
*
* The table is limited to 65535 entries so the
* count cycles at the top of the table, ending
* when the original record is encountered again.
*
* If the top of the table is reached before row
* 65535 then this is treated as a new record.
*
* Entry: Key string to generate hash for.
* Calculated Hash code
* Table of existing hash records
*
* Exit: Hash code the specified key maps to or
* zero if no available record can be found
*
* Called By: Perform Hash_Collision using w_Hash_Key
* w_Hash_Code
* t_Hasht
* Changing w_Hash_Code.
*
* Calls:
*
* Modification History:
*
* Date Reason Version Who
*
Form Hash_Collision using pu_Key type Hash_Key
pu_Code type Hash_Code
t_Hash_Table type Hash_Table
Changing pc_Code type Hash_Code.
*
Define Increment_Hash.
Add 1 to w_Hash_Code.
If w_Hash_Code > 65535.
Move 1 to w_Hash_Code.
EndIf.
End-Of-Definition.
*
Data: w_Hash_Code type Hash_Code,
w_Hash_Record type Hash_Record.
*
Move pu_Code to w_Hash_Code.
Increment_Hash.
Read Table t_Hash_Table index w_Hash_Code into w_Hash_Record.
While w_Hash_Record-Key <> ''
and w_Hash_Record-Key <> pu_Key
and w_Hash_Code <> pu_Code
and sy-subrc = 0.
Increment_Hash.
Read Table t_Hash_Table index w_Hash_Code
into w_Hash_Record.
EndWhile.
*
* No Space ???
*
If w_Hash_Code = pu_Code.
Move 0 to w_Hash_Code.
EndIf.
*
Move w_Hash_Code to pc_Code.
EndForm.
*Eject
***********************************************************************
*
* Procedure: Insert_Row
*
* Purpose: This routine inserts a record in the hash table
* at the specified position. If the position does
* not exist, the table is extended until it does.
*
* Entry: Key value to insert
* Hash code (ie row number) to use
* Hash table to insert into
*
* Exit:
*
* Called By: Perform Insert_Row using w_key w_code t_hash.
*
* Calls:
*
* Modification History:
*
* Date Reason Version Who
*
Form Insert_Row using pu_Key type Hash_Key
pu_Code type Hash_Code
t_Hash_Table type Hash_Table.
*
Data w_Hash_Record type Hash_Record.
*
* Does the record exist ?
*
Read Table t_Hash_Table into w_Hash_Record index pu_Code.
If sy-subrc <> 0.
*
* Nope - Extend the table till it does
*
While Sy-Subrc <> 0.
Clear w_Hash_Record.
Append w_Hash_Record to t_Hash_Table.
Read Table t_Hash_Table index pu_Code into w_Hash_Record.
EndWhile.
EndIf.
*
* And insert the values.
*
Move pu_Key to w_Hash_Record-Key.
Move 0 to w_Hash_Record-Count.
Modify t_Hash_Table from w_Hash_Record index pu_Code.
EndForm.
*Eject
***********************************************************************
*
* Procedure: Populate_Table
*
* Purpose: This routine populates an internal table with
* a series of strings up to a max length of 10
* in their hashed positions to provide some data
* for testing the hashing function.
*
* Entry: Blank table of Hash Records
*
* Exit: Partially filled table of random strings.
* Runtime of last hash search.
*
* Called By: Perform Populate_Table using t_Hasht.
*
* Calls:
*
* Modification History:
*
* Date Reason Version Who
*
Form Populate_Table using t_Hash_Table type Hash_Table
pu_Add_Count type i
Changing pc_Msg type NaTxt
pc_Runtime type i.
Data: w_ran_int type i,
w_Len type i, " Length of key to generate
w_Key type Hash_Key, " Key string generated
w_Hash type Hash_Code, " Hash code of key string
w_Prcnt type f, " Progress
w_Msg type Natxt, " Progress text
w_Jog type f, " Boundary at which %'s
" displayed
w_Txt_Num(20) type c, " Num->Text
w_Runtime type i.
*
* Decide whether to display on 1's 10's 100's etc
*
Move 1 to w_Jog.
Move pu_Add_Count to w_Ran_Int.
While w_Ran_Int > 0.
Multiply w_Jog By 10.
Divide w_Ran_Int by 10.
EndWhile.
Divide w_Jog by 100.
If w_Jog > 10000.
Move 10000 to w_Jog.
EndIf.
*
Do pu_Add_Count times.
*
* How many long is the key ?
*
w_Key = ''.
Call Function 'QF05_RANDOM_INTEGER'
Exporting
Ran_Int_Max = 10
Ran_Int_Min = 1
Importing
Ran_Int = W_Len
Exceptions
Invalid_Input = 0
Others = 0.
*
* Generate the key
*
Do w_Len times.
Call Function 'QF05_RANDOM_INTEGER'
Exporting
Ran_Int_Max = 25
Ran_Int_Min = 0
Importing
Ran_Int = W_Ran_Int
Exceptions
Invalid_Input = 0
Others = 0.
Concatenate w_Key sy-ABCDE+w_Ran_Int(1) into w_Key.
EndDo.
*
* And put it in the table.
*
Perform Calculate_Hash using w_Key t_Hash_Table
changing w_hash
w_Runtime.
If w_Runtime > pc_Runtime.
Move w_Runtime to pc_RunTime.
EndIf.
*
* If the hash is zero then there's no place for it to go.....
*
If w_Hash <> 0.
Perform Insert_Row using w_Key w_Hash t_Hash_Table.
Else.
Exit.
EndIf.
*
* Show them we're still awake Every w_jog records
*
Compute w_Prcnt = Trunc( sy-Index / w_Jog ) * w_Jog.
If w_Prcnt = sy-Index.
Write sy-Index to w_Txt_Num.
Condense w_Txt_Num.
Write pu_Add_Count to w_Msg.
Condense w_Msg.
Concatenate w_Txt_Num
'of'
w_Msg
'added.'
into w_Msg
separated by ' '.
Compute w_Prcnt = ( sy-Index / pu_Add_Count ) * 100.
Call Function 'SAPGUI_PROGRESS_INDICATOR'
Exporting
Percentage = w_Prcnt
Text = w_Msg.
EndIf.
Enddo.
*
* Any message ?
*
If w_Hash = 0.
Move 'Table is full.' to pc_Msg.
EndIf.
EndForm.
*Eject
***********************************************************************
*
* Procedure: Search_Insert
*
* Purpose: This routine searches for the specified key. If
* the key is not found the key is inserted in the
* table.
*
* Entry: Hash key to insert
* Hash table
*
* Exit: Key is found or inserted into table
* Runtime of last hash search.
*
* Called By: Perform Populate_Table using t_Hasht.
*
* Calls:
*
* Modification History:
*
* Date Reason Version Who
*
Form Search_Insert using pu_Key type Hash_Key
t_Hash_Table type Hash_Table
Changing pc_Runtime type i
pc_Msg type Natxt..
*
Data: w_Hash_Record type Hash_Record,
w_Key type Hash_Key,
w_Hash type Hash_Code,
w_Runtime type i.
*
Move pu_Key to w_Key.
Translate w_Key to upper case.
Perform Calculate_Hash using w_Key t_Hash_Table
changing w_hash
w_Runtime.
If w_Runtime > pc_Runtime.
Move w_Runtime to pc_RunTime.
EndIf.
*
* If the hash is zero then there's no place for it to go.....
*
If w_Hash <> 0.
Read table t_Hash_Table into w_Hash_Record index w_Hash.
If w_Hash_Record-Key = ''.
Perform Insert_Row using w_Key w_Hash t_Hash_Table.
Concatenate w_Key 'Inserted into table'
into pc_msg
separated by ' '.
Else.
If w_Hash_Record-Key = w_Key.
Write w_Runtime to pc_Msg.
Condense pc_Msg.
Concatenate w_Key 'Found in' pc_Msg 'Msecs'
into pc_Msg
separated by ' '.
Else.
Move 'Whoops - problems here wrong key' to pc_Msg.
EndIf.
EndIf.
Else.
Move 'No table space.' to pc_Msg.
EndIf.
EndForm. Index Tables
Index tables are a generic name for the Standard and Sorted tables. The term index table is used in the declaration of a procedure or function module's arguments if the argument is a standard or sorted table and you have not declared a table type for the relevant table. There is however one downside to this in that you cannot use the READ TABLE command specifying a key. (The table has no structure....) You can however, loop round it quite happily, assigning a field symbol to the table structure.
For example, the procedure declaration:
Code: Form Seq_Search using pu_Key type Char_Key
t_Stdrd_Table type Value_Table. could be recorded as:
Code: Form Seq_Search using pu_Key type Char_Key
t_Stdrd_Table type Index Table. Any Table
Another declaration. This can be used in the same manner as Index tables to specify a generic table as a form parameter. The only operations (such as LOOP etc) that can be performed on a table declared as this type are those of the Hashed tables.
What use are the different tables.
The different table types are not provided just to make our lives difficult. They each have their own pros and cons. Generally the con is the amount of memory needed to implement a table of the specified type. The pros are varied.
Standard table types are (or I do anyway...) generally used to hold data as a temporary staging area after being read from the database (you do use SELECT ... INTO TABLE rather than SELECT ... ENDSELECT don't you ?). These type of tables can hold large amounts of information at the lowest cost to memory. Relatively they are slower to search than the sorted or hashed tables as the records could be unordered, the only sure way of finding that an entry is not in the table is to search the table from start to finish.
Sorted tables automatically sort the rows into a specified key order. This enables a faster search of the table as large amounts of information can be discounted quickly. These are handy as they provide easier ways of reporting control breaks and so forth. However, I do not tend to use these as either I provide the user with the ability to sort the report by whatever fields they require meaning that a fixed key limits this, or I tend to use Hash tables if I require a look up.
As mentioned above, and shown in the example program above, Hash tables are at their best being used as a look up table. The access time is fast, it's constant and using one of these properly can certainly speed up your program.
Related Items:
|
|
|
|
