4
\$\begingroup\$

I'm doing a coding challenge for fun and to work on my skills - some of you may remember the Advent of Code challenge from last December, I'm working through that. I've got this code as the solution to one of the problems, which works, but it's uselessly slow.

inp = "1113122113"

def iterate(num):
    pos = 0
    new = ""
    while pos < len(num):
        counter = 0
        d = num[pos]
        for i in range(pos, len(num)):
            if num[i] == d:
                counter += 1
            else:
                break
        new+=str(counter)
        new+=str(d)
        pos += counter
    print len(new)
    return new

for i in range (50):
    inp = iterate(inp)

Past iteration 35 or so, it gets to the point where it's taking several minutes for each iteration. The objective is to generate a look-and-say sequence - so 1 goes to 11, then 21, 1211, 111221, 3112211 and so on. I need to find the length of the string after the 50th iteration, but it's 360154 characters long after 40 iterations and my code just isn't optimised enough to handle strings that long in a reasonable time. Can anyone give me some pointers?

\$\endgroup\$
  • 2
    \$\begingroup\$ Can you please explain in more detail what you want the code to do? I don't understand how you came up with the example output. \$\endgroup\$ – TheBlackCat Oct 6 '16 at 16:06
  • \$\begingroup\$ @TheBlackCat that is the look-and-say sequence \$\endgroup\$ – Copperfield Oct 6 '16 at 17:32
  • \$\begingroup\$ You should put the link in the question. \$\endgroup\$ – TheBlackCat Oct 6 '16 at 17:57
  • \$\begingroup\$ @TheBlackCat sure I can try to put in there, but is not my question... \$\endgroup\$ – Copperfield Oct 6 '16 at 18:02
3
\$\begingroup\$

So let's look at what the basic idea of the sequence is (if I understand correctly):

  1. Break the sequence into contiguous blocks of identical values.
  2. Figure out the lengths of those blocks.
  3. Create a new sequence with the length of each block followed by the value of that block.

Step 1 seems to be the problem here. The key issue is to me is that you are rolling your own solution when python provides something to do step 1 for you: itertools.groupby.

So consider your last number:

>>> from itertools import groupby
>>> inp = "1113122113"
>>> print([(k, list(g)) for k, g in groupby(inp)])
[('1', ['1', '1', '1']), ('3', ['3']), ('1', ['1']), ('2', ['2', '2']), ('1', ['1', '1']), ('3', ['3'])]

This gives you an iterator of tuples, where the first tuple is the value of the group and the second is the group itself. You can use the value of the group for second element of each number pair and length of the group as the first element. Then you just have to put them together into a new string.

So the algorithm can be reduced to:

new = ''.join(str(sum(1 for _ in g))+k for k, g in groupby(inp))

Other comments:

  1. Your multi-run is done in the root of the script. It would be better to give it its own function.
  2. You are printing in the same function that generates the sequence. This assumes you will always want to print. Better to just return the results and let whatever calls the function determine what to do with those results.
  3. You should put all the automatically-run code in if __name__ = '__main__': so you can use the functions elsewhere.
  4. You should use from __future__ import print_function to make your code python3 compatible.
  5. Use _ in place of i for loop indices you don't care about.
  6. You can use default function arguments to make the code a bit simpler to run

So here is my complete solution:

from __future__ import print_function


def iterate(num):
    return ''.join(str(sum(1 for _ in g))+k for k, g in groupby(num))


def multiiter(n, inp='1'):
    for _ in range(n):
        print(inp, len(inp))
        inp = iterate(inp)


if __name__ == '__main__':
    multiiter(n=50, inp='1113122113')

Using a version that commented out the print took 5.53 seconds to run 50 answers.

Edit: Included Copperfield's sum suggestion.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ instead of creating a unnecessary list to just know its size, you can get the same result with sum(1 for _ in g) \$\endgroup\$ – Copperfield Oct 6 '16 at 18:26
  • \$\begingroup\$ @Copperfield: Good idea, added. \$\endgroup\$ – TheBlackCat Oct 6 '16 at 18:33
  • \$\begingroup\$ Why is sum(1 for _ in g) better than len(g)? \$\endgroup\$ – Tam Coton Oct 7 '16 at 9:06
  • 1
    \$\begingroup\$ @TamCoton because g is a generator, and generator create values dynamically on the fly so you cannot know its length without iterating over it, also you can create generators of infinity size, therefore they don't implement len so you need an alternative way to get the same result \$\endgroup\$ – Copperfield Oct 7 '16 at 14:56
2
\$\begingroup\$

Do not create huge lists just to throw them away

In Python 2 (that you are using because of print without parenthesis), range generates a list. This list can be over 5 million (\$5 * 10 ^ 6\$) elements long (in the last iteration) and as soon as it is created it is discarded. This is very bad for performance.

Changing range to xrange that instead generates a list just as needed (and using ''.join just to be extra sure quadratic behaviour does not kick in) I got a 98% improvement in performance.

On PyPy it now takes 12.7 seconds to run 50 iterations.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Building an n-length string by concatenating strings of length 1 performs in O(n^2), hence the slowing down for large strings. Use lists of digits as your representation instead.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ stackoverflow.com/questions/4435169/… Not always. Interpreter optimization may make running time O(N). Anyhow I agree that you should not rely on that. \$\endgroup\$ – Caridorc Oct 6 '16 at 18:52
  • \$\begingroup\$ Wow, I did not realise how computationally expensive string concatenation was. Changing range to xrange sped it up a lot, but it was still unreasonably slow past iteration 45ish, then replacing the string concatenation with a list append and using join at the end of the while loop made another enormous boost to performance! Those two tweaks solved the problem by themselves! \$\endgroup\$ – Tam Coton Oct 7 '16 at 9:21
  • \$\begingroup\$ Good! I would be interested in performance measurements if you have them. \$\endgroup\$ – Valentin Waeselynck Oct 7 '16 at 9:34

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.