Schwartzian transform - Wikipedia

Jump to content

Search

Search

Donate

Create account

Log in

Personal tools

Donate

Create account

Log in

Schwartzian transform

4 languages

Català<br>日本語<br>Polski<br>Русский

Edit links

From Wikipedia, the free encyclopedia

Programming idiom for efficiently sorting a list by a computed key

This article includes a list of general references but lacks corresponding inline citations . Please help improve this article by introducing more precise citations. (February 2024) (Learn how and when to remove this message)

In computer programming, the Schwartzian transform is a technique used to improve the efficiency of sorting a list of items. This idiom[1] is appropriate for comparison-based sorting when the ordering is actually based on the ordering of a certain property (the key) of the elements, where computing that property is an expensive operation that should be performed a minimal number of times. The Schwartzian transform is notable in that it does not use named temporary arrays.

The Schwartzian transform is a version of a Lisp idiom known as decorate-sort-undecorate , which avoids recomputing the sort keys by temporarily associating them with the input items. This approach is similar to memoization, which avoids repeating the calculation of the key corresponding to a specific input value. By comparison, this idiom assures that each input item's key is calculated exactly once, which may still result in repeating some calculations if the input data contains duplicate items.

The idiom is named after Randal L. Schwartz, who first demonstrated it in Perl shortly after the release of Perl 5 in 1994. The term "Schwartzian transform" applied solely to Perl programming for a number of years, but it has later been adopted by some users of other languages, such as Python, to refer to similar idioms in those languages. However, the algorithm was already in use in other languages (under no specific name) before it was popularized among the Perl community in the form of that particular idiom by Schwartz. The term "Schwartzian transform" indicates a specific idiom, and not the algorithm in general.

For example, to sort the word list ("aaaa","a","aa") according to word length: first build the list (["aaaa",4],["a",1],["aa",2]), then sort it according to the numeric values getting (["a",1],["aa",2],["aaaa",4]), then strip off the numbers and you get ("a","aa","aaaa"). That was the algorithm in general, so it does not count as a transform. To make it a true Schwartzian transform, it would be done in Perl like this:

[0] }\n sort { $a->[1] $b->[1] or $a->[0] cmp $b->[0] } # Use numeric comparison, fall back to string sort on original\n map { [$_, length($_)] } # Calculate the length of the string\n @unsorted;\n"}}'>@sorted = map { $_->[0] }<br>sort { $a->[1] $b->[1] or $a->[0] cmp $b->[0] } # Use numeric comparison, fall back to string sort on original<br>map { [$_, length($_)] } # Calculate the length of the string<br>@unsorted;

The Perl idiom<br>[edit]

The general form of the Schwartzian transform is:

[0] }\n sort { $a->[1] cmp $b->[1] or $a->[0] cmp $b->[0] }\n map { [$_, foo($_)] }\n @unsorted;\n"}}'>@sorted = map { $_->[0] }<br>sort { $a->[1] cmp $b->[1] or $a->[0] cmp $b->[0] }<br>map { [$_, foo($_)] }<br>@unsorted;

Here foo($_) represents an expression that takes $_ (each item of the list in turn) and produces the corresponding value that is to be compared in its stead.

Reading from right to left (or from the bottom to the top):

the original list @unsorted is fed into a map operation that wraps each item into a (reference to an anonymous 2-element) array consisting of itself and the calculated value that will determine its sort order (list of item becomes a list of [item, value]);

then the list of lists produced by map is fed into sort, which sorts it according to the values previously calculated (list of [item, value] ⇒ sorted list of [item, value]);

finally, another map operation unwraps the values (from the anonymous array) used for the sorting, producing the items of the original list in the sorted order (sorted list of [item, value] ⇒ sorted list of item).

The use of anonymous arrays ensures that memory will be reclaimed by the Perl garbage collector immediately after the sorting is done.

Efficiency analysis<br>[edit]

Without the Schwartzian transform, the sorting in the example above would be written in Perl like this:

@sorted = sort { foo($a) cmp foo($b) } @unsorted;

While it is shorter to code, the naive approach here could be much less efficient if the key function (called foo in the example above) is expensive to compute. This is because the code inside the brackets is evaluated each time two elements need to be compared. An optimal comparison sort performs O(n log n) comparisons (where n is the length of the list), with 2 calls to foo every comparison, resulting in O(n log n) calls to foo. In comparison, using the Schwartzian transform, we only make 1 call to foo per...