slow runtime for large input values

Question

This code is supposed to take a string of r (red), b (blue) and y (yellow) values and combine them, pairwise, to find one resulting colour. For example, 'rybbry' -> 'brbyb' -> 'yyrr' -> 'ybr' -> 'ry' -> 'b'. It works for small inputs, but forever for big ones. Too many nested loops?

def colour_trio(colours):
  while len(colours) > 1:
    new_colours = ''
    for i in range(len(colours) - 1):
      if colours[i:i+2] == 'rr' or colours[i:i+2] == 'by' or colours[i:i+2] == 'yb':
        new_colours = new_colours + 'r'
      elif colours[i:i+2] == 'bb' or colours[i:i+2] == 'ry' or colours[i:i+2] == 'yr':
        new_colours = new_colours + 'b'
      else:
        new_colours = new_colours + 'y'
    colours = new_colours
  
  if len(colours) == 1:
    if colours[0] == 'b':
        return 'b'
    if colours[0] == 'y':
        return 'y' 
    if colours[0] == 'r':
        return 'r'

Tried this as well. Still runtime is too long.

def colour_trio(colours):
  colours = list(colours)
  length = len(colours)
  for i in range(length-1):
    for k in range(length - 1 - i):
      colours[k] = color_sum(colours[k:k+2])
  return colours[0]

def color_sum(pair):
    if pair[0] == pair[1]:
        return pair[0]
    if 'r' in pair:
        if 'b' in pair:
            return 'y'
        return 'b'
    return 'r'

Here is what the tester file looks like:

def colour_trio_generator(seed):
    rng = random.Random(seed)
    items = ''
    for n in islice(pyramid(3, 4, 1), 10000):
        items += rng.choice('ryb')
        yield items
        if len(items) == n:
            items = rng.choice('ryb')

I didn't understand the rules for transforming the input to the output. — mkrieger1, Apr 10 '22 at 20:40
@mkrieger1 the code helps with that. For string length `n` you take `n-1` pairs and compact all of them at once. It's `O(n^2)` actually with a lot strings copied over and over, so it's not strange it works so slow. Thinking how it could be improved. — kosciej16, Apr 10 '22 at 20:44
This isn't going to be a major speed-up, but an obvious improvement would be to assign `colours[i:i+2]` to a variable, rather than performing that slice six times. — jasonharper, Apr 10 '22 at 20:46
@JacopoStifani see BrokenBenchamrk solution, he used that idea. — kosciej16, Apr 11 '22 at 10:06
@kosciej16 Actually strings can be faster, see the benchmarks in my answer. — Kelly Bundy, Apr 12 '22 at 10:20

score 1 · Answer 1 · answered Apr 10 '22 at 20:50

1

Your code makes use of repeated string concatencation. Each addition operation on a string takes O(n) time, because strings are immutable. This operation occurs O(n^2) times, so the runtime of your algorithm is O(n^3), where n is the length of the string.

One optimization is to use a list to store the letters, and then call ' '.join(), taking the runtime from O(n^3) to O(n^2):

def colour_trio(colours):
    result = colours
    
    while len(result) != 1:
        letters = []
        for fst, snd in zip(result, result[1:]):
            if fst == snd:
                letters.append(fst)
            else:
                [letter_to_add] = list(set('ryb') - set(fst) - set(snd))
                letters.append(letter_to_add)
            
        result = ''.join(letters)
        
    return result
    
print(colour_trio("rybbry")) # Prints "b"

answered Apr 10 '22 at 20:50

BrokenBenchmark

18,126
7
21
33

This makes sense. I ran it on my tester and the function is still too slow. – Jacopo Stifani Apr 11 '22 at 13:55
What input size are you running on? – BrokenBenchmark Apr 12 '22 at 00:47
big enough that it takes more than 20 seconds – Jacopo Stifani Apr 12 '22 at 02:35
I meant the length of the string, not the number of seconds it takes to run. – BrokenBenchmark Apr 12 '22 at 02:36
I understand... i don't know what the string length is, a tester automatically generates one long enough that the code takes over 20 seconds to execute. – Jacopo Stifani Apr 12 '22 at 02:57
Do you have any information on constraint size, where these strings come from, etc.? There's not much we can do without this information. – BrokenBenchmark Apr 12 '22 at 03:25
I've added the tester code to the OP. Not sure how to read it though. – Jacopo Stifani Apr 12 '22 at 03:29
This actually appears to be the *slowest* so far, see benchmarks in my answer. – Kelly Bundy Apr 12 '22 at 10:28

Fabio Craig Wimmer Florey · Answer 2 · 2022-04-12T12:45:24.830

I think this is faster than the last solution I posted and faster than other solutions, I think classes make everything tidy looking, but you can re-work it to become a single function.

PS. Thank you for the feedback @KellyBundy! Now the algorithm is correct, it took even fewer chars!

New Solution

colors = ['r', 'b', 'y']

def split(x):
    return [f'{Couple(i)}' for i in [f'{x[i]}{x[i+1]}' for i in range(len(x)-1)]]

class Couple:
    def __init__(self, x) -> None:
        self.a = x[0]
        self.b = x[1]

    def __repr__(self) -> str:
        if self.a == self.b:
            return self.a
        return (set(colors).difference(set((self.a, self.b))).pop())

def ColoursTrio(x):
    while len(x) > 1:
        x = split(x)
    return x[0]

print(ColoursTrio('bbr'))

or even shorter (and faster):

def ColoursTrio(x):
    while len(x) > 1:
        x = [f'''{i[0] if i[0] == i[1] 
            else  set("rby").difference(set((i[0],
            i[1]))).pop()}''' for i in [f'{x[i]}{x[i+1]}' 
            for i in range(len(x)-1)]]
    return x[0]

print(ColoursTrio('bbr'))

Old Solution

This is almost a bit convoluted but I think it's faster, I also think it's very similar to the one posted by @BrokenBenchmark (and I think his is better) so I'll add his example string too!

COLORS = ['r','b','y']

class ColorsCouple:
    def __init__(self, x:str, y:str) -> None:
        self.x = x
        self.y = y
    
    def mix(self):
        if self.x == self.y:
            return f'{self.x}'
        if 'y' in (self.x, self.y):
            return set(COLORS).difference((self.x, self.y)).pop()
        return 'y'

class Colors:
    def __init__(self, colors:str) -> None:
        self.colors = self.get_couples([*colors])
    
    def get_couples(self, element):
        return [(element[i],element[i+1]) for i in range(len(element)-1)]

    def get_color(self):
        colors = [ColorsCouple(*couples).mix() if len(couples)==2 else couples[0] for couples in self.colors]
        while len(colors)>1:       
            colors = self.get_couples(colors)
            colors = [ColorsCouple(*couples).mix() if len(couples)==2 else couples[0] for couples in colors]
        return colors[0]

    def __repr__(self) -> str:
        return f'{self.get_color()}'

print(Colors('bbr'))
print(Colors('rybbry'))

Yeah, Kelly, I just noticed that the algorithm is way different than I read, I wrote it at work in a coffee pause (not that it justifies me!). Mine took groups of colors, but not all groups! I'll write another one in a couple of minutes since I'll be having a coffe :) — Fabio Craig Wimmer Florey, Apr 12 '22 at 12:27
@KellyBundy adjusted the coupling of charachters! I'm ready for your benchmark! — Fabio Craig Wimmer Florey, Apr 12 '22 at 12:46

Kelly Bundy · Answer 3 · 2022-04-12T14:53:20.490

Another solution, first some benchmark results, with random strings of 70 to 560 letters (I think 140 is the maximum in the actual tests):

 n= 70   n=140   n=280   n=560 
  0.03    0.06    0.11    0.24  Kelly_linear (I might show this one later)
  0.47    1.71    6.58   25.85  Kelly        (this is the one I am already showing)
  0.77    3.17   12.50   52.57  Jacopo_2
  1.59    6.38   25.62  107.81  Jacopo_1
  1.69    7.09   27.93  110.67  Fabio
  1.82    7.69   30.17  120.77  BrokenBenchmark

My solution is the function Kelly below. First I double every letter, then trim first and last letter. So rybbry becomes ryybbbbrry. Essentially that gives me all the pairs, if you think spaces into it then it would be ry yb bb br ry. Then I replace pairs of different letters with what that pair shall become, but in uppercase. So I get BRbbYB. Then replace pairs of equal letters with what that pair shall become: BRBYB. Then just go back to lower case. Repeat until done.

Full benchmark code (Try it online!):

def Kelly(colours):
    while len(colours) != 1:
        colours = (colours
            .replace('b', 'bb')
            .replace('r', 'rr')
            .replace('y', 'yy')
            [1:-1]
            .replace('br', 'Y').replace('rb', 'Y')
            .replace('by', 'R').replace('yb', 'R')
            .replace('ry', 'B').replace('yr', 'B')
            .replace('bb', 'B')
            .replace('rr', 'R')
            .replace('yy', 'Y')
            .lower())
    return colours

def Jacopo_1(colours):
  while len(colours) > 1:
    new_colours = ''
    for i in range(len(colours) - 1):
      if colours[i:i+2] == 'rr' or colours[i:i+2] == 'by' or colours[i:i+2] == 'yb':
        new_colours = new_colours + 'r'
      elif colours[i:i+2] == 'bb' or colours[i:i+2] == 'ry' or colours[i:i+2] == 'yr':
        new_colours = new_colours + 'b'
      else:
        new_colours = new_colours + 'y'
    colours = new_colours
  if len(colours) == 1:
    if colours[0] == 'b':
        return 'b'
    if colours[0] == 'y':
        return 'y' 
    if colours[0] == 'r':
        return 'r'

def Jacopo_2(colours):
  colours = list(colours)
  length = len(colours)
  for i in range(length-1):
    for k in range(length - 1 - i):
      colours[k] = color_sum(colours[k:k+2])
  return colours[0]
def color_sum(pair):
    if pair[0] == pair[1]:
        return pair[0]
    if 'r' in pair:
        if 'b' in pair:
            return 'y'
        return 'b'
    return 'r'

def BrokenBenchmark(colours):
    result = colours    
    while len(result) != 1:
        letters = []
        for fst, snd in zip(result, result[1:]):
            if fst == snd:
                letters.append(fst)
            else:
                [letter_to_add] = list(set('ryb') - set(fst) - set(snd))
                letters.append(letter_to_add)
            
        result = ''.join(letters)        
    return result

def Fabio(x):
    while len(x) > 1:
        x = [f'''{i[0] if i[0] == i[1] 
            else  set("rby").difference(set((i[0],
            i[1]))).pop()}''' for i in [f'{x[i]}{x[i+1]}' 
            for i in range(len(x)-1)]]
    return x[0]

lengths = 70, 140, 280, 560
funcs = [
    Kelly,
    Jacopo_2,
    Jacopo_1,
    Fabio,
    BrokenBenchmark,
]

from timeit import default_timer as timer, repeat
import random

Tss = [[] for _ in funcs]
for length in lengths:
    tss = [[] for _ in funcs]
    for _ in range(5):
        colours = ''.join(random.choices('bry', k=length))
        def run():
            global result
            result = func(colours)
        expect = None
        for func, ts in zip(funcs, tss):
            t = min(repeat(run, number=1))
            if expect is None:
                expect = result
            assert result == expect
            ts.append(t)
           # print(*('%7.3f ms ' % (t * 1e3) for t in sorted(ts)[:3]), func.__name__)
       # print()
    print(*(f' n={length:3} ' for length in lengths))
    for func, Ts, ts in zip(funcs, Tss, tss):
        Ts.append(min(ts))
        print(*('%6.2f ' % (t * 1e3) for t in Ts), func.__name__)
    print()

Wonderful idea! Would never have thought of this. Works like a (py)charm. Still running just over 10s for the tester, but at least under 20. — Jacopo Stifani, Apr 12 '22 at 14:53
@JacopoStifani Yeah I'm really not sure whether this is intended to be solved in quadratic or linear time. It *can* be done in linear time. See the first row of the benchmark results I just added :-) — Kelly Bundy, Apr 12 '22 at 14:55
Incredible. This is an introductory course in Python, so at this stage of my learning I am just trying to wrap my brain around the question at hand. Optimization for us means execution under 20 seconds. I'll worry about faster runtimes on my next revisit. — Jacopo Stifani, Apr 12 '22 at 15:06

slow runtime for large input values

3 Answers3

New Solution

Old Solution