Optimizing Running Time Analysis for Efficient Code Performance
Dive into benchmarking and analyzing running times for data structures, exploring methodologies for diagnosing slow code and categorizing code performance based on primitive operations. Discover best practices for efficient code execution.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
All Data Structures (time to add n elements) 600000000 500000000 400000000 ArrayList 300000000 LinkedList IntTree IntSearchTree 200000000 100000000 0 1000 1200 1400 1600 1800 2000 2200 2400 2600 2800 3000 3200 3400 3600 3800 4000 4200 4400 4600 4800 5000 5200 5400 5600 5800 6000 6200 6400 6600 6800 7000 7200 7400 7600 7800 8000 8200 8400 8600 8800 9000 9200 9400 9600 9800 0 200 400 600 800 10000 n
ArrayList, LinkedList and IntSearchTree (time to add n elements) 50000000 45000000 40000000 35000000 30000000 25000000 ArrayList LinkedList 20000000 IntSearchTree 15000000 10000000 5000000 0 1000 1200 1400 1600 1800 2000 2200 2400 2600 2800 3000 3200 3400 3600 3800 4000 4200 4400 4600 4800 5000 5200 5400 5600 5800 6000 6200 6400 6600 6800 7000 7200 7400 7600 7800 8000 8200 8400 8600 8800 9000 9200 9400 9600 9800 0 200 400 600 800 10000 n
ArrayList IntSearchTree (time to add n elements) 700000 600000 500000 400000 ArrayList 300000 IntSearchTree 200000 100000 0 1000 1200 1400 1600 1800 2000 2200 2400 2600 2800 3000 3200 3400 3600 3800 4000 4200 4400 4600 4800 5000 5200 5400 5600 5800 6000 6200 6400 6600 6800 7000 7200 7400 7600 7800 8000 8200 8400 8600 8800 9000 9200 9400 9600 9800 0 200 400 600 800 10000 n
Benchmarking Running a program to see how long it takes Downsides: Tests only one specific scenario Ignores time spent programming We need to wait for our results variable, depends on the machine It might change if I run it tomorrow I have to implement the code first Diagnose where our code is slow
Running Time Analysis Count the number of primitive operations the code will do Adding, multiplying, indexing into an array, assigning a variable Expressed in terms of the size of the input (typically called ?) Count using that worst case scenario Put that count into a bucket to categorize its running time To find bucket: ignore all constant coefficients, ignore all terms except the biggest one containing ? Examples of buckets: ?(1) : constant ?(?) : linear ? ?2: quadratic
Benchmarking Running a program to see how long it takes Downsides: Different computers will take different times The same computer might take different amounts of time Waste of time to do the experimentation Networking issues Error with starting/stopingthe stopwatch Depends on the PL I have to implement it first Code takes different amounts of time for different inputs
