在列表中查找因素的最有效方法是什么？ [英] What's the most efficient way to find factors in a list?

问题描述

我需要做一个函数，给定一个正整数列表（可以有重复的整数），将所有三元组（在列表中），其中第三个数字是第二个的倍数，第二个是第一个的倍数：

I need to make a function that, given a list of positive integers (there can be duplicate integers), counts all triples (in the list) in which the third number is a multiple of the second and the second is a multiple of the first:

（同一数字不能使用两次

(The same number cannot be used twice in one triple, but can be used by all other triples)

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

For example, [3, 6, 18] is one because 18 goes evenly into 6 which goes evenly into 3.

因此，给定 [1、2、3、4、5、6] ：

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

并返回 3 （找到的三元组数）

and return 3 (the number of triples it found)

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

I made a couple of functions that work but are not efficient enough. Is there some math concept I don't know about that would help me find these triples faster? A module with a function that does better? I don't know what to search for...

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

这是我在所有人的帮助下想出的，但我必须做错什么，因为它得到的答案是错误的（虽然速度确实很快）：

Here's what I've come up with with help from y'all but I must be doing something wrong because it get's the wrong answer (it's really fast though):

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 ）-哦，我知道计数使索引var从1而不是0开始。现在可以使用。

(39889 instead of 40888) - oh, I accidentally made the index var start at 1 instead of 0. It works now.

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

I've found the best way to find the number of triples by reevaluating what I needed it to do. This method doesn't actually find the triples, it just counts them.

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

这是解释思维过程的函数（由于垃圾邮件打印，不适用于庞大的列表）：

And here's a version of the function that explains the thought process as it goes (not good for huge lists though because of spam prints):

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)

推荐答案

关键见解是：

如果 a 除以 b ，则表示 a 适合 b 。
如果 a 不除 c ，则表示 a 不适合 c 。
并且如果 a 不适合 c ，则 b 不适合 c （想象如果 b 放入 c ，由于 a 放入 b ，则 a 适合所有适合 c 的 b ，因此 a 也必须适合 c 。 （想想分解因数等）

if a divides b, it means a "fits into b". if a doesn't divide c, then it means "a doesn't fit into c". And if a can't fit into c, then b cannot fit into c (imagine if b fitted into c, since a fits into b, then a would fit into all the b's that fit into c and so a would have to fit into c too.. (think of prime factorisation etc))

这意味着我们可以进行优化。如果我们将数字从小到大排序，然后从小数字开始。第一次迭代，以最小的数字 a
开始。如果将数字分为两组，则分组为 1 ，即 a 除，然后将 2 分组为 a 不进行分组的组，那么我们知道组 1 中没有数字可以将组中的数字除 2 ，因为组 2 中没有数字包含 a 。

this means that we can optimise. If we sort the numbers smallest to largest and start with the smaller numbers first. First iteration, start with the smallest number as a If we partition the numbers into two groups, group 1, the numbers which a divides, and group 2 the group which a doesn't divide, then we know that no numbers in group 1 can divide numbers in group 2 because no numbers in group 2 have a as a factor.

所以如果我们有[2,3,4,5,6,7]，我们将从2开始并得到：
[2,4,6]和[3,5,7]
我们可以在每个组上重复该过程，分成较小的组。这表明算法可以更有效地计算三元组。这些小组很快就会变得非常小，这意味着其效率应该与产出的规模相当接近。

so if we had [2,3,4,5,6,7], we would start with 2 and get: [2,4,6] and [3,5,7] we can repeat the process on each group, splitting into smaller groups. This suggests an algorithm that could count the triples more efficiently. The groups will get really small really quickly, which means its efficiency should be fairly close to the size of the output.

这篇关于在列表中查找因素的最有效方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！