Exploring the execution of a Python LampSort algorithm
This tutorial shows how to analyse Python code using GT's PythonBridge. In particular, we'll look at a simple sorting algorithm and mold our tools to explain how the algorithm works.
Setup
First make sure GT's PythonBridge is up and running. Let's define a small list of random numbers.
import random numbers = random.sample(range(100), 10)
The indicator in the Python snippet above should show an active Python connection.
We can now copy our tutorial files into the PythonBridgeRuntime directory next to our GT image.
files := FileLocator gtResource / 'feenkcom' / 'gt4python' / 'data' / 'python' childrenMatching: 'lampsort*.py'. files do: [ :each | each copyTo: PBPlatform current workingDirectory / each basename ]. PBPlatform current workingDirectory
LampSort
Now we can open a view on the Python files inside into the PythonBridgeRuntime directory next to our GT image which now contains our tutorial files. Let's look at lampsort0.py which is our orginal version.
GtLSPPythonModel onDirectory: PBPlatform current workingDirectory
LampSort is an object that wraps a data list and sorts it in place. The LampSort algorithm is a non-recursive implementation of QuickSort.
It works by partitioning the list into intervals around a pivot, where the left interval contains elements smaller than the pivot and the right interval elements larger than the pivot. Intervals are partitioned further until they contain one element or are empty, in which case they are sorted by default.
The algorithm starts from a set containing one interval covering the whole list. It is done when this set is empty. Range objects are used to represent intervals.
Let's make sure our implementation works.
import lampsort0 result = lampsort0.LampSort(numbers.copy()).sort() assert result == sorted(numbers) result
Tracing
If you look carefully at the LampSort implementation you'll notice that there are method for each individual step, with a meaningful name and with relevant arguments (the data list of elements is never passed as an argument, it is an instance variable).
A very low cost way to analyse our code is by tracing it. We do this by adding a @gtTrace method annotation. The result can be seen in lampsort1.py. Open the view we used above and click the + at the top left to expand a directory view listing all files, clicking the - to go back.
To explain what is going on, we start by looking at the result. We run our second version, with annotated methods.
import lampsort1 from gtoolkit_bridge import reset_signals, get_signals reset_signals() result = lampsort1.LampSort(numbers.copy()).sort() assert result == sorted(numbers) get_signals()
The result of get_signals() is a TelemetrySignalGroup which is a wrapper around a list of TelemetrySignals. In the case of @gtTrace each method produces two signals: an ArgumentMethodStartSignal and a ResultMethodEndSignal. Matching start and end signals get combined into TelemetryEvents.
The tracing does not produce text output somewhere, it produces a collection of signals that get interpreted as events. The signals/events contain automatically derived information: the name of the method, the argument names mapped to argument values and the method result. Timing information is also included.
Analysis
A number of custom views on TelemetrySignalGroup now show us what is going on with our algorithm. The Signals view/tab lists all collected signals, basically the wrapped data.
Looking at an individual signal there is a call view/tab that show the the argument names mapped to argument values and/or the method result.
The Tree view/tab allows you to see the call structure: the substeps belonging to each step (you can click the tree open with the triangle).
Note that the elements of the tree are events, they combine a start and stop signal. The call view/tab now shows both the argument names mapped to argument values and the method result.
By keeping a tree open with call details as a linked view, you can now move through each step the algorithm takes.
The Map view/tab is a more graphical representation of the events/steps. You can now see the decomposition of higher level step into substeps. Each box contains the method/step name and is clickable to inspect details.
Signals
We can also add simple signals inside our code for additional instrumentation. We create yet another variant, lampsort2.py where we add four information signals to the partition method. We want to see how the decision for each element with respect to the pivot is made. Furthermore we mark how the pivot is first stashed away to the end and then restored.
import lampsort2 from gtoolkit_bridge import reset_signals, get_signals reset_signals() result = lampsort2.LampSort(numbers.copy()).sort() assert result == sorted(numbers) get_signals()
When we change code in a Python source file that we already loaded in our running PythonBridge instance, we need to reload it using importlib.
import importlib importlib.reload(lampsort2)
Combining the simple information signal with our more sophisticated trace signals helps to explain why each swap is being made when we look at the Tree view/tab.
Molding
Up to now we used predefined signals and event. The last signal that we added contained only an identifying message string. We can do better by adding our own custom signal with a custom view.
In lampsort3.py we define a PivotComparisonSignal subclass of TelemetrySignal to hold two properties. Then we define a view to show these properties.
import lampsort3 from gtoolkit_bridge import reset_signals, get_signals reset_signals() result = lampsort3.LampSort(numbers.copy()).sort() assert result == sorted(numbers) get_signals()
References
LampSort, a non-recursive QuickSort implementation and LampSort Revisited, Visualised (Combining Object Logging & Agile Visualisation)
Equivalent code in GT: GtLampSort
and GtLampSortWithAnnouncements
with examples.