快速比较数组数

-20

我有int数组，我想看看有多少not 1号有：快速比较数组数

int* t = new int[50]; 
int counter = 1; 
for(int i = 0; i < 50; i++){ 
    t[i] = i % 10; 
    if((memcmp((void*)t[i], (void*)1, 4) != 0)){ 
     counter++; 
    } 
}

，但我得到adress violation。如何使它工作...快速工作。你知道更快的解决方案，不是标准解决方案。请不要t[i]==1。

编辑：因为我使用的大小362856427的数组中的计划，我想让它简单。

来源

2013-05-05 Yoda

um ...'if（t [i]！= 1）'。在这里使用'memcmp'是很奇怪的。 – Dave 2013-05-05 14:53:09

什么让你觉得“那个解决方案”（'t [i] == 1）不是最快的一个？ – dialer 2013-05-05 14:53:54

这个“不是那个解决方案”是关于t [i] == 1的。我不会，如果它是最快的我需要最快的请不要在这里聊天。 – Yoda 2013-05-05 14:54:29

您正在输入地址1。这意味着你在地址1比较，而不是1.你的解决方案将创建int one = 1;，然后将&one代替(void*)1。

来源

2013-05-05 14:54:18 unxnut

这工作，但对于大小'362856427'的数组它永远不会结束.. – Yoda 2013-05-05 15:02:00

@RobertKilar，A-它会结束...... B-它不会结束任何更快！ – 2013-05-05 15:06:18

我注意到另一个问题。你正在使用指向t [i]的指针。它应该改为（void *）（t + i）。另外，你的计数器应该初始化为0. – unxnut 2013-05-05 15:15:50

为什么不这样做：

int* t = new int[50]; 
int counter = 0; // <-- Shouldn't it be "0" at the beginning? 
for(int i = 0; i < 50; i++){ 
    if(t[i] != 1){ 
     counter++; 
    } 
}

来源

2013-05-05 14:56:53

TL; DR：这样做的明显的方式，并确保你的编译器优化它。

如果没有一个完整的，可重现的程序例子，很难对性能进行推理。所以让我们从一个简单的实现开始：

#include <array> 
#include <algorithm> 

std::array<int, 362856427> a = {}; 

int main() 
{ 
    a[500] = 1; 
    a[5000] = 1; 
    a[50000] = 1; 
    a[500000] = 1; 

    auto counter = 0u; 
    for (auto i = 0u; i < a.size(); ++i) { 
    if (a[i] != 1) 
     ++counter; 
    } 

    return counter != 362856423; 
}

时间这个，我得到了1.79秒的用户时间。然后我意识到自己的错误，并将-O3添加到我的编译命令中。这是更好的：

g++ -std=c++17 -g -Wall -Wextra -O3 16385733.cpp -o 16385733 
time ./16385733 
0.07user 0.08system 0:00.16elapsed 98%CPU (0avgtext+0avgdata 2212maxresident)k

我们可以尝试简化环路，但是这没有可测量的差异（优化已经击败了我们这一个）：

for (auto i = 0u; i < a.size(); ++i) 
    counter += a[i] != 1;

另一种方法是使代码更清晰，通过使用标准算法：

auto counter = a.size() - std::count(a.begin(), a.end(), 1);

这一直比明显循环长50％。

如果输入阵列大得多，你也许可以通过并行这样的计算获得：

 auto counter = 0ul; 
#pragma omp parallel for reduction(+:counter) 
    for (auto i = 0ul; i < a.size(); ++i) 
     counter += a[i] != 1;

我的基准测试表明这为作为标准算法慢，当数组大小为362856427 ，并没有更快，当它上升到3628564270.

有几种方法来重新写在等价形式：

for (auto i: a) 
     counter += i != 1;

for (auto p = a.data(); p < end; ++p) 
     counter += *p != 1;

所有这些都表现出类似的性能，而OpenMP并没有得到改进。

那么简单的答案是

做的明显的方式
请确保您的编译器优化和
基准的替代品。

来源

2017-04-05 10:09:31

快速比较数组数

回答

相关问题