Quote:
Originally Posted by daveT
The two profs in this course are Lisp/Scheme programmers. This isn't supposed to be a 'how to program Python course,' but a 'how to program' course and this course is pretty list/tuple heavy. I guess that this is an okay way to present data, but I agree that this is likely overkill when working with the data. However, I was beginning to believe that list/tuple/dictionary comprehensions was the strong point of Python.
It is a strong point, but you wouldn't use a hammer to cut a piece of wood in half.
Quote:
Originally Posted by daveT
The profs were talking about how Lisp deals with pointers and list comprehensions and what happens when there are lists inside of lists, and then what happens if values have variable length, and my mind about exploded. Python simplifies all of this.
Yes, they love nesting things. The first class I had to take in grad school was all about programming fundamentals and was taught in Scheme. Towards the end of the class, they introduced us to what is called and S-Expression<T> (The <T> means that the data structure is generic and T is some data type, but the structure works the same for all types T).
Quote:
An S-Expression<T> is either a value of type T or a list of S-Expressions<T>.
The following are all valid S-Expressions of ints.
Code:
1
(2 3)
(1 (2 3) 4)
(1 (2 3) (4 (5 6)))
From a theory perspective, it is quite beautiful. A one sentence definition that only allows for two options. But the fact that the data structure is recursive allows you to essentially create any representation you want for your data. The problem is that it is a huge pain to actually work with something like that. The data structure does not provide any help, you just have to know the underlying layout. Scheme really likes lists and recursion (lists are recursive too), but in my opinion, it is used even when it is not the best tool for the job.
Quote:
Originally Posted by daveT
Right now, they are talking about memoization, which, as far as I can tell, is just a dictionary of values.
At the core, yes, that is how it is done. But the point of memoization is why it is done and when. The goal of memoization is to not calculate the same value twice. Think about it like this:
[php]def fib(int n):
if (n>1):
return fib(n-1) + fib(n-2)
return n
[/php]
I found the 1000th Fibonacci number and it took me a minute to calculate.
If I want to find the 2000th number, it will take me at least a minute because you have to have calculate all the numbers before it. Even more basic, calling fib(1000) twice in succession would take 2 minutes. But I already know the 1000th number, so I really don't need to recalculate it.
[php]
memo = {}
def fib(int n):
if (n in memo):
return memo[n]
if (n>1):
result = fib(n-1) + fib(n-2)
memo[n] = result
return result
return n
[/php]
The function is only slightly more complicated (3 extra lines) and has the advantage of returning faster the more often you use it. The first call to fib(1000) still takes a minute (actually a little longer). But if you call fib(1000) again, it is just a hash-table look up to get the answer. The downsides are that the initial call will take longer because of the extra work and you use lots of memory. For now, you are just learning the method, so it doesn't matter. When you get to a point where you will actually use it, you will have to decide what is the best balance between recalculating values and storing old values in memory.