Sorting Lists of Names

This book page describes and compares several methods for sorting lists of names. It revisits using attributes for rapid sorting, with attention to their global effect on strings. It demonstrates the use of the lexorder[n] option to sort and it illustrates the use of convert/local.

Introduction

Occasionally it is useful to sort a list of names—usually variables extracted from an expression—into a repeatable order. The simple and obvious way to do this is with the sort command.

      sort([x, y, Z, a1, a1]);
                                     [Z, a1, a1, x, y]
    

That approach does not work if there are indexed names in the list.

      sort([x, y, Z, a[1], a[2]]);
                                    [x, y, a[1], a[2], Z]
    

The elements are sorted, but by machine address rather than alphabetically. This can be shown using the addressof command:

      map(addressof,%);
                [135350720, 141574716, 143418428, 143418444, 143451544]
    

The explanation can be found from a careful reading of the sort help page. A list of symbols are, by default, sorted lexically. However, an indexed name is not a symbol. Consequently, the list is sorted by machine address, which is session dependent and hence not repeatable.

Sorting Techniques

The following sections look at a few ways to use the Maple sort command to sort a list of names into a repeatable order. Ideally the same final permutation is returned for any given permutation of the elements in the list.

Sorting as strings

The sort command takes an optional second argument which can be an ordering function that takes two arguments—elements of the list—and returns true if the first argument is sorted with respect to the second, false otherwise. To sort names we can compare them as strings.

      SortNames[1] := proc(names :: list)
          sort( names
                , (a,b) -> convert(a,string) <= convert(b,string)
              );
      end proc:

      SortNames[1]( [x, y, Z, a[1], a[2]] );
                                             [ Z, a[1], a[2], x, y ]
    

Note the use of the inequality `<=' in the comparison rather than strict inequality, `<'. That prevents an unnecessary swap if the strings are equal, and achieves a stable sorting, that is, one in which equal elements maintain their original order.

This procedure has two problems. First, it is rather slow, at least in comparison to later techniques. Second, because they map to the same string, it cannot distinguish the indexed variable x[1] and the symbol `x[1]`. We can correct this latter problem by using sprintf with the %a format string to convert names to strings:

      SortNames[2] := proc(names :: list)
          sort( names
                , (a,b) -> sprintf("%a",a) <= sprintf("%a",b)
              );
      end proc:

      SortNames[2]( [x, y, Z, `a[1]`, a[1], a[2], `b[1]` ] );
                                    [Z, `a[1]`, `b[1]`, a[1], a[2], x, y]

    

Sorting with attributes

In a previous blog entry

I explained how attributes can be used to sort a list of floating-point numbers with respect to a relatively expensive function. That speeded up the operation by (1) reducing the number of calls to the function to the number of elements in the list, and (2) removing the need to call a user-defined order function, which is invariably slower than the built-in Maple order functions. The same technique can be employed here. However, because we are sorting strings rather than floats, there are a few new subtleties to consider.

Here is the basic routine

      SortNames[3] := proc(names :: list)
      local n;
          map(attributes, sort([seq](setattribute(sprintf("%a",n),n)
                                     , n = names)
                               , 'string'));
      end proc:
    

If you have not read the previously mentioned article this may need a bit of explanation. The [seq](...) expression creates a list of strings, using sprintf as previously described. As each string is created it is passed to setattribute which assigns the original name as the attribute to the string. The resulting list of strings is then sorted lexically. Finally the attributes of the sorted strings are extracted and returned. Because the attributes are the original names of the strings, the returned list is the sorted list of names.

This procedure has two flaws: one minor, one major.

The minor flaw is that it has global side-effects due to the way that Maple handles strings. Each unique string in Maple exists in memory in one location. Adding an attribute to a string does not change this location. Calling setattribute replaces any preexisting attributes, so if some other procedure was using attributes with strings, and one of the strings matched a name passed to this procedure, its attribute would be changed.

The major flaw is subtle but potentially fatal. Suppose two distinct names mapped to the same string. When the attributes are extracted from the sorted strings, both strings are mapped to the same name, the second one in the original list. The returned list of names, then, does not contain one of the original names. Using sprintf rather than convert/string eliminates some of the collisions, however, it is still possible for two names to map to the same string. A simple example is escaped local variables, which can be readily generated with convert/local:

      lst := map(convert, [a,a], `local`):
      convert(lst, set);
                                                 {a,a}
    

To demonstrate that this really occurs convert the sorted list to a set.

      convert(Sort[3](lst), set);
                                                  {a}
    

Avoiding Collisions

Both flaws in SortNames[3] can be corrected by attaching the attributes to a list containing a string rather than the string itself. Unlike attributes attached to a string, attributes attached to a list (and most attributable objects) only affect that instance of the object; two lists that are otherwise identical but have separate attributes are different elements in Maple. This can be verified with

      lst := [1,2]:
      lst1 := setattribute(lst,1):
      lst2 := setattribute(lst,2):
      lst3 := setattribute(lst,2):
      map(evalb, [lst1=lst2, lst2=lst3]);
                                          [ false, true ]
    

Normally, enclosing elements of a list in lists requires providing a user-defined order function to sort to unpack and compare them, which reduces the advantage of this technique. However, sort takes the optional symbol lexorder[n] which tells it to lexically compare the n'th element of each sublist. The following procedure does just that, using n=1.

      SortNames[4] := proc(names :: list)
      local n;
         map(attributes, sort([seq](setattribute([sprintf]("%a",n),n)
                                    , n = names)
                              , 'lexorder'[1]));
      end proc:
    

Demonstrate that this fixes the collision problem.

      convert(SortNames[4](lst), set);
                                       {a,a}
    

Sorting as Symbols

The procedures discussed convert names to strings and then sort the strings. Another option is to convert names to symbols and sort the symbols. The Maple procedure convert/symbol may be used to convert names (and other expressions) to symbols. However, the distinct names a[1] and `a[1]` get mapped to the same symbol. To avoid that, we can use convert/local, which maps each name to a distinct symbol.

      SortNames[5] := proc(names :: list)
      local n;
          map(attributes, sort([seq](setattribute(convert(n,'`local`'),n)
                                     , n = names)));
      end proc:
    

      convert(SortNames[5](lst), set);
                                       {a,a}
    

Remaining Issue

The goal was to create a procedure that rapidly sorts any permutation of a list of names into a session-independent, repeatable, sorted order. The results, SortNames[4] and SortNames[5], do not quite meet that goal. If the list of names contains names that lexically match but are different (escaped local variables) then the resulting order of those names is identical to their relative input order. Otherwise those procedures work as required. This is a relatively benign failure; furthermore it is not clear it can be be avoided.

Performance Comparison

As shown in the following table, using attributes (cases 3-5) is substantially faster and uses less memory than providing a user-defined order function to sort (cases 1-2). SortNames[4], which uses lists to avoid string collisions, is slighter slower, but more robust, than SortNames[3], but faster than SortNames[5], which uses symbols. SortNames[4] is the best overall choice.

      $ tmaple sort-names.mpl

	Compare performance of sorting names.
	Each test sorts the same list of 50 names of 5 characters 500 times.

	time (s)  used (MB)  alloc (MB)  gctimes  proc
	--------  ---------  ----------  -------  ----
	  2.28     54.70       36.12         2    SortNames[1]
	  3.73     47.19       35.93         2    SortNames[2]
	  0.40      4.90        3.44         1    SortNames[3]
	  0.46      6.25        3.50         1    SortNames[4]
	  0.60     10.63        6.56         1    SortNames[5]
    

The table was generated using custom tools for accurately and repeatably measuring the time and memory usage of Maple procedures. They shall be the subject of another article.