1.4 KiB
Runtime Analysis
List Results
foxsays_tleader_in_50k.txt
foxsays_tleader_in_200k.txt
Dict Results
foxsays_tleader_in_50k.txt
foxsays_tleader_in_200k.txt
Dict Performance Improvement
The biggest waste of run time in the dict version of the program was creating the list of animals encountered based on the sounds heard. Originally for each sound encountered I was checking if the animals_encountered list already contained the animal. This is a poor implementation because it meant that for every sound encountered we were perform an O(n) operation (the in operator on list). To fix this I changed animals_encountered to be a set instead of a list. This alone was enough to speed up the run time of the 200K sample from ~101 seconds to ~1.8s (see below). The one drawback of this is that sets (in theory) do not preserve insertion order, and so we lose the order in which the animals were encountered.
Dict Runtime Plot
Based on the runtimes (computed with time.perf_counter()), there appears to be a relatively linear runtime for the dictionary based program relative to its input size. This is likely because we only have to iterate through every input line once.