python - 编码-CountNonDivisible(Python，性能更好)

Question

有问题的练习是：


  您将得到一个由N个整数组成的数组A。
  
  对于0≤i   不是A [i]除数的数组元素。我们说
  这些元素是非因数的。
  
  例如，考虑整数N = 5和数组A使得：

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 3
A[4] = 6 For the following elements:

  
  A [0] = 3，非因数是：2，6，A [1] = 1，非因数是：
  3，2，3，6，A [2] = 2，非因数是：3，3，6，A [3] = 3，
  非除数为：2、6，A [4] = 6，没有任何非除数。写
  功能：
  
  def解决方案（A）
  
  给定一个由N个整数组成的数组A，则返回一个序列
  表示非除数的整数。
  
  结果数组应以整数数组形式返回。
  
  例如，给定：

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 3
A[4] = 6 the function should return [2, 4, 3, 2, 0], as explained above.

  
  针对以下假设编写有效的算法：
  
  N是[1..50,000]范围内的整数；数组A的每个元素
  是[1..2 * N]范围内的整数。


我的直接解决方案是：

def solution(A):

    sol = [0]*len(A)

    for i in range(0, len(A)):
        for j in range(0, len(A)):
            if i != j and A[i] % A[j] != 0:
                sol[i] += 1
    return sol

这可以正常工作，但是在性能上却很糟糕。

改进代码的下一步是什么？

Answer 1

另一个尝试（100% result at Codility）

在这里，我使用collections.Counter来获取列表中单个数字的计数。

从计数器迭代每个唯一键（值x），我知道我只需要检查x的因数。对于计数器中存在的每个因子，我都会减少非因数的初始和。

代码：

from itertools import chain
from collections import Counter

lst = [3, 1, 2, 3, 6]

def factors(n):
    yield from chain.from_iterable(({i, n//i} for i in range(1, int(n ** 0.5) + 1) if n % i == 0))

def get_non_divisible(lst):
    c = Counter(lst)
    d = {val: sum((-c.get(f, 0) for f in factors(val)), len(lst)) for val in c}
    return [d[i] for i in lst]

sol = get_non_divisible(lst)
print(sol)

印刷品：

[2, 4, 3, 2, 0]

做一些基准测试（solution()是@GaborFekete答案，solution_naive()是@Eric答案）：

from timeit import timeit
from random import randint

lst = []
N = 20000
for _ in range(N):
    lst.append(randint(1, N*2+1))

t1 = timeit(lambda: get_non_divisible(lst), number=1)
print(t1)
t2 = timeit(lambda: solution(lst), number=1)
print(t2)
t3 = timeit(lambda: solution_naive(lst), number=1)
print(t3)

印刷品（机器AMD 2400G，Python3.6）：

0.13960983700235374
54.908645510993665
33.11579795999569

哪一种方法到目前为止是最快的。

对于N=50000，时间为0.49225338897667825-其他算法超时。