|
It seems to me that the different versions of find_element(p,t) from unit 3.26 and 3.27 can have very different execution times when working with big lists, one can take as much as 10 times longer than other. I'm not sure why this is so, perhaps someone can enlight me. For example, if we make a really big list and call for the last element of it The function defined as takes (in my machine) about 7.6 seconds to run while the function takes only 0.77 seconds to run. By the way, I meassure this time with I've never programmed in Python but I know a little Common Lisp (and people like to use A LOT of lists there). Perhaps the problem is because in the first case we traverse the list too many times? Does the call p[i] makes Python traverse the list up to the ith element each time? (Lisp would do that). In the second example we traverse (I suspect) the list only 2 times: once with the t in p statement and the other with the p.index(t) statement. Is there a clever way to traverse the list only one? I'd like to know. ... or perhaps the whole problem is that I am timing wrong the execution times. |
The question has been closed for the following reason "The question is answered, right answer was accepted" by Andres Garcia Saravia Ortiz M. 13 Mar '12, 17:23
|
It looks interesting. In the first function, you are going through elements one by one, searching for the right value, which is O(n). In the second one, you are using Note: List in Python is implemented internally as a continuous array of elements, which gives the above mentioned complexities. Resource for those information can be found here. My best guess in order to explain your numbers would be that both functions are of the same complexity (the second one has only twice as big constant). But the first function is implemented in Python itself (is interpreted), while the second one is calling Python's built-in functions, which are implemented in C (?) and thus it is much faster than the first one. Another, even wilder guess would be that you are doing the same operation (walking through the list until the same element) twice in very close succession and some optimization would do its thing. However, I does not look as a good explanation to me, because your times are way too different in order to base explanation just on this. Yet it is the only one I can think of. Would you run it with large lists of different sizes? Anyone any ideas? Your answer misses the mark, except for the part about interpretation vs. built-in functions. Andres asked why one implementation ran slower than the other. He did not ask about the growth orders. Yes, they are both O(n), but so what? The speeds differ by a factor of 10 because of coding choices that Andres made, and because of the interpreter implementation that underlies those choices. That is the level at which an answer is needed. Interesting comment, but as list are implemented with arrays in Python maybe the built-in functions could use some other search method than linear search. |
|
The integer addition in the while loop is not a machine code level "add operation". |
You're right about traversing the list twice. In the first example, in each iteration you have to increment i, test whether it is less than len(p) - which means calculating len(p) each time, and then look up the number at position i. I believe Python lists were taken from LISP, so each cell contains an element plus a pointer to the next element, so they can be traversed easily.
@ Peter yes, that's what I thought. however I recently found this text by Peter Norvig and it says Lisp lists are different from Python lists: "Lists are not Conses. Python lists are actually like adjustable arrays in Lisp or Vectors in Java. That means that list access is O(1)[...]". If this were Lisp indeed you would traverse the list twice, but it seems Python handles lists in a different way.
Hmmm interesting. I had always thought them the same.