c++ - 寻找除数对

Question

我正在尝试解决此练习 http://main.edu.pl/en/archive/amppz/2014/dzi而且我不知道如何提高我的代码的性能。当程序必须处理超过 500,000 个唯一数字(如描述中最多 2,000,000 个)时，就会出现问题。然后用 1-8 秒遍历所有这些数字。我使用的测试来自 http://main.edu.pl/en/user.phtml?op=tests&c=52014&task=1263 ，我通过命令测试它
program.exe < data.in > result.out

描述: You are given a sequence of <sub>n</sub> integer a<sub>1</sub>, a<sub>2</sub>, ... a<sub>n</sub>. You should determine the number of such ordered pairs(<sub>i</sub>, <sub>j</sub>), that <sub>i</sub>, <sub>j</sub> equeals(1, ..., <sub>n</sub>), <sub>i</sub> != <sub>j</sub> and a<sub>i</sub> is divisor of a<sub>j</sub>.<br/>
The first line of input contains one integer <sub>n</sub>(1 <= <sub>n</sub> <= 2000000)
The second line contains a sequence of <sub>n</sub> integers a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>(1 <= a<sub>i</sub> <= 2000000).<br/>
In the first and only line of output should contain one integer, denoting the number of pairs sought.<br/>
For the input data:
5
2 4 5 2 6<br/>
the correct answer is: 6<br/>
Explanation: There are 6 pars: (1, 2) = 4/2, (1, 4) = 2/2, (1, 5) = 6/2, (4, 1) = 2/2, (4, 2) = 4/2, (4, 5) = 6/2.


例如:
- 总共有 2M 个数字和 635k 个唯一数字，总共有 34500 万次迭代
- 总数2M，未求数200万，共迭代18.85亿次

#include <iostream>
#include <math.h>
#include <algorithm>

#include <time.h>


#define COUNT_SAME(count) (count - 1) * count


int main(int argc, char **argv) {
    std::ios_base::sync_with_stdio(0);

    int n; // Total numbers
    scanf("%d", &n);

    clock_t start, finish;
    double  duration;

    int minVal = 2000000;
    long long *countVect = new long long[2000001]; // 1-2,000,000; Here I'm counting duplicates

    unsigned long long counter = 0;
    unsigned long long operations = 0;

    int tmp;
    int duplicates = 0;

    for (int i = 0; i < n; i++) {
        scanf("%d", &tmp);

        if (countVect[tmp] > 0) { // Not best way, but works
            ++countVect[tmp];
            ++duplicates;
        } else {
            if (minVal > tmp)
                minVal = tmp;

            countVect[tmp] = 1;
        }
    }

    start = clock();

    int valueJ;
    int sqrtValue, valueIJ;
    int j;

    for (int i = 2000000; i > 0; --i) {
        if (countVect[i] > 0) { // Not all fields are setted up
            if (countVect[i] > 1) 
                counter += COUNT_SAME(countVect[i]); // Sum same values

            sqrtValue = sqrt(i);

            for (j = minVal; j <= sqrtValue; ++j) {
                if (i % j == 0) {
                    valueIJ = i / j;

                    if (valueIJ != i && countVect[valueIJ] > 0 && valueIJ > sqrtValue)
                        counter += countVect[i] * countVect[valueIJ];

                    if (i != j && countVect[j] > 0)
                        counter += countVect[i] * countVect[j];
                }

                ++operations;
            }
        }
    }

    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("Loops time: %2.3f", duration);
    std::cout << "s\n";
    std::cout << "\n\nCounter: " << counter << "\n";
    std::cout << "Total operations: " << operations;

    std::cout << "\nDuplicates: " << duplicates << "/" << n;
    return 0;
}  

我知道，一开始我不应该对数组进行排序，但我不知道如何以更好的方式进行排序。

任何提示都会很棒，谢谢!

这是改进后的算法 - 0.5 秒内生成 2M 个唯一数字。感谢@PJTraill!

#include <iostream>
#include <math.h>
#include <algorithm>

#include <time.h>


#define COUNT_SAME(count) (count - 1) * count


int main(int argc, char **argv) {
    std::ios_base::sync_with_stdio(0);

    int n; // Total numbers
    scanf("%d", &n);

    clock_t start, finish;
    double  duration;

    int maxVal = 0;
    long long *countVect = new long long[2000001]; // 1-2,000,000; Here I'm counting duplicates

    unsigned long long counter = 0;
    unsigned long long operations = 0;

    int tmp;
    int duplicates = 0;

    for (int i = 0; i < n; i++) {
        scanf("%d", &tmp);

        if (countVect[tmp] > 0) { // Not best way, but works
            ++countVect[tmp];
            ++duplicates;
        } else {
            if (maxVal < tmp)
                maxVal = tmp;

            countVect[tmp] = 1;
        }
    }

    start = clock();

    int j;
    int jCounter = 1;

    for (int i = 0; i <= maxVal; ++i) {
        if (countVect[i] > 0) { // Not all fields are setted up
            if (countVect[i] > 1)
                counter += COUNT_SAME(countVect[i]); // Sum same values

            j = i * ++jCounter;

            while (j <= maxVal) {
                if (countVect[j] > 0)
                    counter += countVect[i] * countVect[j];

                j = i * ++jCounter;
                ++operations;
            }

            jCounter = 1;
        }
    }

    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("Loops time: %2.3f", duration);
    std::cout << "s\n";
    std::cout << "\n\nCounter: " << counter << "\n";
    std::cout << "Total operations: " << operations;

    std::cout << "\nDuplicates: " << duplicates << "/" << n;
    return 0;
}

Answer 1

我希望以下算法比 OP 的算法(优化倾斜)运行得更快:

• (值的类型和频率应为 32 位无符号，计数为 64 位——如果您的语言不支持，则在计算计数之前进行提升。)
• 读取值的个数，N。
• 读取每个值 v，将其频率 freq[v] 加一(无需存储)。
  • (freq[MAX](或 MAX+1)可以静态分配，可能最优初始化为全 0)
• 从 freq[1] 和值的数量计算涉及 1 的对的数量。
• 对于 2..MAX 中的每个 i (freq[i] > 0):
  • 根据 freq[i] 计算对 (i,i) 的数量。
  • 对于 2m..MAX 中 i 的每个 m 倍数:
    • (使用 m 作为循环计数器并递增，而不是乘法)
    • 根据 freq[i] 和 freq[m] 计算 (i,m) 对的数量。
  • (如果 freq[i] = 1，可以省略 (i,i) 计算并执行针对 freq[i] = 1 优化的循环变体)
• (可以从 2..MAX/2 执行前一个(外部)循环，然后从 MAX/2+1..MAX 执行省略倍数处理)

对数 (i,i) = _freq[i]C₂ = ( freq[i] * (freq[ i] - 1) )/2 。
对数 (i,j) = freq[i] * freq[j] for i ≠ j.

这避免了排序、sqrt 和除法。

其他优化

可以存储不同的值，然后扫描该数组(顺序无关紧要)；由此产生的 yield 或损失取决于 1..MAX 中值的密度。

如果最大频率 < 2¹⁶，这听起来很有可能，所有产品都适合 32 位。可以通过使用数字类型作为模板编写函数、跟踪最大频率然后为其余部分选择适当的模板实例来利用这一点。这需要 N*(compare+branch) 并且可以通过使用 32 位而不是 64 位执行 D² 乘法来获得 yield ，其中 D 是不同值的数量。除了 N < 2¹⁶ 之外，我看不出有什么简单的方法可以推断出 32 位就足够了。

如果对 n 个处理器进行并行处理，可以让不同的处理器处理不同的残基模 n。

我考虑过跟踪偶数的数量，以避免扫描一半的频率，但我认为对于给定参数内的大多数数据集，这不会产生什么优势。