As our programs become larger, more complex, and deal with more data, efficiency increasingly becomes an issue. For some students this has already caused problems, where inefficient solutions time out when running in Gradescope. If such a thing were to happen to you, how might you go about figuring out where exactly in your program you need to fix your code? This week's lab provides some tools to help with this, namely the gprof profiler and the ability to insert timers into your code to show exactly how long it takes for sections of code to run.
Note: Tuesday is a holiday, so Tuesday students must do the lab on their own, unless you can find a person to do it with you, from your usual lab group. This means Tuesday students still do the outline, and still edit slides to create their lab contents, but do not take a quiz and do not fill out the peer reflection form. Tuesday students will be given the class average for their quiz and peer reflection form scores. Tuesday students should finish their lab work by Thursday at noon.
gprof is a profiler that helps you see how much time is spent in each section of your program. Bottlenecks can be identified and made more efficient.
Go through the steps on the Resources / gprof page. Apply this to the Lab 12 Sorting Algorithms Comparison program in Replit to identify bottlenecks.
Modify the Lab 12 Sorting Algorithms Comparison program in Replit so that it exits after a predetermined number of executions through the main loop in main(). Choose two different sorting algorithms and analyze them using gprof. Identify the bottleneck, and give an intuitive explanation why that is the bottleneck, submitting this for your lab preparation outline.
Submit your code into the Reading Outline Submission Form that we've been using each week, by copy / pasting it into the form question that asks for 250 words minimum, entitled "What are the main points to this topic?"
Post your outlines on your partner group's slides. Use them to help you describe one of the bottlenecks you found in one of the sorting program, explaining how you used gprof to find it. Include appropriate screen shots to make the process clear.
Array vs. Linked List
We have seen examples of implementing a dynamic array, as well as doing the same thing using a linked list instead. Which of these two approaches is faster at adding random numbers in order, and then deleting random numbers? Our intuition tells us that using a linked list should be faster, since everytime we add a new number we don't need to shift all the other values after it to make room. How much faster is it, if indeed it is faster? This is the question you will attempt to answer.
Modify the Replit Lab 12 Array vs Linked List program to use time of day to keep track of and display elapsed time. You only need to add code in functions useArray(...) and useLinkedList(...) to record the start time and compute the elapsed time, which gets returned. Use Lab 12 Sorting Algorithms Comparison program in Replit for an example of how to use time. Time permitting, create a graph of your results.
In case you are accessing this page without access to Replit, see the links below for the two programs used: