问题描述:

Is it possible that Dictionaries are slower than Brute Force in this problem?

  • PROBLEM (from Project-Euler):

    The following iterative sequence is defined for the set of positive integers:

    n → n/2 (n is even)

    n → 3n + 1 (n is odd)

    Using the rule above and starting with 13, we generate the following sequence:

    13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

    It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

    Which starting number, under one million, produces the longest chain?

    Note: Once the chain starts the terms are allowed to go above one million.

  • CODE [Brute Force]:

    I started with a brute force program that takes every number from 1 to 1000000 and print the longest chain found.

    It take about 30 second to finish.

    # number from 1 to 1000000

    num = 0

    # longest chain here

    maxLength = 0

    # number that produce the longest chain

    result = 0

    while num < 1000000:

    num += 1

    k = num

    # count the current chain pieces

    i = 0

    while k > 1:

    i += 1

    if k%2 == 0:

    k /= 2

    else:

    k = k*3 + 1

    if maxLength < i:

    maxLength = i

    result = num

    print result

    Then I said: "It's too much time! Let's implement dictionaries!"

  • CODE [Dictionaries]:

    With Dictionaries, every time a chain end, the starting number of the chain and the chain pieces number are stored in a Dictionary, so when it found the same number more than one times, it can use the value associated with this number stored in the dictionary.

    After 5 minutes I stopped it.

    # number from 1 to 1000000

    num = 0

    # longest chain here

    maxLength = 0

    # number that produce the longest chain

    result = 0

    dictionary = {}

    while num < 1000000:

    num += 1

    k = num

    i = 0

    while k > 1:

    # if it processed the number before, it use the shortcut

    if str(k) in dictionary.keys():

    i += dictionary[str(k)]

    break

    i += 1

    if k%2 == 0:

    k /= 2

    else:

    k = k*3 + 1

    # add new shortcut

    if not (str(num) in dictionary.keys()):

    dictionary[str(num)] = i

    if maxLength < i:

    maxLength = i

    result = num

    print result

Is it possible that dictionary affect the performance of this program, making it really slow? Aren't they used to improve performance and speed up programs? or... is my code buggy?

Thanks!

网友答案:

this

if str(k) in dictionary.keys():
#                      ^^^^^

is bad. This turns the set of keys into a list! and scans that lineraly (in python3, it's a generator, but nearly as bad).

You can say.

if str(k) in dictionary:

and that does the right thing, in O(1) instead of O(n)!

Additionally, it's unneccesary in python to convert things to string to use them as keys in dict's. Numbers are just fine, so you can really say: k everywhere you're currently saying str(k).

相关阅读:
Top