Nicer micro-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.

Nicer micro-optimized solution in Speedy category for Colorful Disks by StefanPochmann

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

May 19, 2024

Comments:

StefanPochmann on May 19, 2024, 10:38 p.m.
Two nested loops instead of one allow me to update <pre class='brush: python'>count</pre> only half as often and avoids updating the largest radius with <pre class='brush: python'>R = r</pre> completely. Times for discs = list(range(10**5, 0, -1)) <pre class='brush: python'> 3.67 ± 0.02 ms count_discs_4b 5.17 ± 0.02 ms count_discs Python: 3.12.2 (main, May 17 2024, 19:27:45) [GCC 14.1.1 20240507] </pre> Benchmark script: <pre class='brush: python'>def count_discs(discs): c = R = 0 for r in reversed(discs): if R < r: R = r c += 1 return c def count_discs_4b(discs): count = 0 R = 0 rev = reversed(discs) for r in rev: if R < r: for R in rev: if r < R: count += 1 break else: return 2*count + 1 return 2*count funcs = [count_discs, count_discs_4b] from itertools import * from timeit import timeit from statistics import mean, stdev import sys import random discs = list(range(10**6)) 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 = timeit(lambda: f(discs), number=1) times[f].append(t) for f in sorted(funcs, key=stats): print(stats(f), f.__name__) print('\nPython:', sys.version) </pre> <a href="https://ato.pxeger.com/run?1=hVRLbtswEN10pVPMzpKjCFYaF4VQX6CrwFtXEGRpmBCRKIGkAhhGTpJNNu2-V-gxepoOKcr6GEUI2DDfPA7fvBnz7Vd70k-NeH__2Wl2-_Xvp-8lMiiaTuis5KpQvv0OEg9oFbCDPX02dscaCRK4AIkvKBWWM65ZnBH9G8gRMctkkDOkgJsdxBaSqDspoPC8hZDs_jjXYkIXLaMqEmPyzyVd6f1Io-Hur7iTM5LO7K8jo7JLRct1lJg_zyJYKbxO5Zy4W7t8c4Mc7HmsE4Wiig8Tr8KFcSnRZFMD1yh101QKeN02UsO6xzWvkesB7Hd9ROlcc6V5cTlSYy5Cwkt88RykTmr4KXNRNjU1z9xMqio67BP4iH68Wa-_BIHXUyL11DFW4dAgYzgzhtt6ejdayYX2maMEXr8P_pt9G8ImhNuYqKYGwzizBA4pzLO_2tkypSmfuXHS1kNyBGL8bPna8BUVRVNk0x1YGhySbZpO-8BWZ-OIr2kut9Ede4U_v-Fs7bHYvcVqBStbYmZnyineuLsXjliN48guXbFqSWzfJr_K62OZJzDYFILo6iPKXRyMdCc_ytsWBZUz8dtVaC8I4RlPO2tMMG3BYFUILMoykdeYZdSGPrj6IR7sI5KsQjMKkfnn8UYE_ZPiXpbhhfkH">Attempt This Online!</a>

veky on May 19, 2024, 10:45 p.m.
Is it really faster to update by 1 and then multiply by 2 at the end, than to just update by 2?

StefanPochmann on May 19, 2024, 10:56 p.m.
Yes. Not by much, but with <pre class='brush: python'>discs = list(range(512, 0, -1))</pre> you can clearly see it: <pre class='brush: python'>13.89 ± 0.01 μs count_discs_plus1 15.95 ± 0.04 μs count_discs_plus2 </pre> Though I do wish I had done it, as it's clearer and prettier: <pre class='brush: python'>def count_discs_plus2(discs): count = 0 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 </pre> <a href="https://ato.pxeger.com/run?1=1ZS9btswEICXTnqK2yy5imoJcVAI9TsUXl1BkK1jQ0SiBJIKYBh5ki5Zkj17pj5AH6CP0qnHH8V25LFLNUjk_fHuuxN_PPd7fduJx8enQbOrz78__KmRwa4bhC5rrnaq7JtBpaFdR3kA9FgtrGBhd-u3lcR7WtMbpcLau1gN6yRI4MIoXQzzcEbOX0AeJaPtemJ74iPJZz3VHDP7uIL0onorsbo702CjcBpKoh6kgGzu4_lw5-IguEQq-99IZf-C1EVOnhIbxE5RtZvJUMVTegXZy64FrlHqrmsU8LbvpIa5k2veItej0O2cRulKc6X57s2lxUrEJK_xPvAitVfjUlai7lpqojmc0mvIOSThdwzTxXx-E0WBM0nU7cBYg2OXDHVmqNvCHJJecqFD5k2iwO2ji9GXaRbDIoarlAxNBUZ_YDlsCjiP_WAnzBSmQuYnSluUxANSvLH22tgrKokGyYbbsCLa5MuiOG0Gmx0Mj1DTaC6TjD3Azxc4WDhWdm1lv14VzGyFpZ0rj2PhD38HxCZ5HNv3UGy6lK3rUthU7bauchgpxSCGdotyZeLDJ6DP0c3XkVR9j4LqOsHuS7UHxXCH-5UlFJ12YmQWA0vKUlQtliV1wyln38RXe-nls9hMRGL-Qt6JyF2B_iYcb8S_">Attempt This Online!</a>

StefanPochmann on May 19, 2024, 10:46 p.m.
Maybe <pre class='brush: python'>count += 2</pre> without the <pre class='brush: python'>2*</pre> in the return would be better because it would be clearer. Guess why I did it the way I did.

veky on May 19, 2024, 10:55 p.m.
It's especially puzzling for me, since I saw previous versions of yours that used the other approach. :o Of course, on some older processors, INCing memory directly was quicker than ADC, but that's so removed from modern Python that it really doesn't play any role here.

StefanPochmann on May 19, 2024, 11:31 p.m.
Do you see it now? Is the 512 in the above benchmark enough of a hint? :-)

veky on May 20, 2024, 7:18 a.m.
You mean preconstructed integers? But there are so few of them (compared to list sizes that you seem to target), and it doesn't work for floats anyway.

StefanPochmann on May 20, 2024, 8:13 a.m.
Yes that's it. Yes, for the sizes I had previously benchmarked it's really insignificant and even for 512 updates it's not much. But, well, very large sizes aren't everything, and for such smaller sizes it's at least some advantage. And yes, it doesn't work for floats, which is why I only did it for ints. I'm thinking of cleaning up, posting the countdiscsplus2 version, deleting the others, but linking to them with the "share" links in a comment so I think the discussions will remain accessible. Do you know what happens with deleted solutions? Are they just not listed anymore or do they fully get deleted at some point so they're not accessible at all anymore?

veky on May 20, 2024, 8:22 a.m.
I think they are really deleted, but it's been a long time since I deleted anything here. I'm not Germanly obsessed with order. 😅

StefanPochmann on May 31, 2025, 3:08 p.m.
Still accessible a year later, so I guess they're safe :-)

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.