Numpy gcd-Funktion

Tut numpy haben eine gcd Funktion irgendwo in der Struktur der Module?

Ich bin mir dessen bewusst fractions.gcd dachte aber, ein numpy entspricht vielleicht potenziell schneller und besser arbeiten mit numpy Datentypen.

Habe ich nicht in der Lage war zu entdecken, nichts auf google außer diesem link, die scheint veraltet und ich weiß nicht, wie ich den Zugriff auf die _gcd - Funktion schlägt er existiert.

Naiv versucht:

np.gcd
np.euclid

nicht für mich gearbeitet...

  • Ich denke, die _gcd Funktion, die Sie sprechen, das ist bei numpy.core._internal._gcd, aber es ist in reinem Python (und so nicht zu schnelle) und nicht handhaben numpy-arrays in jedem Fall.
  • ist der de-facto-Ansatz Fraktionen.gcd? Ich gehe davon aus, dass eine schnellere Umsetzung in C
InformationsquelleAutor bph | 2013-03-22
  1. 11

    Können Sie es selbst schreiben:

    def numpy_gcd(a, b):
    a, b = np.broadcast_arrays(a, b)
    a = a.copy()
    b = b.copy()
    pos = np.nonzero(b)[0]
    while len(pos) > 0:
        b2 = b[pos]
        a[pos], b[pos] = b2, a[pos] % b2
        pos = pos[b[pos]!=0]
    return a

    Hier ist der code, um das Ergebnis testen und die Geschwindigkeit:

    In [181]:
n = 2000
a = np.random.randint(100, 1000, n)
b = np.random.randint(1, 100, n)
al = a.tolist()
bl = b.tolist()
cl = zip(al, bl)
from fractions import gcd
g1 = numpy_gcd(a, b)
g2 = [gcd(x, y) for x, y in cl]
print np.all(g1 == g2)

True

In [182]:
%timeit numpy_gcd(a, b)

1000 loops, best of 3: 721 us per loop

In [183]:
%timeit [gcd(x, y) for x, y in cl]

1000 loops, best of 3: 1.64 ms per loop
    • zwei und ein bisschen, mal schneller, für Ihre numpy-version
    • die Funktion, die Sie schrieb nicht für numpy_gcd(10, 5) oder mache ich etwas falsch? Ich bekomme 0-d arrays können nicht indiziert werden
    • Sein, weil die Funktion erwartet numpy-arrays (und wahrscheinlich numpy Skalare). Sie sollten in der Lage sein zu tun numpy_gcd[10], [5]) oder ändern Sie die Funktion, um direkt mit Python-Skalare.
    InformationsquelleAutor HYRY
  2. 10

    Public service announcement für jemand mit Python 3.5

    from math import gcd
gcd(2, 4)

    Und wenn Sie wollen, schreiben Sie es sich in einem one-liner:

    def gcd(a: int, b: int): return gcd(b, a % b) if b else a
    InformationsquelleAutor lababidi
  3. 7

    Es scheint, gibt es keine gcd Funktion noch in numpy. Es gibt jedoch eine gcd-Funktion in Bruchteilen Modul. Wenn Sie brauchen, um gcd auf numpy arrays, Sie bauen konnte ufunc Verwendung:

    gcd = numpy.frompyfunc(fractions.gcd, 2, 1)
    • Ich bin überrascht, numpy enthält nicht gcd-Funktion
    • Schön. Nehmen Sie den gcd von einer gesamten Liste, können Sie numpy.ufunc.reduce(gcd, m) wo m ist die Liste und die gcd ist, wie in dieser Antwort.
    InformationsquelleAutor Charles Brunet
  5. 1

    Falls das gewünschte Ergebnis nicht ein element-wise gcd, sondern der ggT aller zahlen im array ist, können Sie folgenden code verwenden. 

    import numpy as np
from math import gcd as mathgcd

def numpy_set_gcd(a):
    a = np.unique(a)
    if not a.dtype == np.int or a[0] <= 0:
        raise ValueError("Argument must be an array of positive " +
                         "integers.")

    gcd = a[0]
    for i in a[1:]:
        gcd = mathgcd(i, gcd)
        if gcd == 1:
            return 1 

    return gcd

    Je nach Anwendungsfall, kann es schneller sein das weglassen der Sortierung Schritt a = np.unique(a).

    Alternative (vielleicht eleganter, aber langsamer) Umsetzung mit ufuncs ist

    import numpy as np
from math import gcd as mathgcd
npmathgcd = np.frompyfunc(mathgcd, 2, 1)

def numpy_set_gcd2(a):
    a = np.unique(a)
    if not a.dtype == np.int or a[0] <= 0:
        raise ValueError("Argument must be an array of positive " +
                         "integers.")
    npmathgcd.at(a[1:], np.arange(a.size-1), a[:-1])
    return a[-1]
    InformationsquelleAutor Samufi
Schreibe einen Kommentar