Post Reply 
Little explorations with HP calculators (no Prime)
12-28-2018, 02:00 PM
Post: #328
RE: Little explorations with HP calculators (no Prime)
(12-28-2018 09:06 AM)ijabbott Wrote:  I'm not that fluent in Python, but surely the O(n^2) versions of match_count above could be replaced with an O(n) version to speed it up a bit?

EDIT: Oh, I see Albert Chan has already done it in his version!

Yes, his version nicely speeds up the match_count process. I didn't take the time to absorb it when I first looked at it, but my "aha!" moment occurred when I was thinking about implementing a SysRPL version of this test. As I was working through the possibilities in my head, I thought about rearranging the list being tested to make it easier to keep track of the running totals, and it suddenly hit me: "ahh, that's what Albert was doing with zip!" The light bulb flashed in my head, and I felt a little less confused for a moment. Smile

python's cProfile airs the real "dirty laundry" of this process, though, and it's something that none of our code snippets have addressed: random.shuffle(). If I'm reading the the profile report correctly, it appears that about 92% of the time taken by the fastest version (so far) was spent performing shuffles:
Code:
         4849009 function calls in 3.345 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    3.345    3.345 <string>:1(<module>)
        1    0.019    0.019    3.345    3.345 christmas_balls_ac.py:13(main)
    10000    0.229    0.000    0.245    0.000 christmas_balls_ac.py:4(match_count)
      142    0.000    0.000    0.000    0.000 cp1252.py:18(encode)
  1390000    1.520    0.000    2.054    0.000 random.py:224(_randbelow)
    10000    1.024    0.000    3.080    0.000 random.py:264(shuffle)
      142    0.000    0.000    0.000    0.000 {built-in method _codecs.charmap_encode}
        1    0.000    0.000    3.345    3.345 {built-in method builtins.exec}
    10000    0.002    0.000    0.002    0.000 {built-in method builtins.len}
       71    0.001    0.000    0.001    0.000 {built-in method builtins.print}
    10000    0.016    0.000    0.016    0.000 {built-in method builtins.sum}
  1390000    0.117    0.000    0.117    0.000 {method 'bit_length' of 'int' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
  2028650    0.418    0.000    0.418    0.000 {method 'getrandbits' of '_random.Random' objects}

The code that caused that result was a combination of Thomas Klemm's main() with Albert Chan's match_count():
Code:
import random
import cProfile

def match_count(thelist):
    head, tail = thelist[:70], thelist[70:]
    s = sum(head)
    n = s == 50
    for h, t in zip(head, tail):
        s = s - h + t
        if s==50: n = n + 1
    return n

def main(n):
    thelist = [1]*100 + [0]*40
    result = [0] * 72
    for _ in range(n):
        random.shuffle(thelist)
        result[match_count(thelist)] += 1
    for i, value in enumerate(result[1:], start=1):
        print('%d\t%d' % (i, value))

if __name__ == '__main__':
    cProfile.run('main(10000)')
(I shortened the runs to 10000 due to my lack of patience)
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Little explorations with HP calculators (no Prime) - DavidM - 12-28-2018 02:00 PM



User(s) browsing this thread: 3 Guest(s)