Schwartzian Transform in python

By: Koothrapalli in Python Tutorials on 2012-04-07

The Schwartzian Transform is a technique for sorting a list of elements that is used to improve the efficiency of sorting when the comparison function is computationally expensive. It is named after Randal L. Schwartz, who first introduced the technique in Perl.

In Python, the Schwartzian Transform can be implemented using the sorted() function along with a key function that computes the expensive comparison once per element and caches the result. Here's an example:

# Example list of strings to sort by length
my_list = ['apple', 'banana', 'orange', 'kiwi']

# Use the Schwartzian Transform to sort the list by length
sorted_list = [x[0] for x in sorted([(item, len(item)) for item in my_list], key=lambda x: x[1])]

print(sorted_list)  # Output: ['kiwi', 'apple', 'banana', 'orange']

In this example, the list is sorted by length, which is a computationally expensive comparison. The Schwartzian Transform is used to avoid computing the length of each string multiple times during the sorting process.

The first argument to the sorted() function is a list of tuples, where each tuple contains an element from the original list and the result of the expensive comparison function (in this case, the length of the string). The key argument is a lambda function that extracts the comparison value from each tuple.

Finally, the sorted list is constructed by extracting the original elements from the sorted list of tuples using a list comprehension.

Previous
<< Multidimensional list (array) in python

Next
Delegation in python >>