6

我有一个小问题，在 LARGE unsigned char 数组和仅包含 unsigned char 元素的向量中扫描某些元素的最快方法是什么？直接的答案会很棒，但深入详细的答案会很棒。我说的快是什么意思？基本上，至少在一秒钟内搜索某些字符。我知道这不是一个受过良好教育的定义...

注意：数组未排序。

共同声明：

unsigned char* Array = new unsigned char[ 50000 ];
std::vector< unsigned char > Vec( 50000 );
/*
 * Fill Array & Vec with random bytes
 */

可以说，我想在数组中搜索字母“a”，我只需编写这个循环来搜索它：

注意：搜索过程将搜索多个元素。主要是 256。因此，您可以利用这个神奇的数字。

For循环方法：

unsigned int Count = 0;
for ( unsigned int Index = 0; Index != 50000; ++ Index )
   if( Array[ Index ] == 'a' ) Count ++;

std::count 方法：

unsigned int Count = std::count ( Array, Array + 50000, 'a' );

有没有更快的方法来搜索 Array 中的某些元素？

一些想法 - 请不要为此给我一个大拇指！它只是一个想法。我想要一些意见。

排序

如果我们复制 Array 并对其进行排序，速度会更好吗？为什么要复制？好吧，因为我们需要保留原始内容。目标是基本上扫描并计算一个字符的出现次数。记住，速度很重要。这意味着，复制过程必须很快。

Answer: No and its not worth it!

为什么？好吧，让我们读一下：

@基里尔基洛夫：

依靠。如果您打算搜索单个字符 - 绝对不会。复制数组是一项昂贵的操作。对其进行排序 - 甚至更昂贵。

好吧，如果您只有一个数组并且您计划搜索 100 个不同的字符，那么这种方法可以为您提供更好的性能。现在，这实际上取决于您的使用情况。对于这种情况，没有人能给你绝对正确的答案。您需要运行它并配置文件。

*向下滚动到@Kiril Krov 的信息帖子以获取更多信息。

答案： 到目前为止，还没有一个可靠的或答案，因为没有一个真正“快速”的方法来实现这个目标，尤其是当它没有排序的时候。但是，线程可能是一种可能的解决方案。但是，请注意我们的 CPU！这是基于@Andrea 提交的答案（向下滚动以获取更多信息） - 我希望我没看错。

4

6 回答 6

5

正如其他人所写，最佳算法的复杂性是O(n)，尤其是因为您的数组未排序。

为了使搜索更快，您可以细分数组并在单独的线程中分别扫描每个部分。这将与您机器上可用的 CPU 内核数量成线性关系。

例如，如果您有四个可用内核，则生成四个线程并让每个线程扫描阵列的四分之一。

可能这个讨论可能会有所帮助：Using threads to reduce array search time

在任何情况下（对于任何与性能相关的问题都是如此），您应该分析您的代码。为您拥有的方法创建一个测试用例，测量它所花费的时间并将其作为基线。然后，对于您所做的每一次修改，重新进行测量以检查它是否真的可以缩短执行时间。还要确保每次测量不止一次（在同一个测试用例中）并计算平均值，以减少缓存和其他预热效应（理想情况下，在开始第一次测量之前至少执行一次代码）。

这是与 Java 相关的，但给出了一些很好的反馈，表明并行化并非在所有情况下都有意义：A Beginner´s Guide to Hardcore Concurrency

于 2013-03-21T08:08:23.313 回答
4

最好的算法是O(n)，其中n是元素的数量。

由于您需要检查每个元素，因此您必须遍历整个数组。

我能想到的简单方法已经写在您自己的答案中。

没有更快的方法可以做到这一点——内存是连续的，数组没有排序，你需要“触摸”每个元素。这是最快的解决方案。

关于您的编辑：使用std::count和“手动”循环遍历数组将为您提供相同的性能。

有没有更快的方法来搜索数组中的某些元素

是的，如果数组已排序。然后你可以达到O( log(n) ). 然后，您将需要一些现有的搜索算法，例如二进制搜索。

如果我们复制 Array 并对其进行排序，速度会不会更好

依靠。如果您打算搜索单个字符 - 绝对不会。复制数组是一项昂贵的操作。对其进行排序 - 甚至更昂贵。

好吧，如果您只有一个数组并且您计划搜索 100 个不同的字符，那么这种方法可以为您提供更好的性能。现在，这实际上取决于您的使用情况。对于这种情况，没有人能给你绝对正确的答案。您需要运行它并配置文件。

于 2013-03-21T08:05:41.383 回答
4

“快”是什么意思？

快于复杂性，还是作为常数的改进？您无法使用未排序的数组获得更好的复杂性。但是，如果您很少更改数组并且经常搜索它，您可以考虑在每次更改后对其进行排序，或者更好的是，使用不同的数据结构（如 amultimap或 a set）。

如果你打算在你的O(n)，有一些巧妙的技巧可以使用/滥用 CPU 的缓存。如果您搜索多个元素，通常会更快地搜索每个字符的前几百个数组元素，然后搜索接下来的几百个，依此类推，而不是为每个搜索词扫描整个数组。改进并不在于复杂性，因此效果通常不会那么好。除非此搜索发生在您在其他算法深处重复的瓶颈处，否则我不会推荐它。因此，除非它在渲染算法、设备驱动程序或特定架构等内部，否则很可能不值得。但是，在可能合适的极少数情况下，通过使用内联汇编和滥用 CPU 缓存，我看到速度提高了 3 倍 - 4 倍或更多。

编辑：

您的评论表明，包含有关数据结构的简短介绍可能是个好主意。

  • 数组，向量：访问速度最快，搜索速度较慢，如果未附加到末尾，则添加/删除速度较慢。
  • 列表：访问慢、搜索慢、添加/删除最快
  • 树，哈希表等：最佳搜索（有些允许O(0)搜索！），变化缓慢（取决于类型）

我建议学习 C++ 中的不同数据结构（向量、列表、映射、多重映射、集合、多重集合等），这样您就可以使用最适合您需求的一种。

关于 CPU 缓存：似乎选择更合适的数据结构和代码组织更为重要。但是，为了完整起见，我将其包括在内。如果您以较短的块而不是一次搜索整个数组，则该部分数组将添加到 CPU 的缓存中，并且访问缓存比访问 RAM 快得多。因此，您可以处理较小的数据块（例如，搜索多个元素），然后切换到下一个数据块，依此类推。这意味着，例如，

search "a" in elements 1..100
search "b" in elements 1..100
search "c" in elements 1..100
search "a" in elements 101..200
search "b" in elements 101..200
search "c" in elements 101..200
...
search "c" in elements 999901 .. 1000000

可以比

search "a" in elements 1..1000000
search "b" in elements 1..1000000
search "c" in elements 1..1000000

如果搜索到的元素（a、b、c、..）的数量足够大。为什么？因为在缓存大小为 100 的情况下，在第一个示例中，数据从 RAM 读取 10000 次，在第二个示例中，为 30000 次。

但是，这种效率（以及您对数据块大小的选择）在很大程度上取决于您的架构，并且仅在您确定这是您真正的瓶颈时才推荐使用。通常不是。

于 2013-03-21T08:32:25.713 回答
3

取决于它是一次扫描或多次。排序对扫描速度有很大帮助，您始终可以通过 bisearch 缩小扫描范围。复杂度可能是 O(log(n))。

或者，如果您可以从插入开始并构建将要扫描的数组，则可以使用插入速度慢但始终排序的红黑树。

最后但并非最不重要的一点是，对于您正在扫描“无符号字符数组”的问题，其中元素的数量是有限的。您可以进行一次扫描，但它需要更多内存：使用 unsigned char 数组中每个元素的值作为另一个数组的索引，该数组用于存储扫描结果。

如果你想要每个元素的位置，另一个数组可以是：int scanresult[256][n]，其中 n 是某个字符数的最大数。

如果只需要计算数组中有多少个'a'，另一个数组可以是：int scanresult[256]，以此为例，复杂度为O(n)，但只需要运行一次：

unsigned char* Array = new unsigned char[ 50000 ];
/* Fill Array */
int scanresult[256];
for ( int i=0;i<256;++i) { scanresult[i]=0; }
for ( unsigned int Index = 0; Index != 50000; ++ Index )
   scanresult[Array[Index]]++;
于 2013-03-21T08:40:31.970 回答
2

对于单个字符搜索，std::count可能与您将获得的一样快。而对于小数据集（和 50000） 来说，你不太可能注意到时间。当然，对于单个字符，几乎任何合理的算法都将花费比读取数据更少的时间。（std::count在现代机器上，向量或 C 样式数组中的 50000 个元素几乎是瞬时的。无论如何，您的“至少一秒钟”要好几个数量级。）

如果您想更快，解决方案是不要一开始就创建数组，而是在读取数据时动态进行处理（或通过 立即获取数组 mmap）。如果您需要多个字符的数据......只需在读取数据时建立一个字符频率表。并找到读取数据的最快方法（mmap在 Linux 下几乎可以肯定，至少根据我最近制定的一些措施）。之后，只需在需要计数时索引到该表。读取数据将是 O(n)（并且没有办法解决），但在那之后，获得计数是 O(1)，并且具有非常非常小的常数因子（在很多机器上不到一纳秒）。

于 2013-03-21T09:05:17.600 回答
0

别忘了，unsigned char > 0 && unsigned char <= 256...

#define MAX 50000 

unsigned char* Array = new unsigned char[ MAX ];
unsigned int Logs[ 256 ];

// Fill Array

::memset( &Logs, 0, sizeof( Logs ) * 256 );
for( unsigned int Index = 0; Index != MAX; ++ Index )
   Logs[ Array[ Index ] ] ++;

delete [] Logs;
于 2013-03-21T08:51:52.540 回答