The Schwartz transform is an idiom that appeared in the Perl programming language , which solves the problem of efficiently sorting lists of elements by complex (calculated) attributes.
The idea is to compare the computed attributes of the elements (for example, the length of the string, part of the string, squared number, other formulas and external queries) once to calculate all the elements and put them into a temporary array, which is then sorted by the standard sorting function according to these results, then the temporary data is discarded. In essence, this is caching (temporary storage) of calculated attributes, since they are used repeatedly during sorting (when comparing elements). In Perl , thanks to the use of the "default variable", this algorithm fits in one expression of three functions, that is, very briefly and clearly.
The idiom got its name in honor of Randall Schwartz , who demonstrated it some time after the release of Perl 5 in 1994 . The term "Schwartz transform" was used for many years exclusively for the Perl programming language, but later this transform was adapted by other programmers for other languages (for example, Python ). The algorithm used in the Schwartz transform existed in some programming languages (without a special name) even before it was popularized in the Perl programmer community as an idiom.
Example
Suppose you want to sort a list of words ("aaaa", "a", "aa") by the length of the words. First you need to create a list (["aaaa", 4], ["a", 1], ["aa", 2]), then sort it by a numerical value, and then from the resulting list (["a", 1] , [“Aa”, 2], [“aaaa”, 4]) delete the numbers. The result will be a list ("a", "aa", "aaaa"). The described algorithm is written as a Schwartz transform as follows:
@sorted = map { $ _ -> [ 0 ] }
sort { $ a -> [ 1 ] <=> $ b -> [ 1 ] } # numerical comparison
map { [ $ _ , length ( $ _ )] } # count line lengths
@unsorted ;