python - 在列表中查找因子的最有效方法是什么？

Question

我想做什么:

我需要做一个函数，给定一个正整数列表(可以有重复的整数)，计算所有三元组(在列表中)，其中第三个数字是第二个数字的倍数，第二个数字是倍数第一个:

(同一个数字不能在一个三元组中使用两次，但可以被所有其他三元组使用)

例如，[3, 6, 18] 是一个，因为 18 均匀地进入 6 而均匀地进入 3 。

所以给定 [1, 2, 3, 4, 5, 6] 它应该找到:

[1, 2, 4] [1, 2, 6] [1, 3, 6]

并返回3(它找到的三元组的数量)

我尝试过的:

我制作了几个功能，但效率不够高。是否有一些我不知道的数学概念可以帮助我更快地找到这些三元组？具有更好功能的模块？我不知道要搜索什么...

def foo(q):
    l = sorted(q)
    ln = range(len(l))
    for x in ln:
        if len(l[x:]) > 1:
            for y in ln[x + 1:]:
                if (len(l[y:]) > 0) and (l[y] % l[x] == 0):
                    for z in ln[y + 1:]:
                        if l[z] % l[y] == 0:
                            ans += 1
    return ans

这个有点快:

def bar(q):
    l = sorted(q)
    ans = 0
    for x2, x in enumerate(l):
        pool = l[x2 + 1:]
        if len(pool) > 1:
            for y2, y in enumerate(pool):
                pool2 = pool[y2 + 1:]
                if pool2 and (y % x == 0):
                    for z in pool2:
                        if z % y == 0:
                            ans += 1
    return ans

这是我在你们的帮助下得出的结果，但我一定是做错了什么，因为它得到了错误的答案(虽然它真的很快):

def function4(numbers):
    ans = 0
    num_dict = {}
    index = 0
    for x in numbers:
        index += 1
        num_dict[x] = [y for y in numbers[index:] if y % x == 0]

    for x in numbers:
        for y in num_dict[x]:
            for z in num_dict[y]:
                print(x, y, z)
                ans += 1

    return ans

(39889 而不是 40888)- 哦，我不小心让索引变量从 1 而不是 0 开始。它现在可以工作了。

最终编辑

通过重新评估我需要它做的事情，我找到了查找三元组数量的最佳方法。该方法实际上并没有找到三元组，它只是对它们进行计数。

def foo(l):
    llen = len(l)
    total = 0
    cache = {}
    for i in range(llen):
        cache[i] = 0
    for x in range(llen):
        for y in range(x + 1, llen):
            if l[y] % l[x] == 0:
                cache[y] += 1
                total += cache[x]
    return total

这里有一个解释思考过程的函数版本(不适合大列表，因为垃圾打印):

def bar(l):
    list_length = len(l)
    total_triples = 0
    cache = {}
    for i in range(list_length):
        cache[i] = 0
    for x in range(list_length):
        print("\n\nfor index[{}]: {}".format(x, l[x]))
        for y in range(x + 1, list_length):
            print("\n\ttry index[{}]: {}".format(y, l[y]))
            if l[y] % l[x] == 0:
                print("\n\t\t{} can be evenly diveded by {}".format(l[y], l[x]))
                cache[y] += 1
                total_triples += cache[x]
                print("\t\tcache[{0}] is now {1}".format(y, cache[y]))
                print("\t\tcount is now {}".format(total_triples))
                print("\t\t(+{} from cache[{}])".format(cache[x], x))
            else:
                print("\n\t\tfalse")
    print("\ntotal number of triples:", total_triples)

Answer 1

现在你的算法有 O(N^3) 的运行时间，这意味着每次你将初始列表的长度加倍，运行时间就会增加 8 倍。

在最坏的情况下，您无法对此进行改进。例如，如果你的数字都是 2 的连续幂，这意味着每个数字都除以每个大于它的数字，那么每个数字的三元组都是一个有效的解决方案，所以仅仅打印出所有的解决方案就会像什么一样慢你现在正在做。

如果您有较低“密度”的数字除以其他数字，您可以做的一件事来加快速度是搜索数字对而不是三元组。这将花费仅 O(N^2) 的时间，这意味着当您将输入列表的长度加倍时，运行时间会增加 4 倍。一旦您有了数字对列表，就可以使用它来构建三元组列表。

# For simplicity, I assume that a number can't occur more than once in the list.
# You will need to tweak this algorithm to be able to deal with duplicates.

# this dictionary will map each number `n` to the list of other numbers
# that appear on the list that are multiples of `n`.
multiples = {}
for n in numbers:
   multiples[n] = []

# Going through each combination takes time O(N^2)
for x in numbers:
   for y in numbers:
     if x != y and y % x == 0:
         multiples[x].append(y)

# The speed on this last step will depend on how many numbers
# are multiples of other numbers. In the worst case this will
# be just as slow as your current algoritm. In the fastest case
# (when no numbers divide other numbers) then it will be just a
# O(N) scan for the outermost loop.
for x in numbers:
    for y in multiples[x]:
        for z in multiples[y]:
            print(x,y,z)

可能有更快的算法，它们也利用除法的代数特性，但在您的情况下，我认为 O(N^2) 可能足够快。