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 1000000num = 0# longest chain heremaxLength = 0# number that produce the longest chainresult = 0while num < 1000000:num += 1k = num# count the current chain piecesi = 0while k > 1:i += 1if k%2 == 0:k /= 2else:k = k*3 + 1if maxLength < i:maxLength = iresult = numprint 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 1000000num = 0# longest chain heremaxLength = 0# number that produce the longest chainresult = 0dictionary = {}while num < 1000000:num += 1k = numi = 0while k > 1:# if it processed the number before, it use the shortcutif str(k) in dictionary.keys():i += dictionary[str(k)]breaki += 1if k%2 == 0:k /= 2else:k = k*3 + 1# add new shortcutif not (str(num) in dictionary.keys()):dictionary[str(num)] = iif maxLength < i:maxLength = iresult = numprint 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