Cheers,
Abacus
]]>It's quite fun if you like programming
]]>as one says: "if we exchange two objects, we have one object each, if we exchange two ideas, we have two ideas each".
back on topic, anyone on the prime number task?
]]>Complexity is (just as functional programming) something which is more or less ignored at my university. Unfortunately.
]]>here I am not considering a variable number of months at all.
I am also considering the static case, not the one where I compute the whole array.
also, I consider the time cost source as being addition/substraction operations.
now, the input to the program is any number in range 1-365.
for any value of the input, the number of calculations done in my algorithm is exactly zero (d) or one (d - t_list[i-1])
for any value of the input, the number of calculations done in wuischke algorithm is at most 12 (day - months[month]). I ignore the simple month++ increment.
now the important part is that we consider the function being called a high number of times in a row, with purely random choice among 1-365 as input. given that the repartition of days in months is almost even (~30), the mean number of calculations done in wuischke algorithm will be 6, while for me it is constant and equal to 1, thus my 1:6 ratio.
the reason why I take only additions into account is that I generalized the algorithms in something like:
for i in range(0,len(list)):
if d < list[i]:
f(d,i)
break
vs
while d < list[i]:
d = f(d, i)
i++
f being the costy calculation. this is why one can't count instructions, and how one would evaluate the generic performance of a given algorithm.
of course this is offseted here because f is trivial and consists of a mere substraction. also a compiler may be able to optimise this greatly.
as a simple empirical confirmation, I wrote those two snippets (with cost() aggravating the algorithmical cost unit):
date1.py
from random import *
t_list = [ 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365 ]
def cost():
z=0
for i in range(1, 1000):
z=z+1
for i in range(1, 10000):
d = randint(1, 365)
for i in range(0,len(t_list)):
if d < t_list[0]:
d
cost()
break
elif d <= t_list[i]:
d - t_list[i-1]
cost()
break
date2.py
from random import *
n_list = [ 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 ]
def cost():
z=0
for i in range(1, 1000):
z=z+1
for i in range(1, 10000):
d = randint(1, 365)
i=0
k=d
while n_list[i] < k:
k = k - n_list[i]
cost()
i = i+1
and I ran a number of times:
time python date1.py ; time python date2.py
which gives me 0m1.450s vs 0m7.483s, that's a ratio of ~5.
the funniest part being that if you comment out the calls to cost(), the faster one is wuischke's (1.923/1.682 = 1.14). I can only suppose some compilation optimisation takes place, or I'm using some costy python feature...
]]>Whatever it means, I was in an engineering physics degree for two years and some weeks. I agree with your definition of elegance. That's how I consider math stuff elegant. I don't know enough computer science to consider it math yet!
Engineering Physics Bit dry for my tastes, too much calculus lol, but certainly mathematics! As for computer science, well its not so much that it's pure maths, but the use and design of algorithms has it's roots in mathematics. If you can think logically and clearly, which most mathematicians are trained to do, then you will be better at the computer side of things.
]]>As an aside, do you have any formal training in mathematics or physics, or is it just a hobby?
Whatever it means, I was in an engineering physics degree for two years and some weeks. I agree with your definition of elegance. That's how I consider math stuff elegant. I don't know enough computer science to consider it math yet!
]]>If you increase the number of months, then his array generation loop will increase too...
In something such as you have here, there is no array generation loop, it is a fixed cost when writing the code. If you assume a normal year, and don't account for leap years (which is what I would have done as this program is an exercise in algorithm design rather than a practical exercise) then his will always be faster than yours, although you are correct in saying that yours is 3/2 times slower.
Taking it to the extreme that I took it, you would have the array permanently stored within the program code, so the function could in theory be 36 times faster than yours, however in practice would average out at 18 times quicker.
Here's a simple programming exercise for you it should take no longer than 10 minutes to solve. Write an algorithm to continuously generate prime numbers, until aborted by a keypress.
]]>shining: I have 3 instructions per month, while he has two per month. When we use a high number of months (by either increasing the number of months of the year or executing the code many times), all one-time differences can be ignored, resulting in a ratio of 3/2 -> 1.5.
If you increase the number of months, then his array generation loop will increase too...
The only difference between your version and lloeki one is that he splitted the loop in two.
And the only advantage of doing that is that you can do the initialization once, and then use that array several times.
For example, the code could be simply edited to be run into a loop, asking the user to enter a value as many times as he wants.
Otherwise, if you really care about the complexity of algorithm with higher values (which is not possible in this problem), then doing a linear search sounds really funny.
Even more when you notice that the "cumulative array" is already sorted.
Edit: P.S. See http://bbs.archlinux.org/viewtopic.php?id=44730
]]>lloeki: I'm more or less familiar with complexity and I can see your point, although 6 times is wrong, if I'm not mistaken. (For the worst case I have 12 * 2 instructions + 12 * 1 comparision = 36; you have 12 * 1 instruction + 12 * 1 comparision + 1 instruction (you have to do one substraction, too) = 25 -> my code is up to 1.44 times slower and if you substract the calculations necessary to generate your array, mine needs even less instructions. For higher numbers, your code will be ~1.5 times better, though)
For higher numbers of what? Executions?
If yes, we might finally be on the same line
I think I'll open a little "programming challenges" thread later. I'll think about an interesting problem you can solve within less than an hour, but which still is not too trivial. The demand seems to exist and it's fun.
lloeki: I'm more or less familiar with complexity and I can see your point, although 6 times is wrong, if I'm not mistaken. (For the worst case I have 12 * 2 instructions + 12 * 1 comparision = 36; you have 12 * 1 instruction + 12 * 1 comparision + 1 instruction (you have to do one substraction, too) = 25 -> my code is up to 1.44 times slower and if you substract the calculations necessary to generate your array, mine needs even less instructions. For higher numbers, your code will be ~1.5 times better, though)
But I would happily trade in such a relatively small speed difference for smaller and easier to understand code. That's why I'm currently learning Haskell. I've written (and sometimes I still write) some very bad code in this regard...speed is not everything.
]]>Just to illustrate that for wuischke, or anyone else
I didn't show the code for people to ponder on it oh well.
Oooh, sorry matey Didn't realise that was why you left it out.... i'll edit the post and hope nobody else read it lol
...but, but, writing [31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365] takes more developer time! I try to go by the maxim "early optimization is the root of all evil".
that's why I first went as far as generating days_of_month, from the very rules we all use to actually generate it 'by hand'.
I'm a beginner in python so there may be some more pythonic way to do things.
Thats pretty much how i was thinking of getting the initial array, however I wasn't thinking in python, which is a language I have never used (But certainly one I keep meaning to learn). I would probably have written it in basic to be honest. Either that or C.
]]>