CELL MATCH

CELL MATCH (LET)

Let Subcommand

Return the index in an array where the array value matches a scalar value.

Given a scalar value, VAL, and an array, X, sort the values in X and then find the index, IVAL, such that
\( X_{i} \le \mbox{VAL} < X_{i+1} \)

If \( \mbox{VAL} < X_{1} \), set IVAL to 0. If \( \mbox{VAL} > X_{N} \), set IVAL to N+1.

The CELL MATCH command will do this for an array of values.

This command was motivated in the implementation of the P-square algorithm for one-pass estimation of percentiles.

LET <index> = CELL MATCH <x> <value>
                        <SUBSET/EXCEPT/FOR qualification>
where <y> is a response variable;
            <xseq> is a variable that defines the sequence number for the response variable;
            <x1> ... <x6> is a list of one to six group-id variables;
and where the <SUBSET/EXCEPT/FOR qualification> is optional and rarely used in this context.

Neither the <x> nor the <value> variables need to be pre-sorted. The output variable <index> will be the same length as <value>.

LET IINDX = CELL MATCH X VAL

None

None

MATCH	=	Match a column of values to another column of numbers and return the index of the matching value.
SORT	=	Sort the elements of a variable.
CODE	=	Generate a coded variable.
SEQUENCE	=	Generate a sequence of numbers.

Jain and Chlamtac (1985), "The P^2 Algorithm for Dynamic Calculation of Quantiles and Histograms without Storing Observations," Communications of the ACM, 28, No. 10, pp. 1076-1085.

Raatikanien (1987), "Simultaneous Estimation of Several Percentiles," Simulation, pp. 159-164.

Data Management

2018/08

 
. Purpose:  Demonstrate P-square algorithm for one-pass
.           estimation of percentiles.
.
dimension 40 columns
read y
 0.02
 0.5
 0.74
 3.39
 0.83
22.37
10.15
15.43
38.62
15.92
34.60
10.28
 1.47
 0.40
 0.05
11.39
 0.27
 0.42
 0.09
11.37
end of data
let ny = size y
.
. Step 2:   Initializations based on first 2*m + 3 data points.
.
let p = data 0.1 0.5 0.9
let m = size p
let ninit = 2*m + 3
let q = y
retain q for i = 1 1 ninit
let q = sort q
let n = sequence 1 1 ninit
let f = 0 for i = 1 1 ninit
let f(ninit) = 1
loop for k = 1 1 m
    let iindx = 2*k + 1
    let f(iindx) = p(k)
end of loop
let mp1 = m + 1
loop for k = 1 1 mp1
    let iindx1 = 2*k - 1
    let iindx2 = 2*k + 1
    let iindx3 = 2*k
    let aval1 = f(iindx1)
    let aval2 = f(iindx2)
    let aval3 = (aval1 + aval2)/2
    let f(iindx3) = aval3
end of loop
let d = 1 + 2*(m+1)*f
.
. Step 3:   Now loop through remaining points
.
let nstrt = ninit + 1
delete k
.
loop for k = nstrt 1 ny
    let ynew = y(k)
    let qmin = q(1)
    let qmax = q(ninit)
    if ynew < q1
       let ak = 1
       let q(1) = ynew
    else if ynew > qmax
       let ak = ninit
       let q(ninit) = qmax
    else
       let val = combine ynew
       let iindx = cell match q val
       let ak = iindx(1)
       delete val iindx
    end of if
    .
    let start = ak + 1
    let n = n + 1 for i = start 1 ninit
    let d = d + f
    .
    let mstop = 2*m + 2
    loop for l = 2 1 mstop
        let lm1 = l - 1
        let lp1 = l + 1
        .
        let aval1  = d(l)
        let aval2  = n(l)
        let di = aval1 - aval2
        .
        let aval1  = n(lp1)
        let dp = aval1 - aval2
        .
        let aval1  = n(lm1)
        let dm = aval1 - aval2
        .
        let aval1 = q(lp1)
        let aval2 = q(l)
        let qp = (aval1 - aval2)/dp
        .
        let aval1 = q(lm1)
        let qm = (aval1 - aval2)/dm
        .
        let nl   = n(l)
        let ql   = q(l)
        let qlm1 = q(lm1)
        let qlp1 = q(lp1)
        .
        if di >= 1 and dp > 1
           let qt = ql + ((1 - dm)*qp + (dp -1)*qm)/(dp-dm)
           if qlm1 < qt and qt < qlp1 then
              let q(l) = qt
           else
              let q(l) = ql + qp
           end of if
           let n(l) = nl + 1
        else if di <= 1 and dm < -1
           let qt = ql - ((1 + dp)*qm - (dm +1)*qp)/(dp-dm)
           if qlm1 < qt and qt < qlp1 then
              let q(l) = qt
           else
              let q(l) = ql - qm
           end of if
           let n(l) = nl - 1
        end of if
        .
    end of loop
    .
end of loop
.
set write decimals 4
loop for k = 1 1 m
    let iindx1 = 1 + 2*k
    let aval = q(iindx1)
    let qsave(k) = aval
end of loop
print "Estimated 0.10, 0.50, 0.90 quantiles"
print " "
print qsave
    

The following output is returned

 
Estimated 0.10, 0.50, 0.90 quantiles
 
 
---------------
          QSAVE
---------------
         0.1324
         2.9317
        19.7914