Lists:
In Python lists act as dynamic arrays and support a number of common operations through methods called on them. The two most common operations performed on a list are indexing and assigning to an index position. These operations are both designed to be run in constant time, O(1).
Let's imagine you wanted to test different methods to construct a list that is [0,1,2...10000]. Let go ahead and compare various methods, such as appending to the end of a list, concatenating a list, or using tools such as casting and list comprehension.
For example:
def method1():
l = []
for n in range(10000):
l = l + [n]
def method2():
l = []
for n in range(10000):
l.append(n)
def method3():
l = [n for n in range(10000)]
def method4():
l = range(10000) # Python 3: list(range(10000))
> %timeit method1()
%timeit method2()
%timeit method3()
%timeit method4()
1 loop, best of 3: 197 ms per loop
1000 loops, best of 3: 771 µs per loop
1000 loops, best of 3: 407 µs per loop
The slowest run took 7.05 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 308 ns per loop
We can clearly see that the most effective method is the built-in range() function in Python!
It is important to keep these factors in mind when writing efficient code. More importantly begin thinking about how we are able to index with O(1). We will discuss this in more detail when we cover arrays general. For now, take a look at the table below for an overview of Big-O efficiencies.
Dictionaries:
Something that is pretty amazing is that getting and setting items in a dictionary are O(1)! Hash tables are designed with efficiency in mind, and we will explore them in much more detail later on in the course as one of the most important data structures to undestand. In the meantime, refer to the table below for Big-O efficiencies of common dictionary operations:
No comments:
Post a Comment