Gibt es einen prägnanteren / pythonischen Weg, dies zu tun? (Zählen der längsten Sequenz von Kopf und Zahl bei Münzwürfen)

Question

Zähle die längste Folge von Kopf und Zahl bei 200 Münzwürfen.
Ich habe dies getan - gibt es einen raffinierteren Weg, um es in Python zu tun (ohne zu verdeckt zu sein)?

import random

def toss(n):
    count = [0,0]
    longest = [0,0]
    for i in xrange(n):
        coinface = random.randrange(2)
        count[coinface] += 1
        count[not coinface] = 0

        if count[coinface] > longest[coinface]:
            longest[coinface] = count[coinface]      
        #print coinface, count, longest  

    print "longest sequence heads %d, tails %d" %tuple(longest)

if __name__ == '__main__':
    toss(200)

voir diese für das, was mich zum Spielen veranlasst hat

Answer 1

Dies ist nicht wirklich pythonisch, sondern eher gequält, aber hier ist eine kurze Version (mit bedeutungslosen 1-Zeichen-Variablennamen, nicht weniger!)

import random
x = ''.join([chr(random.randrange(2)) for i in range(200)])
print max([len(s) for s in x.split(chr(0)) + x.split(chr(1))])

Answer 2

Es ist wahrscheinlich ein Axiom, dass jeder Code knapper gestaltet werden kann. Ihr Code sieht jedoch perfekt pythonisch aus.

Wenn ich darüber nachdenke, gibt es vielleicht gar kein solches Axiom der Prägnanz. Wenn kurz und bündig bedeutet "gekennzeichnet durch einen kompakten, präzisen Ausdruck ohne verschwendete Wörter", und wenn wir mit "Wörtern" Wörter des Codes und nicht des Speichers meinen, dann kann ein Ein-Wort-Programm nicht prägnanter gemacht werden (es sei denn, es ist das "Exit"-Programm).

Wenn pythonisch bedeutet "von außerordentlicher Größe und Macht", dann scheint es der Prägnanz zu widersprechen, es sei denn, wir beschränken unsere Definition nur auf die Macht. Ich bin nicht davon überzeugt, dass Ihr Programm überhaupt einem prophetischen Orakel ähnelt, obwohl Sie es als Ascii-Porträt eines bestimmten prophetischen Orakels implementieren könnten. Es sieht nicht wie eine Schlange aus, also gibt es auch hier noch Raum für Verbesserungen.

import random

def toss(n):
    '''
     ___     ____________
<<<((__O\   (__<>___<>__ \   ____
       \ \_(__<>___<>__)\O\_/O___>-<  hiss
        \O__<>___<>___<>)\___/

    '''
    count = [0,0]
    longest = [0,0]
    for i in xrange(n):
        coinface = random.randrange(2)
        count[coinface] += 1
        count[not coinface] = 0

        if count[coinface] > longest[coinface]:
            longest[coinface] = count[coinface]
        #print coinface, count, longest

    print "longest sequence heads %d, tails %d" %tuple(longest)

if __name__ == '__main__':
    toss(200)

Raffiniert, nicht wahr?

Answer 3

import random, itertools

def toss(n):
    faces = (random.randrange(2) for i in range(n))
    longest = [0, 0]
    for face, seq in itertools.groupby(faces):
        longest[face] = max(longest[face], len(list(seq)))
    print "longest sequence heads %d, tails %d" % tuple(longest)

Answer 4

Algorithmus zum Scannen von Zeichenketten

Wenn Sie einen schnellen Algorithmus suchen, können Sie den Algorithmus verwenden, den ich kürzlich für eine Interviewfrage entwickelt habe, bei der es um die längste Folge von aufeinanderfolgenden Buchstaben in einer Zeichenkette ging. Siehe Blogeintrag hier .

def search_longest_substring(s):
    """
    >>> search_longest_substring('AABBBBCBBBBACCDDDDDDAAABBBBCBBBBACCDDDDDDDAAABBBBCBBBBACCDDDDDDA')
    (7, 'D')
    """
    def find_left(s, midc, mid, left):
        for j in range(mid-1, left-1, -1):
            if s[j] != midc:
                return j + 1
        return left
    def find_right(s, midc, mid, right):
        for k in range(mid+1, right):
            if s[k] != midc:
                return k
        return right
    i, longest = 0, (0, '')
    while i < len(s):
        c = s[i]
        j = find_left(s, c, i, i-longest[0])
        k = find_right(s, c, i, len(s))
        if k-j > longest[0]:
            longest = (k-j, c)
        i = k + longest[0]
    return longest

if __name__ == '__main__':
    import random
    heads_or_tails = "".join(["HT"[random.randrange(0, 2)] for _ in range(20)])
    print search_longest_substring(heads_or_tails)
    print heads_or_tails

Dieser Algorithmus ist O(n) im schlimmsten Fall (alle Münzwürfe sind identisch) oder O(n/m) im durchschnittlichen Fall (wobei m die Länge der längsten Übereinstimmung ist). Bitte korrigieren Sie mich in diesem Punkt.

Der Code ist nicht besonders pythonisch (d.h. er verwendet keine Listenauflösungen oder itertools oder andere Dinge). Es ist in Python und es ist ein guter Algorithmus.

Mikro-Optimierungen

Für die Mikro-Optimierung Menge, hier sind Änderungen, die dies wirklich schreien in Python 2.6 auf einem Windows Vista Laptop machen:

def find_left(s, midc, mid, left):
    j = mid - 1
    while j >= 0:
        if s[j] != midc:
            return j + 1
        j -=  1
    return left
def find_right(s, midc, mid, right):
    k = mid+1
    while k < right:
        if s[k] != midc:
            return k
        k += 1
    return right

Zeitliche Ergebnisse für 1000 Iterationen mit timeit :

range: 2.670
xrange: 0.3268
while-loop: 0.255

Hinzufügen von psyco in die Datei importieren:

try:
    import psyco
    psyco.full()
except ImportError:
    pass

0,011 bei 1000 Iterationen mit psyco und while-Schleife. Mit vernünftigen Mikro-Optimierungen und dem Import von psyco läuft der Code etwa 250-mal schneller.