Channels ▼

Open Source

The Power of Associative Arrays

Howard Fosdick is an independent DBA contractor who wrote the Rexx Programmer's Reference, a 700-page guide to open source Rexx, its tools, and interfaces. Les Koehler is a retired Advisory Software Engineer from IBM. He was a contributor during the development of Rexx and the first person outside of the U.K. to have a copy of Rexx.

Here's a problem for you. You need to match all the names in two lists, and create a third list consisting of names in the second list but not in the first. Only exact matches count. How do you do it?

You could read the names into two arrays (tables). Then read each name in one of the arrays, and search through the entire other array for a match. Copy names that don't match into a third array.

You might consider sorting the arrays to speed up the searching and matching process. And you might eliminate I/O time by processing only in memory.

Les Koehler faced this problem in the real world. He had an accounting program on his hands, written by a predecessor, that matched the accounting records they had accumulated against the accounting records that a vendor sent them daily. The format and field definitions varied between the two files. The program ran for several hours to process 25,000 records using the simple "walk the list" technique I just described. Les reduced the run time to less than a minute using associative arrays. In this article, I explain how he did it.

Associative Arrays

Conventional arrays or tables are simply lists of items indexed by numeric subscripts. For example, a simple list or one-dimensional array might look like this:

 ...etc ...

Subscripts can be variables, but those variables must resolve to numeric values.

Associative arrays genericize this concept. They permit entry into the array by arbitrary strings. So entries in the array are referenced by their name, rather than by their location in the array. The array can be considered a collection of keys and related values. For example, you might have:

 ...etc ...

Subscripts, such as string_index_a, could either be a literal value or a variable that resolves into some value. That value could be anything--string or numeric.

The relationship between a key and its value is sometimes called a "mapping" or "binding." The most important associative operation is the simple lookup or "indexing."

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.