5
\$\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\$
4
  • 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\$ Commented Oct 6, 2016 at 16:06
  • \$\begingroup\$ @TheBlackCat that is the look-and-say sequence \$\endgroup\$ Commented Oct 6, 2016 at 17:32
  • \$\begingroup\$ You should put the link in the question. \$\endgroup\$ Commented Oct 6, 2016 at 17:57
  • \$\begingroup\$ @TheBlackCat sure I can try to put in there, but is not my question... \$\endgroup\$ Commented Oct 6, 2016 at 18:02

4 Answers 4

5
\$\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.

\$\endgroup\$
4
  • 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\$ Commented Oct 6, 2016 at 18:26
  • \$\begingroup\$ @Copperfield: Good idea, added. \$\endgroup\$ Commented Oct 6, 2016 at 18:33
  • \$\begingroup\$ Why is sum(1 for _ in g) better than len(g)? \$\endgroup\$
    – Tam Coton
    Commented Oct 7, 2016 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\$ Commented Oct 7, 2016 at 14:56
4
\$\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.

\$\endgroup\$
3
\$\begingroup\$

An observation and a fast solution.

You start with "1113122113". You build further sequences by identifying the streaks of consecutive equal digits and encode them as count+digit pairs.

You will never have a streak of more than three consecutive equal digits and will thus never have a digit larger than 3. Why? If you did, even just four consecutive equal digits, then two of them would be digit values. And they'd be the same. So they would've come from two consecutive streaks of the same digit. But that would be one streak.

So you only have very short streaks and Caridorc was completely right, your long range lists were hugely wasteful. Note they wouldn't have been that wasteful if you had very few but very long streaks, but we now know that the opposite is the case.

Now let's take advantage of this very limited set of possible streaks:

def iterate(num):
    return (
        num
        .replace('111', 'a')
        .replace('222', 'b')
        .replace('333', 'c')
        .replace('11', 'd')
        .replace('22', 'e')
        .replace('33', 'f')
        .replace('1', '11')
        .replace('2', '12')
        .replace('3', '13')
        .replace('a', '31')
        .replace('b', '32')
        .replace('c', '33')
        .replace('d', '21')
        .replace('e', '22')
        .replace('f', '23')
    )

For example the streak 111 will become 31, so we want to do num.replace('111', '31'). We can't do that directly because the different replacings would incorrectly affect later ones. So we temporarily replace them with letters until we're safe enough to replace with digits.

Runtimes along with your original and TheBlackCat's groupby solution, three attempts each (also showing the final sequence length as correctness check):

len(inp)=5103798  13.29  13.32  13.43 seconds  iterate_original
len(inp)=5103798  10.26  10.07  10.00 seconds  iterate_groupby
len(inp)=5103798   0.95   0.91   0.92 seconds  iterate_replace

By now I'm of course using Python 3, where range doesn't produce lists anymore, eliminating your slowness.

My solution makes 15 passes over the sequence instead of only one pass, but str.replace does all the hard work in C and is simply much faster than interpreting multiple Python instructions for each digit.

Benchmark script:

from itertools import groupby
from time import perf_counter as time
import sys

def print(*args, print=print, file=open('out.txt', 'w')):
    print(*args)
    print(*args, file=file, flush=True)
    
def iterate_original(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
    return new

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

def iterate_replace(num):
    return (
        num
        .replace('111', 'a')
        .replace('222', 'b')
        .replace('333', 'c')
        .replace('11', 'd')
        .replace('22', 'e')
        .replace('33', 'f')
        .replace('1', '11')
        .replace('2', '12')
        .replace('3', '13')
        .replace('a', '31')
        .replace('b', '32')
        .replace('c', '33')
        .replace('d', '21')
        .replace('e', '22')
        .replace('f', '23')
    )

for iterate in iterate_original, iterate_groupby, iterate_replace:
    times = []
    for _ in range(3):
        inp = "1113122113"
        start = time()
        for i in range(50):
            inp = iterate(inp)
        times.append(time() - start)
    print(
        f'{len(inp)=}',
        *(f'{t:6.2f}' for t in times), 'seconds ',
        iterate.__name__
    )

print(sys.version)
\$\endgroup\$
2
\$\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.

\$\endgroup\$
3
  • 2
    \$\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
    Commented Oct 6, 2016 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
    Commented Oct 7, 2016 at 9:21
  • \$\begingroup\$ Good! I would be interested in performance measurements if you have them. \$\endgroup\$ Commented Oct 7, 2016 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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