在程序中定义和初始化一个有序 int 数组(具有 20000 个元素/值域为[0, 20000))和 map<int,int>实例(具有 20000 个形如(1,1)和(2,2)的“键-值对”,键分别为“0”到“19999”,分别在数组和 map实例中查找值为 500, 1500, 2500,…, 10500, 11500,…, 19500 等 20 个数据。试着比较在不同的数据结构和应用不同的查找算法(有序数组可以用顺序查找也可用二分查找)所花费的不同时间。用 unordered_map 类替换 map 类后,重新测试查找时间。重建一个键序打乱的哈希表,测试其对查找操作的影响。
时间: 2024-02-13 16:03:51 浏览: 23
好的,这是一个关于数据结构和算法优化的问题。首先,我可以给你一些代码示例,来定义和初始化一个有序 int 数组和一个 map<int,int> 实例:
```cpp
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <chrono>
using namespace std;
int main() {
const int N = 20000;
int a[N];
map<int, int> m;
unordered_map<int, int> um;
// 初始化有序数组
for (int i = 0; i < N; i++) {
a[i] = i;
}
// 初始化 map 实例
for (int i = 0; i < N; i++) {
m[i] = i;
um[i] = i;
}
// 要查找的值
vector<int> keys = { 500, 1500, 2500, 3500, 4500, 5500, 6500, 7500, 8500, 9500, 10500, 11500, 12500, 13500, 14500, 15500, 16500, 17500, 18500, 19500 };
// 顺序查找有序数组
auto start = chrono::steady_clock::now();
for (int key : keys) {
for (int i = 0; i < N; i++) {
if (a[i] == key) {
break;
}
}
}
auto end = chrono::steady_clock::now();
cout << "顺序查找有序数组:" << chrono::duration_cast<chrono::microseconds>(end - start).count() << " us" << endl;
// 二分查找有序数组
start = chrono::steady_clock::now();
for (int key : keys) {
int l = 0, r = N - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] == key) {
break;
}
else if (a[mid] < key) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
}
end = chrono::steady_clock::now();
cout << "二分查找有序数组:" << chrono::duration_cast<chrono::microseconds>(end - start).count() << " us" << endl;
// 查找 map 实例
start = chrono::steady_clock::now();
for (int key : keys) {
m.find(key);
}
end = chrono::steady_clock::now();
cout << "查找 map 实例:" << chrono::duration_cast<chrono::microseconds>(end - start).count() << " us" << endl;
// 查找 unordered_map 实例
start = chrono::steady_clock::now();
for (int key : keys) {
um.find(key);
}
end = chrono::steady_clock::now();
cout << "查找 unordered_map 实例:" << chrono::duration_cast<chrono::microseconds>(end - start).count() << " us" << endl;
// 重建一个键序打乱的哈希表
random_shuffle(um.begin(), um.end());
// 查找打乱键序的 unordered_map 实例
start = chrono::steady_clock::now();
for (int key : keys) {
um.find(key);
}
end = chrono::steady_clock::now();
cout << "查找打乱键序的 unordered_map 实例:" << chrono::duration_cast<chrono::microseconds>(end - start).count() << " us" << endl;
return 0;
}
```
这段代码首先定义了一个长度为 20000 的有序 int 数组和一个 map<int,int> 实例,然后分别用顺序查找和二分查找算法在有序数组中查找 20 个数,用 map 实例和 unordered_map 实例分别查找同样的 20 个数。最后,通过打乱 unordered_map 实例的键序,测试其对查找操作的影响。
你可以在自己的编译器中运行这段代码,看看不同数据结构和不同查找算法所花费的时间。这个例子中使用了 C++ STL 中的 map 和 unordered_map 类,它们分别是基于红黑树和哈希表实现的关联容器。你也可以尝试使用其他语言或者自己实现相应的数据结构和算法来进行测试。
总体来说,有序数组的二分查找算法比顺序查找算法更快,因为前者的时间复杂度是 O(log n),后者的时间复杂度是 O(n)。在 map 和 unordered_map 实例中,哈希表的查找速度通常比红黑树快,因为哈希表的平均查找时间是常数级别的,而红黑树的平均查找时间是 O(log n)。但是,打乱键序的哈希表可能会导致哈希冲突增加,从而影响查找速度。