3
\$\begingroup\$

Zeckendorf's theorem states that all positive integers crepresented uniquely as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers.

So like given the input 10, the outcome would be [8,2].

This is my working code that was for Reddit's dailyprogrammer challenge:

def fib_list(max_num):
    x=3     #starting at 3 because we have [1,1] in list already.
    list_of_fib = [1,1]
    while x < max_num:
        x = list_of_fib[-1] + list_of_fib[-2]
        list_of_fib.append(x)
    return list_of_fib

def find_num_smaller(num, my_list):
    for value in reversed(my_list):
        if value <= num:
            return value 

def solve(num):
    combo_list = []
    list_to_pick_from = fib_list(num)
    while num > 0:
        temp_value = find_num_smaller(num,list_to_pick_from)
        num -= temp_value
        combo_list.append(temp_value)
    print(combo_list)


solve(10)

Running it through timeit.timeit I get about 0.06917929102201015 seconds with the input of 1234. Medium size input of 123456789 yields about 0.22879931901115924 seconds and a large size input of 123456789123456789123456789 yields 1.3149479770218022 seconds. Is there anyway to speed it up? Or make it more acceptable at a "higher standard" (whatever this means, I guess some would call it 'Pythonic' but I'm not sure the correct term)? Maybe is there some better practice I can employ here.

I have thought of turning Solve() into a generator and just get all the combo values out, but I'm not sure if that's faster.

I know that if I were to run it multiple times, I would check if the input is within the already generated fib_list, and if it isn't I would generate a new one. But that's another question, I just want to see one input.

\$\endgroup\$
2
\$\begingroup\$

First some general review:

  1. You should use a if __name__ == "__main__": guard around the test run to allow importing of your code from another module.

  2. You should add docstrings to your functions to explain what they do. Docstrings are of the format:

def f(x, y):
    """Returns the sum of `x` and `y`"""
    return x + y

As you already mentioned, here is a way to use generators. This has two draw-backs compared to your code:

  1. In find_num_smaller we have to iterate forwards (you cannot iterate backwards through an iterator, at least not without converting it to a list first).

  2. We need to re-generate the generator every loop, because it will be partially exhausted

def fib(max_num):
    """
    Yields the fibonacci sequence until the last element smaller than `max_num`
    """
    n_1, n = 0, 1
    while n < max_num:
        yield n
        n_1, n = n, n + n_1


def find_num_smaller(num, my_list):
    """
    Iterates through an iterator until the value in the iterator is larger than `num`. 
    Returns the value before that.
    """
    last_value = next(my_list)
    for value in my_list:
        if value > num:
            return last_value
        last_value = value
    return last_value


def solve(num):
    """
    Description here
    """
    x = num
    while x > 0:
        temp_value = find_num_smaller(x, fib(num))
        x -= temp_value
        yield temp_value

if __name__ == "__main__":
    print list(solve(10))

Note that your fund_num_smaller will return None if all values in my_list are smaller than num. Here I added returning the last element in that case.

However, this actually performs worse than your code (mostly because iterating reversed saves a lot of time and re-doing the fibonacci sequence wastes a lot of cycles).

As an alternative consider this code:

def find_num_smaller(num, my_list):
    for value in reversed(my_list):
        if value <= num:
            return value


def solve(num):
    l = list(fib(num))
    while num > 0:
        temp_value = find_num_smaller(num, l)
        num -= temp_value
        yield temp_value

Where I used your find_num_smaller and put the fibonacci into a list.

Here is acomparison between the three approaches for the input 123456789123456789123456789123456789123456789123456789 on my machine:

no generator     406 function calls in 0.000 seconds
only generators  10111 function calls in 0.003 seconds
mixed            407 function calls in 0.000 seconds

So using generators here will not give you a speed improvement for most inputs. For the fibonacci numbers it will, however, give you a memory improvement (which will take quite some time to matter).

For really large inputs (like 123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789) there is no improvement visible:

no generator  2947 function calls in 0.017 seconds
mixed         2948 function calls in 0.017 seconds

And for the input 123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789:

no generator  5886 function calls in 0.063 seconds
mixed         5887 function calls in 0.064 seconds

So both approaches seem to scale with the number of digits of the input.

\$\endgroup\$
  • \$\begingroup\$ Generators are usually lazy evaluation so they scale way better. I'm not worry about memory because I don't expect someone to input max(int) value into it, Given that if that were to happen, Generators and your method would beat out mine by a long shot. Food for thoughts, but thanks for your feedback. \$\endgroup\$ – MooingRawr Oct 7 '16 at 15:41
  • \$\begingroup\$ @MooingRawr No, here it doesn't, apparently. The no generator in the timings is your code. Both seem to scale with the number of digits of the input (I tried twice the length of the number in the second timing and both timings just doubled). \$\endgroup\$ – Graipher Oct 7 '16 at 15:47
  • \$\begingroup\$ What helps here is that the fibonacci numbers grow really fast. \$\endgroup\$ – Graipher Oct 7 '16 at 15:48
  • \$\begingroup\$ right. I forgot to factor in that It's growth is rapid, interesting... Thanks for pointing that out. \$\endgroup\$ – MooingRawr Oct 7 '16 at 15:49
2
\$\begingroup\$

Let's continue from Graipher's code, sans documentation for brevity:

def fib(max_num):
    n_1, n = 0, 1
    while n < max_num:
        yield n
        n_1, n = n, n + n_1

def find_num_smaller(num, my_list):
    for value in reversed(my_list):
        if value <= num:
            return value

def solve(num):
    l = list(fib(num))
    while num > 0:
        temp_value = find_num_smaller(num, l)
        num -= temp_value
        yield temp_value

What's the slowest part here? solve consists of

l = list(fib(num))
while num > 0:
    temp_value = find_num_smaller(num, l)
    num -= temp_value
    yield temp_value

l = list(fib(num)) is slow, but only runs once. num -= temp_value and yield temp_value are relatively quick, and run once per iteration. find_num_smaller(num, l), however, can take a long time and runs once per iteration.

This is because we're doing Shlemiel the painter's algorithm:

Shlemiel gets a job as a street painter, painting the dotted lines down the middle of the road. On the first day he takes a can of paint out to the road and finishes 300 yards of the road. "That's pretty good!" says his boss, "you're a fast worker!" and pays him a kopeck.

The next day Shlemiel only gets 150 yards done. "Well, that's not nearly as good as yesterday, but you're still a fast worker. 150 yards is respectable," and pays him a kopeck.

The next day Shlemiel paints 30 yards of the road. "Only 30!" shouts his boss. "That's unacceptable! On the first day you did ten times that much work! What's going on?"

"I can't help it," says Shlemiel. "Every day I get farther and farther away from the paint can!"

There are some quick fixes. Firstly, we can try binary search. Python has a fast implementation in the bisect library. But even better is to "move" the paint can as we go along:

while my_list[-1] > num:
    my_list.pop()
return my_list[-1]

This can only do as many pops as there are elements in my_list, so all the calls added together can't be much slower than generating the list in the first place. The resulting code is much faster; for n = 10 ** 5000 it went from 2.6s to 0.026s, a 100x improvement.

There's also a bug! fib_list should be while x <= max_num; else solve(some_fibonacci_number) will include two consecutive numbers (eg. solve(5) → 3, 2 instead of 5).


There are some other minor style points:

temp_value, solve and my_list are terrible names, and fib_list and find_num_smaller are poor. Most variables are temporary, so temp_variable tells you nothing in a lot of space. solve could refer to solving any problem. my_list is silly - obviously it's "your" list and you don't even care if it's a list - you just want a sequence.

There are other improvements, too. Instead of fib giving a bounded iterator, produce an unbounded iterator and call take_while.

If find_num_smaller took a reversed iterator directly, it could be

def find_num_smaller(num, nums):
    for value in nums:
        if value <= num:
            return value

since iterators automatically "pop" read values. You can even inline this by iterating over a filter:

def solve(num):
    fibs = list(takewhile(lambda x: x <= num, gen_fibs()))
    next_fibs = (x for x in reversed(fibs) if x <= num)

    for next_fib in next_fibs:
        num -= next_fib
        yield next_fib

which then suggests inlining the loop:

def solve(num):
    fibs = list(takewhile(lambda x: x <= num, gen_fibs()))

    for fib in reversed(fibs):
        if fib <= num:
            num -= fib
            yield fib

Then one might wonder if you can run fibs in reverse, and avoid generating a list. Yes, you can:

while True:
    yield next
    prior, next = next - prior, prior

So all you need to do is skip forward and iterate backwards:

def gen_fibs_reverse(limit):
    prior, next = 0, 1

    while next <= limit:
        prior, next = next, next + prior

    while prior:
        yield prior
        prior, next = next - prior, prior

def zeckendorf_decomposition(num):
    fibs = gen_fibs_reverse(num)

    for fib in fibs:
        if fib <= num:
            num -= fib
            yield fib
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.