-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtemplate.cpp
More file actions
140 lines (129 loc) · 3.38 KB
/
Copy pathtemplate.cpp
File metadata and controls
140 lines (129 loc) · 3.38 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/****************************************************************
* 源代码中包含
* 1. 指针函数类型的使用
* 2. 使用指针函数时，测试程序的调用实现，为后面多种方案的测试提供了参考
*
**/
#include <iostream>
#include <assert.h>
#include <string.h>
#include <time.h>
#include <algorithm>
#include <vector>
#include <queue>
using std::priority_queue;
#define RANDMAX 0x7FFFFFFFF
#define FUNC_PARAM std::vector<int>& test_arr, const int size, int k
typedef std::vector<int>(*PF_RET_VOID)(FUNC_PARAM);
void test_all(PF_RET_VOID p, int n, int k);
#include <sys/time.h>
static long get_current_time()
{
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec * 1000000 + tv.tv_usec;
}
// Time is O(n) + O(nlogn) = O(nlogn))
std::vector<int> min_k_num_sort (FUNC_PARAM)
{
std::cout << __FUNCTION__;
sort(test_arr.begin(), test_arr.end());
std::vector<int> result(test_arr.begin(), test_arr.begin()+k);
return result;
}
//(n-k)k = O(nk)
std::vector<int> min_k_num_select(FUNC_PARAM)
{
std::cout << __FUNCTION__;
// init knum to save the result
std::vector<int> knum(k, 0);
int kmax = 0;
int index = -1;
// init kmin with the input vector's pre kth elements
// mean while get the max element in [0..k-1] and its index
for (int i = 0; i < k; ++i)
{
knum[i] = test_arr[i];
if (test_arr[i] > kmax)
{
kmax = test_arr[i];
index = i;
}
}
for(int i = k; i< test_arr.size(); ++i)
{
if(test_arr[i] > kmax)
{
knum[index] = test_arr[i];
kmax = test_arr[i];
// select max number again
for (int ki = 0; ki < k; ++ki)
{
if (knum[ki] > kmax)
{
kmax = knum[ki];
index = ki;
}
}
}
}
return knum;
}
// Time is O(nlogn)
std::vector<int> min_k_num_maxheap (FUNC_PARAM)
{
std::cout << __FUNCTION__;
std::priority_queue<int> kheap;
for (int i = 0; i < k; ++i)
{
kheap.push(test_arr[i]);
}
for (int i = k; i < test_arr.size(); ++i)
{
if(kheap.top() > test_arr[i])
{
kheap.pop();
kheap.push(test_arr[i]);
}
}
std::vector<int> result(k, 0);
for (int i = k-1; i >=0; --i)
{
result[i]= kheap.top();
kheap.pop();
}
return result;
}
int main(int argc, char const *argv[])
{
const int size = 10000000;
test_all(min_k_num_sort, size, 10);
test_all(min_k_num_select, size, 10);
test_all(min_k_num_maxheap, size, 10);
return 0;
}
void test_all(PF_RET_VOID p, int n, int k)
{
clock_t start, finish;
srand(0);
std::vector<int> test_arr(n, 0);
for(int i = 0; i < n; ++i) test_arr[i] = rand()%RANDMAX;
#ifdef OUTPUT
for (std::vector<int>::iterator i = test_arr.begin(); i != test_arr.end(); ++i)
{
std::cout << (*i) << " ";
}
#endif
std::cout << std::endl;
start = clock();
std::vector<int> v =(*p)(test_arr, n, k);
finish = clock();
double totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
std::cout << " TEST USING:" << totaltime << "s"<<std::endl;
#ifdef OUTPUT
for (std::vector<int>::iterator i = v.begin(); i != v.end(); ++i)
{
std::cout << (*i) << " ";
}
#endif
}