When you write code it is important that it works
correctly.. It is also important that it runs efficiently. This is what
separates beginner programmers from developers.
Many developers only focus on getting the output.. Companies
also care about how fast the code runs how much memory it uses, whether it can
handle a lot of data and how efficient the code is.
In this coding challenge you will look at a Python script
that seems to work but has a major performance issue. Your goal is to find the
problem make the code run faster and explain how you did it.
This type of challenge is often used in coding interviews
and technical assessments to test your skills.
---
. The Challenge
Lets look at the following Python script:
```python
numbers = list(range(100000))
duplicates = []
for num in numbers:
if num not in duplicates:
duplicates.append(num)
print(len(duplicates))
```
The output of this script is correct. It prints:
```text
100000
```
But the script becomes very slow when the dataset is large.
Can you figure out why this happens?
---
. Understanding the Problem
At glance the code looks fine. Lets break it down step by
step.
... Step 1
The script creates a list of numbers from 0 to 99,999:
```python
numbers = list(range(100000))
```
This list contains all the numbers from 0 to 99,999.
---
... Step 2
The script checks if each number is already in the
duplicates list:
```python
if num not in duplicates:
```
This is where the problem lies.
---
. Why Is It Slow?
When you check if an item is in a list in Python it has to
look through the list one item at a time. This is called a search.
For example if you check if the number 99,999 is in the
duplicates list:
```python
if 99999 in duplicates:
```
Python has to look through the list like this:
```text
Index 1
Index 2
Index 3
...
```
until it finds the number. This process takes a time
especially when the list is large.
The time it takes to do this is called the time complexity.
For this type of search it is:
```text
O(n)
```
Since the script does this for every number in the list the
overall time complexity becomes:
```text
O(n²)
```
which is very inefficient for large datasets.
---
. Visualizing the Problem
Imagine you have a list with 10 elements. The script will
run quickly.
Now imagine you have a list with 1,000,000 elements. The
script has to search through the list times and this takes a long time.
As the list gets bigger the execution time grows
dramatically.
---
. The Optimized Solution
of using a list to keep track of unique numbers you can use
a set. Sets are much faster for this type of operation because they use a hash
table internally.
Here is the optimized code:
```python
numbers = list(range(100000))
unique_numbers = set()
for num in numbers:
print(len(unique_numbers))
```
This code gives the same result but it runs much faster.
---
. Why Sets Are Faster
A set uses a hash table to store its elements. When you add
an element to a set Python calculates a hash value. Uses it to determine where
to store the element.
This makes it very fast to check if an element is in the set
with an average time complexity of:
```text
O(1)
```
which is much faster than the search used for lists.
---
. Performance Comparison
... List-Based Approach
The time complexity of the script is:
```text
O(n²)
```
which becomes very slow for large datasets.
---
... Set-Based Approach
The time complexity of the optimized script is:
```text
O(n)
```
which's much more scalable.
---
. Benchmarking the Difference
Lets compare the execution times of the two scripts.
... List Version
```python
import time
start = time.time()
numbers = list(range(100000))
duplicates = []
for num in numbers:
if num not in duplicates:
duplicates.append(num)
end = time.time()
print(end. Start)
```
---
... Set Version
```python
import time
start = time.time()
numbers = list(range(100000))
unique_numbers = set()
for num in numbers:
unique_numbers.add(num)
end = time.time()
print(end. Start)
```
Most systems will show a speed improvement, sometimes more
than:
```text
100x Faster
```
depending on the size of the dataset.
---
. Common Beginner Mistakes
.. Using Lists for Everything
Lists are very versatile. They are not always the most
efficient data structure.
You should choose the data structure for the job.
---
.. Ignoring Time Complexity
Developers should understand the types of time complexity
such as:
* O(1)
* O(log n)
* O(n)
* O(n²)
Interviewers often ask about algorithm complexity.
---
.. Not Testing with Large Data
Code that works fine with a small dataset may fail with a
dataset.
You should always test your code with datasets to ensure it
scales well.
---
. Another Hidden Bottleneck Example
Consider the following code:
```python
result = ""
for i in range(10000):
result += str(i)
```
This code creates a string in each iteration, which is
inefficient.
A better solution is to use a list to store the strings and
then join them together:
```python
result = []
for i in range(10000):
result.append(str(i))
final = "".join(result)
```
This uses memory efficiently.
---
. Real-World Importance
Performance optimization is crucial in areas, such as:
... Web Applications
Faster page loads improve user experience.
... APIs
Lower response times improve performance.
... Data Analysis
Quicker processing times enable insights.
... Machine Learning
Reduced training times enable faster model development.
... Enterprise Software
Better scalability enables users and data.
Even small improvements can save computing resources.
---
. Interview Perspective
A common interview question is:
> Why would you use a set of a list?
A strong answer would include:
* Faster lookup times
* Better performance
* Reduced complexity
* Ideal for values
Understanding data structures is often more important than
memorizing syntax.
---
. Quick Optimization Checklist
Before deploying your code ask yourself:
✔ Can a set replace a list?
✔ Is there unnecessary looping?
✔ Can a dictionary improve
lookups?
✔ Are repeated calculations
being performed?
✔ Is memory usage reasonable?
Following this checklist can significantly improve your
codes quality.
---
. Challenge Extension
Can you optimize the following script?
```python
numbers = [1,2,3,4,5]
for i in range(len(numbers)):
for j in range(len(numbers)):
print(numbers[i] numbers[j])
```
Questions:
1. What is the time complexity of this script?
2. Can the nested loop be avoided?
3. How would the performance change with one million
numbers?
Share your answer in the comments.
---
. Key Takeaways
This challenge demonstrates a lesson:
Correct code is not always efficient code.
Professional developers constantly evaluate their codes:
* Speed
* Memory usage
* Scalability
* Data structures
Understanding these concepts will improve your coding skills
help you ace interviews and enable you to develop efficient real-world
projects.
The best developers do not just solve problems. They solve
them efficiently.
---
.. Interactive Coding Challenge
Can you improve the script even further?
Post your optimized solution in the comments. Explain:
* What changes you made
* Why your solution is faster
* What complexity improvement you achieved
The best answer will be featured in our coding challenge.
---
.. Learn Python and Software Development, at KodVidya
Academy
Want to master Python data structures, algorithms, backend
development and technical interview preparation?
Join KodVidya Academys hands-on training programs. Work on
real-world coding projects designed to make you placement-ready.
No comments:
Post a Comment