Optimized speedy solution for Colorful Disks by StefanPochmann - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Optimized solution in Speedy category for Colorful Disks by StefanPochmann

def count_discs(discs):
    count = R = 0
    rev = reversed(discs)
    for r in rev:
        if R < r:
            for R in rev:
                if r < R:
                    count += 2
                    break
            else:
                return count + 1
    return count

May 25, 2024

Comments:

StefanPochmann on May 25, 2024, 7:54 a.m.
This is an optimized version of this already fast solution: <pre class='brush: python'>def count_discs_loop(discs): count = R = 0 for r in reversed(discs): if R < r: R = r count += 1 return count </pre> That one updates the largest radius <pre class='brush: python'>R</pre> and the <pre class='brush: python'>count</pre> every time a larger radius <pre class='brush: python'>r</pre> is found. When my optimized version finds a larger radius <pre class='brush: python'>r</pre>, it instead searches for an even larger radius <pre class='brush: python'>R</pre>. If it finds one, then it's already in the variable <pre class='brush: python'>R</pre> and we only need to increase <pre class='brush: python'>count</pre> once instead of twice. This reduced update work helps if there are many visible discs. Benchmark with <pre class='brush: python'>discs = list(range(10**5, 0, -1))</pre> (executed on CheckiO): <pre class='brush: python'> 6.93 ± 0.00 ms count_discs_optimized 9.26 ± 0.01 ms count_discs_loop 23.58 ± 0.01 ms count_discs_accumulate </pre> Previous versions of this and their discussions: <ol> <li><a href="https://py.checkio.org/mission/colorful-disks/publications/StefanPochmann/python-3/second/share/0a1f6c1cd8d6764dea7f9b863660f6f3/">Unoptimized original</a></li> <li><a href="https://py.checkio.org/mission/colorful-disks/publications/StefanPochmann/python-3/micro-optimized/share/daef91e0b9458f943291084e563957a4/">Micro-optimized</a></li> <li><a href="https://py.checkio.org/mission/colorful-disks/publications/StefanPochmann/python-3/nicer-micro-optimized/share/65a49744b38a04a98a611b8484b772c3/">Nicer micro-optimized</a></li> </ol> Benchmark script: <pre class='brush: python'>def count_discs_accumulate(discs): return len(set(accumulate(reversed(discs), max))) def count_discs_loop(discs): count = R = 0 for r in reversed(discs): if R < r: R = r count += 1 return count def count_discs_optimized(discs): count = R = 0 rev = reversed(discs) for r in rev: if R < r: for R in rev: if r < R: count += 2 break else: return count + 1 return count funcs = [ count_discs_accumulate, count_discs_loop, count_discs_optimized, ] from itertools import accumulate from time import perf_counter as time from statistics import mean, stdev import random discs = list(range(10**5)) random.shuffle(discs) for f in funcs: print(f(discs)) print() discs = list(range(10**5, 0, -1)) times = {f: [] for f in funcs} def stats(f): ts = [t * 1e3 for t in sorted(times[f])[:5]] return f'{mean(ts):5.2f} ± {stdev(ts):4.2f} ms ' for _ in range(100): random.shuffle(funcs) for f in funcs: t = time() f(discs) times[f].append(time() - t) for f in sorted(funcs, key=stats): print(stats(f), f.__name__) </pre> <a href="https://ato.pxeger.com/run?1=hVRBbtswELz0pFfsLaQjG3ZaA4VRf8JXQxBYaZkQkUiBpIKmRl7SSy7tvV_ouS_oa0quJFuyUlSAD54djmZnV_z2o3n2D0a_vn5vvVx-_PPud4kSCtNqn5fKFS4XRdHWbSU8MgL4LoHwWPSt1VChZg49G7EsPqF1WPb0FGrxhXOeJNfKlTHNRJOKsIdD-K0JkcaCBaXhSrTjx0fJQP8E9oLEJyrYCdJp3-5hM7ZP6NyZabyq1der183tBVfxRVNvM-P_Mxu5hxl3dMaGM4d5ZdLW3ZvlzxbF46SClcO51DgOuH0zI9nqwoVuj5csZhuSzmpxxnP0nG-aZEHZmhqUR-uNqRyoujHWw0W1I4QTONQatDInQbQgHNU6lvPCK-dVcdapUeg04CU-JT1khS5NHcYezYSWqnCCBfAe2Wa9WGzDsnaUlXtopayGzU_ipGScFIXRxdhYpT2TPYUn3X_-b_UU1iksN4EabUfGSe7gmMFU_YW2MvbjmOw30NMAPCxgg--J7yPfhabC-pHcUWb8uNtm2XiE8uYUY2A-rPJ2dSdf4NdPOFEmhH0grHZwQy3mtIy94_XwwU8TIY-XXb9OhdwGs9ET42dIjr8R4vSeV6JpUHc9MA5L8KO0-_5IPoVHfN5TLHw8gCGoFOQqz7WoMc95d6n1d9twx_0F">Attempt This Online!</a>

StefanPochmann on May 25, 2024, 8:03 a.m.
Forgot to say: After it finds an even larger radius <pre class='brush: python'>R</pre>, it drops back into the outer loop. It's really two states and alternates between them: Holding the largest radius in <pre class='brush: python'>R</pre> and searching for a larger <pre class='brush: python'>r</pre> (outer loop), and holding the largest radius in <pre class='brush: python'>r</pre> and searching for a larger <pre class='brush: python'>R</pre> (inner loop). It's a technique I've used a few times for different problems.

List, list and list again

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.