对于操作count()来说，std::set和std::unordered_set哪个更快？

10 浏览
0 Comments

对于操作count()来说，std::set和std::unordered_set哪个更快？

假设sizeof(void*) == sizeof(size_t)，并且将指针哈希化只是将其转换为size_t。所以我想知道如果我的集合中包含一个元素，哪个更快std::set还是std::unordered_set？

我知道std::set是如何工作的，但我不熟悉std::unordered_set。嗯，我知道无序集使用哈希和桶，如果没有交集发生（这是我的情况），复杂度是O(1)。但我不知道这个常数复杂度有多大。

如果容器中的数据量相关，我的实际情况使用的少于一百¹。但我的好奇心涉及到有少量元素和大量元素的两种情况。

¹ 元素的数量很少，即使是一个std::vector也能正常运行。

0

2 答案

0 Comments

在这个问题中，我们需要比较使用std::set和std::unordered_set哪个更快，来进行操作count()的计数。这个问题的出现是因为unordered_set在许多实现中具有比set更好的缓存局部性。但是由于在这种情况下元素数量很小，一个vector很可能能够完全适应缓存，这使得它成为更好的选择，尽管查找元素的复杂度为O(n)。

为了解决这个问题，我们可以使用以下代码来进行测试和比较：

#include

#include

#include

#include

#include

int main() {

const int SIZE = 1000000;

std::vector vec(SIZE);

std::set set;

std::unordered_set unordered_set;

// Initialize vector, set, and unordered_set with random values

for (int i = 0; i < SIZE; i++) {

vec[i] = reinterpret_cast(i);

set.insert(vec[i]);

unordered_set.insert(vec[i]);

}

// Test the operation count() for set

auto start_time_set = std::chrono::high_resolution_clock::now();

int count_set = set.count(vec[SIZE - 1]);

auto end_time_set = std::chrono::high_resolution_clock::now();

std::chrono::duration elapsed_time_set = end_time_set - start_time_set;

// Test the operation count() for unordered_set

auto start_time_unordered_set = std::chrono::high_resolution_clock::now();

int count_unordered_set = unordered_set.count(vec[SIZE - 1]);

auto end_time_unordered_set = std::chrono::high_resolution_clock::now();

std::chrono::duration elapsed_time_unordered_set = end_time_unordered_set - start_time_unordered_set;

// Print the results

std::cout << "count() for set: " << count_set << " (elapsed time: " << elapsed_time_set.count() << "s)" << std::endl;

std::cout << "count() for unordered_set: " << count_unordered_set << " (elapsed time: " << elapsed_time_unordered_set.count() << "s)" << std::endl;

return 0;

}

通过以上代码，我们可以测试并比较使用std::set和std::unordered_set进行count()操作的性能。测试中，我们首先初始化一个包含1000000个随机值的vector，并使用这些值分别填充set和unordered_set。然后，我们通过调用count()函数来计算set和unordered_set中某个特定元素的数量，并计算操作所花费的时间。

最后，我们将set和unordered_set中count()操作的结果和所花费的时间打印出来，以便比较它们之间的性能差异。

通过以上的文章，我们可以了解到在这个问题中，我们想要比较使用std::set和std::unordered_set哪个更快来进行操作count()的计数。并且给出了解决这个问题的代码示例。

0
0 Comments

在这段内容中，讨论了在使用count()操作时，std::set和std::unordered_set哪个更快的问题。问题的出现是因为作者提到了“元素数量很少，甚至std::vector都可以很好地执行”。然后，作者解释了std::vector相对于std::set和std::unordered_set更友好的缓存性能，因为它将元素分配在内存的连续区域中。虽然对于std::vector来说，查找和插入的复杂度比std::set和std::unordered_set更差（分别是线性和对数级的和摊销的常数级），但数据局部性和更高的缓存命中率很可能主导计算复杂度，并产生更好的性能。然而，选择的数据结构对性能的影响也取决于要执行的操作类型和频率，这在帖子中没有提到。作者建议在选择之前先进行测试，如果没有证据表明某种设计成为了阻碍应用程序满足性能要求的瓶颈，那么始终倾向于更简单的设计。

另外，某些情况下如果插入操作很少而查找操作很频繁，可以使用排序的std::vector结构，通过使用std::binary_search进行查找和插入，这样可以实现O(log n)的复杂度和具有缓存局部性的查找，以及O(n)的复杂度的插入。

总之，为了回答问题“在count()操作中，std::set和std::unordered_set哪个更快”，需要考虑到元素数量、数据局部性、缓存命中率、操作类型和频率等因素，并且建议在选择之前进行测试。

0