Ich habe eine Funktion, die im Grunde genommen viele Aufrufe an eine einfach definierte Hash-Funktion ausführt und prüft, ob sie ein Duplikat findet. Ich muss viele Simulationen damit machen, also möchte ich, dass es so schnell wie möglich ist. Ich versuche, Cython zu verwenden, um dies zu tun. Der Cython-Code wird derzeit mit einer normalen Python-Liste von Ganzzahlen mit Werten im Bereich von 0 bis m ^ 2 aufgerufen.

import math, random
cdef int a,b,c,d,m,pos,value, cyclelimit, nohashcalls   
def h3(int a,int b,int c,int d, int m,int x):
    return (a*x**2 + b*x+c) %m    
def floyd(inputx):
    dupefound, nohashcalls = (0,0)
    m = len(inputx)
    loops = int(m*math.log(m))
    for loopno in xrange(loops):
        if (dupefound == 1):
            break
        a = random.randrange(m)
        b = random.randrange(m)
        c = random.randrange(m)
        d = random.randrange(m)
        pos = random.randrange(m)
        value = inputx[pos]
        listofpos = [0] * m
        listofpos[pos] = 1
        setofvalues = set([value])
        cyclelimit = int(math.sqrt(m))
        for j in xrange(cyclelimit):
            pos = h3(a,b, c,d, m, inputx[pos])
            nohashcalls += 1    
            if (inputx[pos] in setofvalues):
                if (listofpos[pos]==1):
                    dupefound = 0
                else:
                    dupefound = 1
                    print "Duplicate found at position", pos, " and value", inputx[pos]
                break
            listofpos[pos] = 1
            setofvalues.add(inputx[pos])
    return dupefound, nohashcalls 

Wie kann ich inputx und listofpos konvertieren, um Arrays vom Typ C zu verwenden und mit C-Geschwindigkeit auf die Arrays zuzugreifen? Gibt es noch andere Beschleunigungen, die ich verwenden kann? Kann der Wertesatz beschleunigt werden?

Damit es etwas zu vergleichen gibt, benötigen 50 Aufrufe von floyd () mit m = 5000 auf meinem Computer derzeit ungefähr 30 Sekunden.

Update: Beispielcode-Snippet, um zu zeigen, wie Floyd aufgerufen wird.

m = 5000
inputx = random.sample(xrange(m**2), m)
(dupefound, nohashcalls) = edcython.floyd(inputx)