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:
““Never hug and kiss your children! Mother love may make your children’s infancy unhappy and prevent them from pursuing a career or getting married!” That’s total hogwash, of course. But it shows on extreme example of what state-of-the-art “scientific” parenting was supposed to be in early twentieth-century America. After all, that was the heyday of efficiency experts, time-and-motion studies, and the like.”
—Lawrence Kutner (20th century)
“Ask anyone committed to Marxist analysis how many angels on the head of a pin, and you will be asked in return to never mind the angels, tell me who controls the production of pins.”
—Joan Didion (b. 1934)