umpy gcd函数

Question

在其模块的结构中具有一个

gcd

函数？

我知道

fractions.gcd

numpy

，但认为等效可能会更快，并且可以更好地与

numpy

datatypes一起工作。 除了这个似乎已经过时的

link之外，我无法在Google上发现任何内容，我不知道我将如何访问它的功能。

试图：_gcd

没有为我工作...

你可以自己写：

np.gcd
np.euclid

在这里是测试结果和速度的代码：

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

Answer 1

使用Python 3.5

的任何人的公共服务公告

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

如果您想自己写一个单线：

from math import gcd
gcd(2, 4)

Answer 2

它似乎在

def gcd(a: int, b: int): return gcd(b, a % b) if b else a

中还没有

gcd

功能。但是，分数模块中有一个

GCD函数。如果您需要在

numpy

数组上执行

Answer 3

，则可以使用它来构建一个：

numpy

函数GCD（最大的常见除数）

和lcm（最低的常见倍数）

已添加到numpy

IN版本1.15

。 您可以在一对标量上使用它们“原样”

ufunc

或在列表或数组中使用

gcd = numpy.frompyfunc(fractions.gcd, 2, 1)

：

Answer 4

import numpy as np

np.gcd(-5, 10)  # yields '5'

在情况下，所需的结果不是元素的GCD，而是数组中所有数字的GCD，您可以使用以下代码。 .reduce 在用例上删除，省略排序步骤

np.gcd.reduce(np.array([-5, 10, 0, 5])) # yields '5'

的速度更快。

使用ufuncs的替代方案（也许更优雅但更慢）是

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

我到了这里尝试使用基于numpy的跨跨标准

arrayapi

。规范

Answer 5

没有

a = np.unique(a)

函数，也没有支持索引数组。这是我基于2013年Hyry's的实施。我展开了循环的2次迭代，并使用更多变量尝试重复使用数据，减少操作，减少所作用的数据量并尽可能避免分配。

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]