In a previous blog entry I described a novel method, proposed by Robert Israel, for sorting a list of lists of small positive integers, specifically those less than 256. It is significantly faster than the usual method. Roman Pearce responded with a method for rapidly sorting listlists of integers (a listlist is a list of sublists with identical number of elements), regardless of size. While not as fast as Robert's technique, it, too, is significantly faster than the usual method and has no restriction on integer size.

Roman's Method

Roman's method uses a scalar product to compute a key for each list. Here is a modified version of his proposal:

sortLL1 := proc(L::listlist(nonnegint))
local B,X,n,x,j;
    B := max(map(op,L)[])+1;
    n := nops(L[1]);
    X := [seq(B^(n-j), j=1..n)];
    SORT_W_ATTR(Float(inner(X,x)), x, x=L, `<`);
end proc:

The variable B is assigned one more than the largest integer in L, the listlist of integers. The variable X is assigned the list [B^n-1,B^n-2,...,B,1], which is dot multiplied (using the undocumented builtin procedure, inner) with each sublist in L to compute the key. Because B is larger than the largest integer in L, the computed key is guaranteed to be injective and monotonic. SORT_W_ATTR does the actual sorting. It uses the technique of sorting with attributes, which is fast because it does not need to compute the inverse of the scalar.

Macros

SORT_W_ATTR is a macro, not a Maple procedure. As such, it can only be used in code that is processed by tty maple (cmaple). Maple macros are limited, but occasionally useful for simplifying the source code. See the help page ?preprocessor for details. Here is the definition of SORT_W_ATTR.

$define SORT_W_ATTR(k,x,e,F) \
map(attributes, sort([seq(setattribute(k,x),e)],F))

If you do not use tty maple, you can manually expand the macro in the assignment to sortLL1. The equivalent line is

map(attributes, sort([seq(setattribute(Float(inner(X,x)),x),x=L)],`<`));

Optimizing the Base

While this method is impressively fast, it has a practical problem. As B and n (the length of the sublists) increase, the time required to compute the scalar product increase. Theoretically one would expect this to be O(Bⁿ m log m), where m is the number of sublists in L.

Can we do better? My first thought was to improve the vector, X, used in the dot product. Using powers of B for all the components is too conservative. Here is a modified approach that uses the maximum value in each column (think of L as a matrix) to form the base for each component in X.

sortLL2 := proc(L::listlist(nonnegint))
local M,n,B,X,C,k,x;
    M := map(lst -> max(op(lst)), `kernel/transpose`(L));
    n := nops(M);
    B := rtable(1..n);
    C := 0;
    for k from n to 1 by -1 do
        B[k] := C + 1;
        C := M[k]*B[k] + C;
    end do;
    X := [seq(B[k], k=1..n)];
    SORT_W_ATTR(Float(inner(X,x)), x, x=L, `<`);
end proc:

While it takes longer to compute this X, that is only done once, so the resulting speed-up in the scalar products for large lists can be significant. Alas, for uniformly distributed random integers, the effect is miniscule.

Strings

After reflecting on this during my daily walk, I came up with a simpler way to compute an appropriate key, using string catenation rather than arithmetic. The following example shows how a listlist of positive integers is converted to a corresponding list of strings.

[  [  3, 400,   2 ] → "103" "1400" "1002" → "10314001002"
 , [ 20,  31, 203 ] → "120" "1031" "1203" → "12010311203"
 , [  0,  12,  12 ] → "100" "1012" "1012" → "10010121012"
]

Here is the code that implements this conversion.

sortLL3 := proc(L::listlist(nonnegint))
local X,x,n,i;
    X := map(x -> 10^length(max(op(x))), `kernel/transpose`(L));
    n := nops(X);
    SORT_W_ATTR(cat("", seq(X[i]+x[i], i=1..n)), x, x=L, 'lexorder');
end proc:

A minor improvement can be made by using Maple's ability to directly add sequences, term by term:

sortLL4 := proc(L::listlist(nonnegint))
local X,x;
    X := seq(10^length(max(op(x))), x = `kernel/transpose`(L));
    SORT_W_ATTR(cat("", X+x[]), x, x=L, 'lexorder');
end proc:

Negative Integers

Procedure sortLL4 is restricted to nonnegative integers (do you see why?). A slight modification removes this restriction:

sortLL5 := proc(L::listlist(integer))
local X,x;
    X := seq(2*10^length(max((-min,max)(op(x)))), x = `kernel/transpose`(L));
    SORT_W_ATTR(cat("", X+x[]), x, x=L, 'lexorder');
end proc:

Caveat

Using strings with sorting-by-attributes has a subtle but serious flaw. It is not thread-safe. All Maple strings, regardless of any attached attributes, share a common address. This can be seen by doing

sortLL4([[3,4],[1,2]]);
                        [[1,2],[3,4]]
attributes("1112");
                        [1,2]

If two threads called sortLL5 concurrently, a string attributed by one thread could be changed by the other. The call to map(attributes, . ) would then insert a sublist from one thread into the output of the other.

Currently, very few Maple routines use threads, and not all the existing code is thread-safe. However, in the future, as multicore devices become popular, I expect that thread-safety will be important.

The Threads package provides mutexes, which can prevent collisions in data structures however, in this case, because strings are inherently global, there is no robust way to use mutex's to avoid collisions. To avoid the thread-safety issue, attributes must not be applied to strings.

Solution

There is, fortunately, a solution to the thread-safety issue: enclose each string in a list and apply the attribute to the list. The Maple sort procedure can use a builtin comparator, lexorder[n], for comparing lists of strings. The index to lexorder specifies the element in the list to compare. Here is the thread-safe code:

sortLL6 := proc(L::listlist(integer))
local X,x;
    X := seq(2*10^length(max((-min,max)(op(x)))), x = `kernel/transpose`(L));
    SORT_W_ATTR([cat("", X+x[])], x, x=L, 'lexorder'[1]);
end proc:

Alas, this modification reduces the speed of the routine by about a factor of 2, compared to the non thread-safe version. However, it is still faster, and uses less memory, than sortLL1.

Comparison

Here are plots comparing the time and memory usage of each routine. Integers are uniformly distributed from 1 to max.

Vary Number of Sublists

Fix n=5 (number of integers in each list)
    max=10^5
Vary m from 10 to 10^3

Vary Number of Integers in Sublists

Fix m=100 (number of sublists)
    max=10^5
Vary n from 1 to 100

Vary Maximum Integer

Fix m=100 (number of sublists)
    n=5   (number of integers in each list)
Vary max from 10 to 10^4

These plots were created using the Tine package. Here is the Maple Code used to assign and measure the procedures described here.