-
Notifications
You must be signed in to change notification settings - Fork 0
/
test_fast_sorted_mask.m
328 lines (275 loc) · 10.9 KB
/
test_fast_sorted_mask.m
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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
addpath(genpath('bin'))
%% compare the performance
data=sort(rand(1e7,1));
fprintf('comparing the performance for a 10^(%.1f) long vector\n',log10(numel(data)))
min_val=0.9;
max_val=0.91;
tic; mask=data<max_val & data>min_val; %the brute way
time_brute=toc;
subdata1=sort(data(mask));
fprintf('time for brute mask = %.2fms\n',time_brute*1e3)
tic;mask_idx=fast_sorted_mask(data,min_val,max_val);
time_search=toc;
subdata2=data(mask_idx(1):mask_idx(2));
fprintf('time for fast_sorted_mask = %.2fms\n',time_search*1e3)
logic_str = {'FAIL', 'pass'};
fprintf('Results equal test : %s \n',logic_str{isequal(subdata1,subdata2)+1})
fprintf('Speedup test : %s \n',logic_str{(time_search<time_brute)+1})
fprintf('Speedup by 5x test : %s \n',logic_str{(time_search<time_brute*0.2)+1})
%% show how it breaks when not sorted
data=rand(1e7,1);
min_val=0.9;
max_val=0.92;
mask=data<max_val & data>min_val;
subdata1=sort(data(mask));
mask_idx=fast_sorted_mask(data,min_val,max_val);
subdata2=sort(data(mask_idx(1):mask_idx(2)));
fprintf('TEST:unsorted data check ok? (fail is normal): %s \n',logic_str{isequal(subdata1,subdata2)+1})
%% see how it deals with values on the edge
data=(0:0.025:1);
min_val=0.4;
max_val=0.5;
mask=data<max_val & data>min_val;
subdata1=data(mask);
mask_idx=fast_sorted_mask(data,min_val,max_val);
subdata2=sort(data(mask_idx(1):mask_idx(2)));
fprintf('TEST:Edge 1 : %s \n',logic_str{isequal(subdata1,subdata2)+1})
min_val=0;
max_val=0.5;
mask=data<max_val & data>min_val;
subdata1=data(mask);
mask_idx=fast_sorted_mask(data,min_val,max_val);
subdata2=sort(data(mask_idx(1):mask_idx(2)));
fprintf('TEST:Edge 2 : %s \n',logic_str{isequal(subdata1,subdata2)+1})
min_val=0;
max_val=1;
mask=data<max_val & data>min_val;
subdata1=data(mask);
mask_idx=fast_sorted_mask(data,min_val,max_val);
subdata2=sort(data(mask_idx(1):mask_idx(2)));
fprintf('TEST:Edge 3 : %s \n',logic_str{isequal(subdata1,subdata2)+1})
min_val=0;
max_val=1-eps;
mask=data<max_val & data>min_val;
subdata1=data(mask);
mask_idx=fast_sorted_mask(data,min_val,max_val);
subdata2=sort(data(mask_idx(1):mask_idx(2)));
fprintf('TEST:Edge 4 : %s \n',logic_str{isequal(subdata1,subdata2)+1})
%% Check the behaviour when the no counts are in the limits
min_val=-1;
max_val=-0.5;
data=linspace(0,1,1e2);
mask=data<max_val & data>min_val;
subdata1=data(mask);
mask_idx=fast_sorted_mask(data,min_val,max_val);
subdata2=sort(data(mask_idx(1):mask_idx(2)));
fprintf('TEST: nothing in limits lower : %s \n',logic_str{isequal(subdata1,subdata2)+1})
min_val=-1;
max_val=0;
data=linspace(0,1,1e2);
mask=data<max_val & data>min_val;
subdata1=data(mask);
mask_idx=fast_sorted_mask(data,min_val,max_val);
subdata2=sort(data(mask_idx(1):mask_idx(2)));
fprintf('TEST: limits on lower edge : %s \n',logic_str{isequal(subdata1,subdata2)+1})
min_val=2;
max_val=3;
data=linspace(0,1,1e2);
mask=data<max_val & data>min_val;
subdata1=data(mask);
mask_idx=fast_sorted_mask(data,min_val,max_val);
subdata2=sort(data(mask_idx(1):mask_idx(2)));
fprintf('TEST: nothing in limits upper : %s \n',logic_str{isequal(subdata1,subdata2)+1})
min_val=1;
max_val=2;
data=linspace(0,1,1e2);
mask=data<max_val & data>min_val;
subdata1=data(mask);
mask_idx=fast_sorted_mask(data,min_val,max_val);
subdata2=sort(data(mask_idx(1):mask_idx(2)));
fprintf('TEST: limits on upper edge : %s \n',logic_str{isequal(subdata1,subdata2)+1})
%%
%Should find the time for counting and returning as seprate plots
fprintf('comparing the scaling of the methods \n')
points_list=round(logspace(3.5,8.5,400)); %values of n to investigate
%set up the output arrays
iimax=numel(points_list);
time_sort=nan(1,iimax);
time_unsorted_brute=nan(iimax,3);
time_presorted_brute=time_unsorted_brute; %these should be the same
time_presorted_search=time_unsorted_brute;
last_update=posixtime(datetime('now')); %time for updating plots every few seconds
tic
sfigure(1);
clf
set(gcf,'color','w')
set(gcf, 'Units', 'pixels', 'Position', [100, 100, 1600, 900])
plot_colors=parula(5+1); %padd the colors to avoid yellow
min_val=0.89;
max_val=0.9;
m_val=1*10^(2); %compare the scaled speed if you repeat the search m times after a single sort
% min,max=[0.1,0.2]
fprintf(' \n%03u',0)
for ii=1:iimax
fprintf('\b\b\b%03u',ii)
unsorted_data=rand(points_list(ii),1);
tic;
mask=unsorted_data<max_val & unsorted_data>min_val;
time_unsorted_brute(ii,1)=toc;
count_unsorted_brute=sum(mask);
time_unsorted_brute(ii,2)=toc;
subdata1=unsorted_data(mask);
time_unsorted_brute(ii,3)=toc;
time_unsorted_brute(ii,2:3)=time_unsorted_brute(ii,2:3)-time_unsorted_brute(ii,1);
subdata1=sort(subdata1);%need to sort this for comparing later
tic;
sorted_data=sort(unsorted_data);
time_sort(ii)=toc;
tic;
mask_idx=fast_sorted_mask(sorted_data,min_val,max_val);
time_presorted_search(ii,1)=toc;
count_presorted_search=mask_idx(2)-mask_idx(1)+1;
time_presorted_search(ii,2)=toc;
subdata2=sorted_data(mask_idx(1):mask_idx(2));
time_presorted_search(ii,3)=toc;
time_presorted_search(ii,2:3)=time_presorted_search(ii,2:3)-time_presorted_search(ii,1);
tic;
mask=sorted_data<max_val & sorted_data>min_val;
time_presorted_brute(ii,1)=toc;
count_presorted_brute=mask_idx(2)-mask_idx(1)+1;
time_presorted_brute(ii,2)=toc;
subdata3=sorted_data(mask);
time_presorted_brute(ii,3)=toc;
time_presorted_brute(ii,2:3)=time_presorted_brute(ii,2:3)-time_presorted_brute(ii,1);
if ~isequal(subdata1,subdata2,subdata3) || ~isequal(count_unsorted_brute,count_presorted_search,count_presorted_brute)
error('not the same')
end
ptime=posixtime(datetime('now'));
if ptime-last_update>2 || ii==iimax
sfigure(1);
subplot(2,1,1)
loglog(points_list,...
time_unsorted_brute(:,1)+time_unsorted_brute(:,2),'color',plot_colors(1,:))
hold on
loglog(points_list,...
time_presorted_brute(:,1)+time_presorted_brute(:,2),'color',plot_colors(2,:))
loglog(points_list,...
time_sort'+time_presorted_brute(:,1)+time_presorted_brute(:,2),'color',plot_colors(3,:))
loglog(points_list,...
time_presorted_search(:,1)+time_presorted_search(:,2),'color',plot_colors(4,:))
loglog(points_list,...
(time_sort'+(time_presorted_search(:,1)+time_presorted_search(:,2))...
*m_val)/m_val,'color',plot_colors(5,:))
legend('unsorted brute mask','presorted brute mask',...
'sort then fast\_sorted\_mask','presorted fast\_sorted\_mask',...
[sprintf('sort then 10^{%.1f}*',log10(m_val)),...
'fast\_sorted\_mask (scaled)'],'Location','northwest')
hold off
xlabel('Vector Size(n)');
ylabel('Execution Time');
title('Return Mask Count')
subplot(2,1,2);
loglog(points_list,...
time_unsorted_brute(:,1)+time_unsorted_brute(:,3),'color',plot_colors(1,:))
hold on
loglog(points_list,...
time_presorted_brute(:,1)+time_presorted_brute(:,3),'color',plot_colors(2,:))
loglog(points_list,...
time_sort'+time_presorted_brute(:,1)+time_presorted_brute(:,3),'color',plot_colors(3,:))
loglog(points_list,...
time_presorted_search(:,1)+time_presorted_search(:,3),'color',plot_colors(4,:))
loglog(points_list,...
(time_sort'+(time_presorted_search(:,1)+time_presorted_search(:,3))...
*m_val)/m_val,'color',plot_colors(5,:))
legend('unsorted brute mask','presorted brute mask',...
'sort then fast\_sorted\_mask','presorted fast\_sorted\_mask',...
[sprintf('sort then 10^{%.1f}*',log10(m_val)),...
'fast\_sorted\_mask (scaled)'],'Location','northwest')
hold off
xlabel('Vector Size(n)');
ylabel('Execution Time');
title('Return Mask Values')
pause(1e-6)
last_update=ptime;
end
end
figure(1)
fprintf('\n')
saveas(gcf,'fig1.png')
%% how many repeats?
%note this will depend on the min/max that is chosen
%from above we can see that the sort then search method
% O ~ nlog(n) +2 log(n)
%vs the brute mask
% O ~ 2n
%can never compensate for the sort time, however if we are sorting once and then doing m operations
%we can win back a speedup for large enough m
% O ~ nlog(n) + 2 m log(n)
% O ~ 2n m
%solving
%time_sort + m*time_presorted_search=m*time_unsorted_brute
%time_sort =m*time_unsorted_brute-m*time_presorted_search
%time_sort/(time_unsorted_brute-time_presorted_search) =m
counts_or_values=0;
c_or_v_idx=2+counts_or_values;
n_desired=10^(7);
sfigure(2);
clf
set(gcf,'color','w')
set(gcf, 'Units', 'pixels', 'Position', [100, 100, 1600, 900])
subplot(2,2,1)
loglog(points_list,...
(time_presorted_search(:,1)+time_presorted_search(:,c_or_v_idx))./...
(time_presorted_brute(:,1)+time_presorted_brute(:,c_or_v_idx)),'color','k')
title('Rel. Time(Exc. Sort) fast\_sorted\_mask/brute mask')
ylabel('Relative Execution Time')
xlabel('Vector Size(n)');
subplot(2,2,2)
set(gcf,'color','w')
m_list=10.^(1:.5:4);
rel_times=arrayfun(@(m) (time_sort' + ...
m.*(time_presorted_search(:,1)+time_presorted_search(:,c_or_v_idx)))...
./ (m.*(time_unsorted_brute(:,1)+time_unsorted_brute(:,c_or_v_idx))),m_list,'UniformOutput',0);
plot_colors=parula(numel(m_list)+1);
if numel(rel_times)
for ii=1:numel(rel_times)
loglog(points_list,rel_times{ii},'color',plot_colors(ii,:))
if ii==1, hold on ,end
end
end
lgd=legend(arrayfun(@(x) sprintf('m=10^{%.1f}',x),log10(m_list),'UniformOutput',0),...
'Location','West');
xlabel('Vector Size (n)');
ylabel('Relative Execution Time')
title('Rel. Time sort+m*fast\_sorted\_mask/ m*brute mask')
yl=ylim;
ylim([yl(1),2])
hold off
%now lets calculate the win factor for some values of m repeated masks
% relative time=(time_sort + m*time_presorted_search) / m*time_unsorted_brute
subplot(2,2,3)
m_crossover=time_sort'...
./((time_unsorted_brute(:,1)+time_unsorted_brute(:,c_or_v_idx))-...
(time_presorted_search(:,1)+time_presorted_search(:,c_or_v_idx)));
semilogx(points_list,m_crossover,'color','k')
%yl=ylim;
ylim([0,50]);
xlabel('Vector Size (n)');
ylabel('Repeated Uses (m)')
title('Repeated uses (m) for sort+fast\_sorted\_mask to win over brute mask');
subplot(2,2,4)
set(gcf,'color','w')
m_list=logspace(0,6,100);
[~,n_idx]=min(abs(points_list-n_desired));
n_actual=points_list(n_idx);
rel_times=(time_sort(n_idx) + m_list.*...
(time_presorted_search(n_idx,1)+time_presorted_search(n_idx,c_or_v_idx)))./...
(m_list.*...
(time_unsorted_brute(n_idx,1)+time_unsorted_brute(n_idx,c_or_v_idx))');
plot_colors=parula(numel(m_list));
loglog(m_list,rel_times,'color','k')
xlabel('Repeated Uses (m)');
ylabel('Relative Execution Time');
title(sprintf('Rel. Time Inc. Sort for n=10^{%.1f}',log10(n_actual)))
hold off
saveas(gcf,sprintf('fig%u.png',counts_or_values+2))