Generalised Searching

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 29

Utility Corner: Generalised Searching¶

(The purpose of this column is to make you more productive by introducing you to utility functions. Think of utility functions as APL functions that have names instead of symbols. By expanding your function vocabulary, you’ll be able to write APL code that’s more concise, more efficient, and more readable.)

In last issue’s LIMBERING UP column, we asked you to design and write utility functions LEIOTA and LTIOTA to emulate (≤⍳) and (<⍳), in which ⍳ is a hypothetical operator that returns an array of indices into the vector left argument where each value in the right argument first relates true according to the relational function operand provided. Whew! That’s a mouthful. Here’s an example:

      38 42 75 84 (=⍳) 42 15 38
2 5 1

The number 42 is found in the 2nd index of the left argument; 15 is not found, so 5 is returned (one beyond the last index in the left argument); and 38 is found in the 1st position. This is the behaviour of the normal dyadic ⍳ function. Let’s try different relational functions:

      10 20 35 50 (≤⍳) 12 57 35
2 5 3
      10 20 35 50 (<⍳) 12 57 35
2 5 4

In the first of these two expressions, the first time 35 is less-than-or-equal any value of the left argument is in the 3rd position. In the second, the first time 35 is less-than any value of the left argument is in the 4th position.

Before we discuss the LEIOTA and LTIOTA functions that implement these hypothetical primitives, let’s get practical. What good are they? If available, how can you use them?

The (≤⍳) and (<⍳) functions have the useful property of mapping values into ranges of values. For example, suppose you want to classify all employees by age range, where you’ve defined five ranges:

1:       age≤10
2:    10<age≤20
3:    20<age≤35
4:    35<age≤50
5:    50<age

Given a vector of ages, say 12 57 35, you’d like to convert them to the corresponding range indices 1 to 5, in this case 2 3 5. This is exactly what (≤⍳) does. After using (≤⍳) awhile, you’d come to view its left argument as a vector of inclusive range upper limits. Any number in the right argument that is not in any of the defined ranges, i.e., that is greater than the largest upper limit, is assigned one greater than the last index of the left argument.

By a similar line of reasoning, you’d come to view the left argument of (<⍳) as a vector of noninclusive range upper limits. The only difference between (≤⍳) and (<⍳) is whether the limits are inclusive.

Now suppose you define these four age ranges:

1:    if 35<age≤50
2:    if 20<age≤35
3:    if 10<age≤20
4:          age≤10

You might be tempted to use 50 35 20 10 as the left argument:

      50 35 20 10 (≤⍳) 12 57 35
1 5 1

Unfortunately, the result is worthless. The meaningfulness of the results of (≤⍳) and (<⍳) requires that the values of the left argument be in ascending order.

Nevertheless, the shortcomings of these hypothetical primitive functions should not deter us. Since we’re the programmers, we can make our utility functions do whatever we want. Let’s call the utility functions UIOTAI (upper limit inclusive) and UIOTAN (noninclusive) instead of LEIOTA and LTIOTA.

Here’s what we want:

      50 35 20 10 UIOTAI 12 57 35
3 5 2
      50 35 20 10 UIOTAN 12 57 35
3 5 1

And, while we’re at it, let’s define two other functions that take lower limits (inclusive and noninclusive):

      10 20 35 50 LIOTAI 12 57 35
1 4 3
      10 20 35 50 LIOTAN 12 57 35
1 4 2

All four functions (UIOTAI, UIOTAN, LIOTAI, LIOTAN) require a vector left argument ( as does dyadic ⍳). The values in the left argument needn’t be sorted in any special order. They also needn’t be distinct, but, as with dyadic ⍳, they usually will be. Finally, the right argument does not need to be a vector. If it’s a matrix, the result will be a matrix too.

Now, to the solutions we received.

Gary Logan pointed out that IBM’s APL2 Language Reference Manual defines dyadic iota with the following identity:

      L⍳R    ↔    ⎕IO++/∨\~R∘.≡L

If L and R are simple (non-nested) arrays, ≡ can be replaced by =. Taking it a step further, = can be replaced by ≤ or by < to produce the behaviour of our hypothetical (≤⍳) and (<⍳) functions. In fact, in APL2 implementations that permit user-defined operators, the operator IOTA can be defined like so,

      ⎕vr'IOTA'

    ∇ Z←L(F IOTA)R
[1]   Z←⎕IO++/∧\~R∘.F L
    ∇

permitting this syntax:

      10 20 35 50 ≤IOTA 12 57 35
2 5 3
      10 20 35 50 <IOTA 12 57 35
2 5 4

This solution is direct, elegant, and general. Unfortunately, not all implementations of APL permit user-defined operators. Even if they did, some efficiency can be gained by knowing in advance the function to be used as the operand. For example, instead of using ~R∘.≤L, you can use R∘.>L:

    ∇ Z←L UIOTAI1 R
[1]   Z←⎕IO++/∧\R∘.>L
    ∇

Furthermore, as Henri Brudzewsky noted, the function ∧\ (leading) is redundant if the values of the left argument are in ascending order, leading to:

    ∇ Z←L UIOTAI2 R
[1]   Z←⎕IO++/R∘.>L
    ∇

Unfortunately, neither of these solutions gives the result you want when the values of the left argument are in descending order.

Also, they rely on outer product, which can be a resource hog. Since all possible combinations of the values in the left and right arguments are compared, two large arguments can cause the algorithm to bog down, and possibly generate a WS FULL message. For example, if the left argument has 100 values (ranges), and the right argument has 10,000 numbers, one million comparisons will be made, and a 1000 by 100 Boolean matrix will be constructed and manipulated.

To avoid the outer product dilemma, Eric Baelen offered a solution that uses grade-up (⍋) to perform the comparisons. More accurately, his solution uses ranking (⍋⍋). Remember, ranking tells you the relative ranking of each value in its argument relative to the other values. The ranking 1 is assigned to the smallest number, 2 to the next smallest, and so on. For example:

      ⍋⍋27 15 5 36 22 15 33
5 2 1 7 4 3 6

Here’s Eric’s solution:

    ∇ Z←L UIOTAI3 R
[1]   Z←⎕IO+((⍴R)↑⍋⍋R,L)-⍋⍋R
    ∇

The insight that leads to this solution comes from the observation that respective rankings of the values in a vector increase as more values are catenated to the end of the vector. Specifically, they each increase by the number of values catenated that are less than that value. By catenating the limits (L) to the end of the values (R), and comparing the resulting rankings to the rankings without the limits catenated, you can quickly determine how many limits are less that each value. The result follows directly.

In general, the grade functions are surprisingly efficient for large arguments – more efficient than outer product. Unfortunately, this solution performs four grades. If the left and right arguments have 100 and 10,000 elements respectively, two grades of length 10,100 and two grades of length 1000 are performed. That’s a lot of grading.

Fortunately, the ranking process can be made somewhat more efficient by taking advantage of the fact that the leftmost ⍋ in the expression ⍋⍋V is operating on a permutation vector (a vector of some arrangement of the elements ⍳⍴V). Indexed assignment can be used in place of the second grade-up:

This leads to the next solution:

    ∇ Z←L UIOTAI4 R;G
[1]   Z←G←⍋R,L
[2]   Z[G]←⍳⍴G
[3]   R←G←⍋R
[4]   R[G]←⍳⍴G
[5]   Z←⎕IO+((⍴R)↑Z)-R
    ∇

Using ⍋ twice is faster than using it four times, but once would be better yet. Paul Zocco submitted a solution that does just that. We’ve left the comments in his solution for obvious reasons:

    ∇ R←UPPER UIOTAI5 VALS;G;I;M
[1]    ⍝ Returns the index of the value of
[2]    ⍝ the vector UPPER that is the
[3]    ⍝ nearest upper bound (inclusive)
[4]    ⍝ for each element of the vector
[5]    ⍝ VALS. Values in UPPER need not be
[6]    ⍝ ascending or distinct. ⎕IO+⍴UPPER
[7]    ⍝ is returned for elements in VALS
[8]    ⍝ above the largest value in UPPER
[9]    ⍝
[10]   ⍝ Combine and sort up to use 1st val
[11]   ⍝ in UPPER if vals not distinct:
[12]    R←G←⍋VALS,UPPER
[13]   ⍝ Flag elts from UPPER in grade vec:
[14]    I←(G≥⎕IO+⍴VALS)/⍳⍴G
[15]   ⍝ Inds into UPPER, in sorted order,
[16]   ⍝ using "one greater" for values
[17]   ⍝ above largest in UPPER:
[18]    M←(G[I]-⍴VALS),⎕IO+⍴UPPER
[19]   ⍝ Replicate inds for values in
[20]   ⍝ corresp. ranges:
[21]    R[G]←((I,⎕IO+⍴G)-⎕IO,I)/M
[22]    R←(-⍴UPPER)↓R ⍝ Discard UPPER inds
    ∇

Paul’s function permits the left argument vector of limits to contain duplicates and to be in any order. This is an advantage over the other functions listed. However, the logic assumes the right argument is a vector. To make the function more general, the right argument can be ravelled at the beginning, and the result can be reshaped at the end to the argument’s original shape.

Let’s look at the efficiency of these functions. We timed each of them under APL*PLUS II/386 using a left argument of 5 elements and a right argument of 10,000 elements, and again with a left argument of 100 elements. Both arguments were all integers. The values were uniformly distributed among the ranges defined.

Here are the results; all times were scaled to that of the fastest algorithm:

As you can see, the outer product solutions go to sleep when both arguments get large.

Since UIOTAI5 is the fastest function and produces the desired behaviour for a left argument whose values contain duplicates or are not in strictly sorted order, we took the liberty to write the UIOTAN, LIOTAI, and LIOTAN functions in the same style:

    ∇ R←UPPER UIOTAN VALS;G;I;M
[1]   R←G←⍒VALS,UPPER
[2]   I←(G≥⎕IO+⍴VALS)/⍳⍴G
[3]   M←(⎕IO+⍴UPPER),G[I]-⍴VALS
[4]   R[G]←((I,⎕IO+⍴G)-⎕IO,I)/M
[5]   R←(-⍴UPPER)↓R
    ∇

    ∇ R←LOWER LIOTAI VALS;G;I;M
[1]   R←G←⍒VALS,LOWER
[2]   I←(G≥⎕IO+⍴VALS)/⍳⍴G
[3]   M←(G[I]-⍴VALS),⎕IO+⍴LOWER
[4]   R[G]←((I,⎕IO+⍴G)-⎕IO,I)/M
[5]   R←(-⍴LOWER)↓R
    ∇

    ∇ R←LOWER LIOTAN VALS;G;I;M
[1]   R←G←⍋VALS,LOWER
[2]   I←(G≥⎕IO+⍴VALS)/⍳⍴G
[3]   M←(⎕IO+⍴LOWER),G[I]-⍴VALS
[4]   R[G]←((I,⎕IO+⍴G)-⎕IO,I)/M
[5]   R←(-⍴LOWER)↓R
    ∇

The comments are basically the same.

Ray Cannon has submitted a new solution for LTIOTA and LEIOTA using dynamic functions:

LEIOTA←{⊃1++/⍺{⍺<⍵}¨(⊂⍵)}
LTIOTA←{⊃1++/⍺{⍺≤⍵}¨(⊂⍵)}

and an operator solution which can take < or ≤ as the function argument:

IOTA←{⊃1++/⍺ ⍺⍺{⍺ ⍺⍺ ⍵}¨(⊂⍵)}