Schwartzian Transform - Efficiency Analysis

Efficiency Analysis

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 needs 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 element, at the beginning map stage, for a total of n calls to foo.

However, if the function foo is relatively simple, then the extra overhead of the Schwartzian transform may be unwarranted.

Read more about this topic:  Schwartzian Transform

Famous quotes containing the words efficiency and/or analysis:

    I’ll take fifty percent efficiency to get one hundred percent loyalty.
    Samuel Goldwyn (1882–1974)

    Whatever else American thinkers do, they psychologize, often brilliantly. The trouble is that psychology only takes us so far. The new interest in families has its merits, but it will have done us all a disservice if it turns us away from public issues to private matters. A vision of things that has no room for the inner life is bankrupt, but a psychology without social analysis or politics is both powerless and very lonely.
    Joseph Featherstone (20th century)