VM2D 1.14
Vortex methods for 2D flows simulation
Loading...
Searching...
No Matches
knnCPU.cpp
Go to the documentation of this file.
1/*--------------------------------*- VM2D -*-----------------*---------------*\
2| ## ## ## ## #### ##### | | Version 1.14 |
3| ## ## ### ### ## ## ## ## | VM2D: Vortex Method | 2026/03/06 |
4| ## ## ## # ## ## ## ## | for 2D Flow Simulation *----------------*
5| #### ## ## ## ## ## | Open Source Code |
6| ## ## ## ###### ##### | https://www.github.com/vortexmethods/VM2D |
7| |
8| Copyright (C) 2017-2026 I. Marchevsky, K. Sokol, E. Ryatina, A. Kolganova |
9*-----------------------------------------------------------------------------*
10| File name: knnCPU.cpp |
11| Info: Source code of VM2D |
12| |
13| This file is part of VM2D. |
14| VM2D is free software: you can redistribute it and/or modify it |
15| under the terms of the GNU General Public License as published by |
16| the Free Software Foundation, either version 3 of the License, or |
17| (at your option) any later version. |
18| |
19| VM2D is distributed in the hope that it will be useful, but WITHOUT |
20| ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
21| FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
22| for more details. |
23| |
24| You should have received a copy of the GNU General Public License |
25| along with VM2D. If not, see <http://www.gnu.org/licenses/>. |
26\*---------------------------------------------------------------------------*/
27
41#include "knnCPU.h"
42
43#include <algorithm>
44
45namespace knnNew
46{
47
48 const int twoPowCodeLengthVar = (1 << codeLength);
49
50
51
52 //"Разрежение" двоичного представления беззнакового целого, вставляя по одному нулику между всеми битами
53 unsigned int ExpandBits(unsigned int v)
54 {
55 // вставит 1 нуль
56 v = (v | (v << 8)) & 0x00FF00FF; // 00000000`00000000`abcdefgh`ijklmnop
57 // | 00000000`abcdefgh`ijklmnop`00000000
58 // = 00000000`abcdefgh`XXXXXXXX`ijklmnop
59 // & 00000000`11111111`00000000`11111111
60 // = 00000000`abcdefgh`00000000`ijklmnop
61
62 v = (v | (v << 4)) & 0x0F0F0F0F; // 00000000`abcdefgh`00000000`ijklmnop
63 // | 0000abcd`efgh0000`0000ijkl`mnop0000
64 // = 0000abcd`XXXXefgh`0000ijkl`XXXXmnop
65 // & 00001111`00001111`00001111`00001111
66 // = 0000abcd`0000efgh`0000ijkl`0000mnop
67
68 v = (v | (v << 2)) & 0x33333333; // 0000abcd`0000efgh`0000ijkl`0000mnop
69 // | 00abcd00`00efgh00`00ijkl00`00mnop00
70 // = 00abXXcd`00efXXgh`00ijXXkl`00mnXXop
71 // & 00110011`00110011`00110011`00110011
72 // = 00ab00cd`00ef00gh`00ij00kl`00mn00op
73
74 v = (v | (v << 1)) & 0x55555555; // 00ab00cd`00ef00gh`00ij00kl`00mn00op
75 // | 0ab00cd0`0ef00gh0`0ij00kl0`0mn00op0
76 // = 0aXb0cXd`0eXf0gXh`0iXj0kXl`0mXn0oXp
77 // & 01010101`01010101`01010101`01010101
78 // = 0a0b0c0d`0e0f0g0h`0i0j0k0l`0m0n0o0p
79 return v;
80 }
81
82
83 //Мортоновский код для пары из чисел типа double
84 //Исходное число - строго в диапазоне [0, 1 / (1.0 + 1/(2^codeLength - 1) ))
85 unsigned int Morton2D(const Point2D& r)
86 {
87 const Point2D& rscale = twoPowCodeLengthVar * r;
88 const unsigned int& xx = ExpandBits((unsigned int)(rscale[0]));
89 const unsigned int& yy = ExpandBits((unsigned int)(rscale[1]));
90 return yy | (xx << 1);
91 }
92
93
95 void RSort_Parallel(TParticleCode* m, TParticleCode* m_temp, unsigned int n, unsigned int* s)
96 {
97 if (n == 0)
98 return;
99 // Количество задействованных потоков
100 unsigned char threads = omp_get_max_threads();
101 //std::cout << "threads = " << (int)threads << std::endl;
102
103#pragma omp parallel num_threads(threads)
104 {
105 TParticleCode* source = m;
106 TParticleCode* dest = m_temp;
107 unsigned int l = omp_get_thread_num();
108 unsigned int div = n / omp_get_num_threads();
109 unsigned int mod = n % omp_get_num_threads();
110 unsigned int left_index = l < mod ? (div + (mod == 0 ? 0 : 1)) * l : n - (omp_get_num_threads() - l) * div;
111 unsigned int right_index = left_index + div - (mod > l ? 0 : 1);
112
113 for (unsigned int digit = 0; digit < sizeof(m->key); ++digit)
114 {
115 unsigned int s_sum[256] = { 0 };
116 unsigned int s0[256] = { 0 };
117 unsigned char* b1 = (unsigned char*)&source[right_index].key;
118 unsigned char* b2 = (unsigned char*)&source[left_index].key;
119 while (b1 >= b2)
120 {
121 ++s0[*(b1 + digit)];
122 b1 -= sizeof(TParticleCode);
123 }
124 for (unsigned int i = 0; i < 256; i++)
125 {
126 s[i + 256 * l] = s0[i];
127 }
128
129#pragma omp barrier
130 for (unsigned int j = 0; j < threads; j++)
131 {
132 for (unsigned int i = 0; i < 256; i++)
133 {
134 s_sum[i] += s[i + 256 * j];
135 if (j < l)
136 {
137 s0[i] += s[i + 256 * j];
138 }
139 }
140 }
141
142 for (unsigned int i = 1; i < 256; ++i)
143 {
144 s_sum[i] += s_sum[i - 1];
145 s0[i] += s_sum[i - 1];
146 }
147 unsigned char* b = (unsigned char*)&source[right_index].key + digit;
148 TParticleCode* v1 = &source[right_index];
149 TParticleCode* v2 = &source[left_index];
150 while (v1 >= v2)
151 {
152 dest[--s0[*b]] = *v1--;
153 b -= sizeof(TParticleCode);
154 }
155#pragma omp barrier
156 std::swap(source, dest);
157 }
158 }
159
160 // Если ключ структуры однобайтовый, просто копируем в исходный массив
161 if (sizeof(m->key) == 1)
162 {
163 memcpy(m, m_temp, n * sizeof(TParticleCode));
164 }
165 }
166
167
168 inline size_t BinSearch(const std::vector<std::pair<double, size_t>>& currentNN, double x, int low, int high)
169 {
170 int mid = -1;
171
172 if (x > currentNN[high].first)
173 return high + 1;
174
175 while (low <= high) {
176 mid = (low + high) / 2;
177
178 if (currentNN[mid].first == x)
179 return mid + 1; //выход из цикла
180
181 if (currentNN[mid].first < x)
182 low = mid + 1;
183 else
184 high = mid - 1;
185 }
186 return mid;
187 }
188
189 void newSort(std::vector<std::pair<double, size_t>>& mass, std::vector<std::pair<double, size_t>>& dstKeys) {
190 const size_t k = mass.size();
191 size_t cnt = 0;
192
193 for (size_t i = 0; i < k; ++i)
194 {
195 double elem = mass[i].first;
196
197 cnt = 0;
198 for (size_t j = 0; j < k; ++j)
199 cnt += (mass[j].first < elem);
200
201 //Это для того, чтобы сортировка была устойчивой? Без этого никак?
202 //&&&
203 //for (size_t j = 0; j < i; ++j)
204 // cnt += (mass[j].first == elem);
205
206 dstKeys[cnt] = mass[i];
207 }
208 mass.swap(dstKeys);
209 }
210
211 void newMerge(
212 int iii,
213 std::vector<std::pair<double, size_t>>& currentNN, const std::vector<std::pair<double, size_t>>& candidateNN,
214 std::vector<size_t>& loc,
215 std::vector<size_t>& counter,
216 std::vector<size_t>& offset,
217 std::vector<size_t>& counterScan,
218 std::vector<std::pair<double, size_t>>& updateNN
219 )
220 {
221 const size_t k = candidateNN.size() / 2; //количество ближайших соседей
222
223 for (size_t j = 0; j < 2 * k; ++j)
224 loc[j] = BinSearch(currentNN, candidateNN[j].first, 0, (int)k - 1);
225
226 for (size_t j = 0; j < 2 * k; ++j)
227 counter[j] = j & 1;
228
229 for (size_t j = 0; j < 2 * k; ++j)
230 {
231 if ((loc[j] > 0) && ((loc[j] == k) || (candidateNN[j].second == currentNN[loc[j] - 1].second)))
232 offset[j] = k + 1;
233 else
234 offset[j] = counter[2 * loc[j]]++;
235 }
236
237 counterScan[0] = 0;
238 for (size_t j = 1; j < 2 * k; ++j)
239 counterScan[j] = counterScan[j - 1] + counter[j - 1];
240
241 size_t index;
242 for (size_t j = 0; j < k; ++j)
243 {
244 index = counterScan[2 * j + 1];
245 if (index < k)
246 updateNN[index] = currentNN[j];
247 }
248
249 for (size_t j = 0; j < 2 * k; ++j)
250 {
251 if (2 * loc[j] < 2 * k)
252 {
253 index = counterScan[2 * loc[j]] + offset[j];
254 if (index < k)
255 updateNN[index] = candidateNN[j];
256 }
257 }
258
259 currentNN.swap(updateNN);
260 }
261
262
263 std::pair<bool, bool> calcCheck(const Vortex2D& vtxi, const Vortex2D& vtxk, double maxG, double cSP, double cRBP, double epsCol, int type, double& d2)
264 {
265 bool flagExit = false;
266 bool check = false;
267
268 //линейное увеличение радиуса коллапса
269 double mnog = std::max(1.0, /* 2.0 * */ (vtxi.r()[0] - cRBP) / cSP);
270 double r2test = (epsCol * mnog) * (epsCol * mnog);
271
272 if (type == 1)
273 r2test *= 4.0; //Увеличение радиуса коллапса в 2 раза для коллапса вихрей разных знаков
274
275 d2 = (vtxi.r() - vtxk.r()).length2();
276
277 if (d2 > r2test)
278 {
279 flagExit = true;
280 return { true, false };
281 }
282
283 const double gi = vtxi.g();
284 const double gk = vtxk.g();
285
286 if (d2 < r2test)
287 {
288 switch (type)
289 {
290 case 0:
291 check = (fabs(gi * gk) != 0.0) && (fabs(gi + gk) < (mnog * mnog) * maxG);
292 break;
293 case 1:
294 check = (gi * gk < 0.0);
295 break;
296 case 2:
297 check = (gi * gk > 0.0) && (fabs(gi + gk) < (mnog * mnog) * maxG);
298 break;
299 }
300 }//if r2 < r2_test
301
302 return { false, check };
303 }
304
305}
306
307void WakekNNnewForCollaps(const std::vector<Vortex2D>& vtx, const size_t k, std::vector<std::vector<std::pair<double, size_t>>>& initdist,
308 double cSP, double cRBP, double maxG, double epsCol, int type)
309{
310 using namespace knnNew;
311
312 double preTime = -omp_get_wtime();
313
314 const size_t n = vtx.size();
315
317 auto xx = std::minmax_element(vtx.begin(), vtx.end(), [](const Vortex2D& P1, const Vortex2D& P2) {return P1.r()[0] < P2.r()[0]; });
318 auto yy = std::minmax_element(vtx.begin(), vtx.end(), [](const Vortex2D& P1, const Vortex2D& P2) {return P1.r()[1] < P2.r()[1]; });
319
320 double scale = std::max(xx.second->r()[0] - xx.first->r()[0], yy.second->r()[1] - yy.first->r()[1]);
321
322 //сортировка массива (data) по мортоновским кодам
323 std::vector<unsigned int> s(256 * omp_get_max_threads());
324
325 std::vector<TParticleCode> mcdata(vtx.size());
326 std::vector<TParticleCode> mcdata_temp(vtx.size());
327
328 //std::vector<unsigned int> iq;
329
330 //Сдвигаем все точки
331 const int nSdvig = 5;
332 double tStart[nSdvig], tFinish[nSdvig];
333 double tm[nSdvig][5];
334
335 preTime += omp_get_wtime();
336
337 std::pair<double, size_t> zeroPair = std::make_pair<double, size_t>(0.0, 0);
338 std::pair<double, size_t> minusOnePair = std::make_pair<double, size_t>(-1.0, 0);
339
340 std::vector<std::pair<double, size_t>> dist(2 * k, { -1.0, 0 });
341 std::vector<size_t> loc(2 * k);
342 std::vector<size_t> counter(2 * k, 0);
343 std::vector<size_t> offset(2 * k, 0);
344 std::vector<size_t> counterScan(2 * k, 0);
345 std::vector<std::pair<double, size_t>> dstKeys1(2 * k, zeroPair);
346
347 std::vector<std::pair<double, size_t>> updateNN(k, zeroPair);
348 std::vector<std::pair<double, size_t>> dstKeys(k, zeroPair);
349
350 //14-05-2024
351 for (size_t sdvig = 0; sdvig < nSdvig /*5*/; ++sdvig)
352 {
353 tStart[sdvig] = omp_get_wtime();
354
355 const Point2D& lowLeft = { xx.first->r()[0], yy.first->r()[1] };
356 double* time = tm[sdvig];
357
358 //масштабирование координат вихрей в [0;0.75)^2, поиск их мортоновских кодов
359
360 time[0] = omp_get_wtime();
361#pragma omp parallel for
362 for (int i = 0; i < vtx.size(); ++i)
363 {
364 Point2D sh = (vtx[i].r() - lowLeft) * (0.75 / scale) + sdvig * Point2D{ 0.05, 0.05 };
365 mcdata[i].key = Morton2D(sh);
366 mcdata[i].originNumber = i;
367 }
368
369 time[1] = omp_get_wtime();
370
371 //сортировка единого массива (data и query) по мортоновским кодам
372 RSort_Parallel(mcdata.data(), mcdata_temp.data(), (int)mcdata.size(), s.data());
373
374 time[2] = omp_get_wtime();
375
376 for (size_t idx = 0; idx < 2 * k; ++idx)
377 {
378 dist[idx] = minusOnePair;
379 dstKeys1[idx] = zeroPair;
380 loc[idx] = counter[idx] = offset[idx] = counterScan[idx] = 0;
381 }
382
383 for (size_t idx = 0; idx < k; ++idx)
384 updateNN[idx] = dstKeys[idx] = zeroPair;
385
386 time[3] = omp_get_wtime();
387
388#pragma omp parallel for firstprivate(dist, loc, counter, offset, counterScan, updateNN, dstKeys, dstKeys1)
389 for (int i = 0; i < initdist.size(); ++i)
390 {
391 const Vortex2D& vtxi = vtx[mcdata[i].originNumber];
392
393 int cntr = 0;
394 int search = i - 1; // iq[i];
395 std::vector<std::pair<double, size_t>>& fillPosition = ((sdvig == 0) ? initdist[mcdata[i].originNumber] : dist);
396
397 while ((cntr < k) && (search >= 0))
398 {
399 const Vortex2D& vtxk = vtx[mcdata[search].originNumber];
400 bool flagExit, check;
401 double d2;
402 std::tie(flagExit, check) = calcCheck(vtxi, vtxk, maxG, cSP, cRBP, epsCol, type, d2);
403
404 if (flagExit)
405 break;
406
407 if ((mcdata[search].originNumber > mcdata[i].originNumber) && check)
408 fillPosition[cntr++] = { d2, mcdata[search].originNumber };
409
410 --search;
411 }
412
413 for (int w = cntr; w < k; ++w)
414 fillPosition[cntr++] = { 100000000.0, 0 };
415
416 search = i + 1;
417
418 while ((cntr < 2 * k) && (search < mcdata.size()))
419 {
420 const Vortex2D& vtxk = vtx[mcdata[search].originNumber];
421 bool flagExit, check;
422 double d2;
423 std::tie(flagExit, check) = calcCheck(vtxi, vtxk, maxG, cSP, cRBP, epsCol, type, d2);
424
425 if (flagExit)
426 break;
427
428 if ((mcdata[search].originNumber > mcdata[i].originNumber) && check)
429 fillPosition[cntr++] = { d2, mcdata[search].originNumber };
430
431 ++search;
432 }
433 for (int w = cntr; w < 2 * k; ++w)
434 fillPosition[cntr++] = { 100000000.0, 0 };
435
436 if (sdvig == 0)
437 {
438 newSort(initdist[mcdata[i].originNumber], dstKeys1);
439 initdist[mcdata[i].originNumber].resize(k);
440 }
441 else
442 {
443 newSort(dist, dstKeys1);
444 newMerge(mcdata[i].originNumber, initdist[mcdata[i].originNumber], dist, loc, counter, offset, counterScan, updateNN);
445 newSort(initdist[mcdata[i].originNumber], dstKeys);
446 }
447 }
448
449 time[4] = omp_get_wtime();
450
451 tFinish[sdvig] = omp_get_wtime();
452
453 }//for sdvig
454} // WakekNNnewForCollaps
455
456
457
458void WakekNNnewForEpsast(const std::vector<BH::PointsCopy>& vtx, const size_t k, std::vector<std::vector<std::pair<double, size_t>>>& initdist)
459{
460 using namespace knnNew;
461
462 double preTime = -omp_get_wtime();
463
464 const size_t n = vtx.size();
465
467 auto xx = std::minmax_element(vtx.begin(), vtx.end(), [](const Vortex2D& P1, const Vortex2D& P2) {return P1.r()[0] < P2.r()[0]; });
468 auto yy = std::minmax_element(vtx.begin(), vtx.end(), [](const Vortex2D& P1, const Vortex2D& P2) {return P1.r()[1] < P2.r()[1]; });
469
470 double scale = std::max(xx.second->r()[0] - xx.first->r()[0], yy.second->r()[1] - yy.first->r()[1]);
471
472 //сортировка массива (data) по мортоновским кодам
473 std::vector<unsigned int> s(256 * omp_get_max_threads());
474
475 std::vector<TParticleCode> mcdata(vtx.size());
476 std::vector<TParticleCode> mcdata_temp(vtx.size());
477
478 //std::vector<unsigned int> iq;
479
480 //Сдвигаем все точки
481 const int nSdvig = 5;
482 double tStart[nSdvig], tFinish[nSdvig];
483 double tm[nSdvig][5];
484
485 preTime += omp_get_wtime();
486
487 std::pair<double, size_t> zeroPair = std::make_pair<double, size_t>(0.0, 0);
488 std::pair<double, size_t> minusOnePair = std::make_pair<double, size_t>(-1.0, 0);
489
490 std::vector<std::pair<double, size_t>> dist(2 * k, { -1.0, 0 });
491 std::vector<size_t> loc(2 * k);
492 std::vector<size_t> counter(2 * k, 0);
493 std::vector<size_t> offset(2 * k, 0);
494 std::vector<size_t> counterScan(2 * k, 0);
495 std::vector<std::pair<double, size_t>> dstKeys1(2 * k, zeroPair);
496
497 std::vector<std::pair<double, size_t>> updateNN(k, zeroPair);
498 std::vector<std::pair<double, size_t>> dstKeys(k, zeroPair);
499
500 //14-05-2024
501 for (size_t sdvig = 0; sdvig < nSdvig /*5*/; ++sdvig)
502 {
503 tStart[sdvig] = omp_get_wtime();
504
505 const Point2D& lowLeft = { xx.first->r()[0], yy.first->r()[1] };
506 double* time = tm[sdvig];
507
508 //масштабирование координат вихрей в [0;0.75)^2, поиск их мортоновских кодов
509
510 time[0] = omp_get_wtime();
511#pragma omp parallel for
512 for (int i = 0; i < vtx.size(); ++i)
513 {
514 Point2D sh = (vtx[i].r() - lowLeft) * (0.75 / scale) + sdvig * Point2D{ 0.05, 0.05 };
515 mcdata[i].key = Morton2D(sh);
516 mcdata[i].originNumber = i;
517 }
518
519 time[1] = omp_get_wtime();
520
521 //сортировка единого массива (data и query) по мортоновским кодам
522 RSort_Parallel(mcdata.data(), mcdata_temp.data(), (int)mcdata.size(), s.data());
523
524 time[2] = omp_get_wtime();
525
526 for (size_t idx = 0; idx < 2 * k; ++idx)
527 {
528 dist[idx] = minusOnePair;
529 dstKeys1[idx] = zeroPair;
530 loc[idx] = counter[idx] = offset[idx] = counterScan[idx] = 0;
531 }
532
533 for (size_t idx = 0; idx < k; ++idx)
534 updateNN[idx] = dstKeys[idx] = zeroPair;
535
536 time[3] = omp_get_wtime();
537
538#pragma omp parallel for firstprivate(dist, loc, counter, offset, counterScan, updateNN, dstKeys, dstKeys1)
539 for (int i = 0; i < initdist.size(); ++i)
540 {
541 const Vortex2D& vtxi = vtx[mcdata[i].originNumber];
542
543 int cntr = 0;
544 int search = i - 1; // iq[i];
545 std::vector<std::pair<double, size_t>>& fillPosition = ((sdvig == 0) ? initdist[mcdata[i].originNumber] : dist);
546
547 while ((cntr < k) && (search >= 0))
548 {
549 const Vortex2D& vtxk = vtx[mcdata[search].originNumber];
550 double d2 = (vtxi.r()-vtxk.r()).length2();
551 fillPosition[cntr++] = { d2, mcdata[search].originNumber };
552 --search;
553 }
554
555 for (int w = cntr; w < k; ++w)
556 fillPosition[cntr++] = { 100000000.0, 0 };
557
558 search = i + 1;
559
560 while ((cntr < 2 * k) && (search < mcdata.size()))
561 {
562 const Vortex2D& vtxk = vtx[mcdata[search].originNumber];
563 double d2 = (vtxi.r() - vtxk.r()).length2();
564 fillPosition[cntr++] = { d2, mcdata[search].originNumber };
565 ++search;
566 }
567 for (int w = cntr; w < 2 * k; ++w)
568 fillPosition[cntr++] = { 100000000.0, 0 };
569
570 if (sdvig == 0)
571 {
572 newSort(initdist[mcdata[i].originNumber], dstKeys1);
573 initdist[mcdata[i].originNumber].resize(k);
574 }
575 else
576 {
577 newSort(dist, dstKeys1);
578 newMerge(mcdata[i].originNumber, initdist[mcdata[i].originNumber], dist, loc, counter, offset, counterScan, updateNN);
579 newSort(initdist[mcdata[i].originNumber], dstKeys);
580 }
581 }
582
583 time[4] = omp_get_wtime();
584
585 tFinish[sdvig] = omp_get_wtime();
586
587 }//for sdvig
588
589 //for (size_t sd = 0; sd < nSdvig; ++sd)
590 // std::cout << "knn[" << sd << "] = " << tFinish[sd] - tStart[sd] << "sec. " << std::endl;
591
592} // WakekNNnewForEpsast
codeLength
#define codeLength
Definition Gpudefs.h:97
VMlib::Vortex2D
Класс, опеделяющий двумерный вихревой элемент
Definition Vortex2D.h:59
VMlib::Vortex2D::r
HD Point2D & r()
Функция для доступа к радиус-вектору вихря
Definition Vortex2D.h:87
VMlib::Vortex2D::g
HD double & g()
Функция для доступа к циркуляции вихря
Definition Vortex2D.h:95
WakekNNnewForEpsast
void WakekNNnewForEpsast(const std::vector< BH::PointsCopy > &vtx, const size_t k, std::vector< std::vector< std::pair< double, size_t > > > &initdist)
Definition knnCPU.cpp:458
WakekNNnewForCollaps
void WakekNNnewForCollaps(const std::vector< Vortex2D > &vtx, const size_t k, std::vector< std::vector< std::pair< double, size_t > > > &initdist, double cSP, double cRBP, double maxG, double epsCol, int type)
Definition knnCPU.cpp:307
knnCPU.h
knn CPU.
knnNew::ExpandBits
unsigned int ExpandBits(unsigned int v)
Definition knnCPU.cpp:53
knnNew::newMerge
void newMerge(int iii, std::vector< std::pair< double, size_t > > &currentNN, const std::vector< std::pair< double, size_t > > &candidateNN, std::vector< size_t > &loc, std::vector< size_t > &counter, std::vector< size_t > &offset, std::vector< size_t > &counterScan, std::vector< std::pair< double, size_t > > &updateNN)
Definition knnCPU.cpp:211
knnNew::RSort_Parallel
void RSort_Parallel(TParticleCode *m, TParticleCode *m_temp, unsigned int n, unsigned int *s)
Сортировка массива из мортоновский кодов
Definition knnCPU.cpp:95
knnNew::Morton2D
unsigned int Morton2D(const Point2D &r)
Definition knnCPU.cpp:85
knnNew::calcCheck
std::pair< bool, bool > calcCheck(const Vortex2D &vtxi, const Vortex2D &vtxk, double maxG, double cSP, double cRBP, double epsCol, int type, double &d2)
Definition knnCPU.cpp:263
knnNew::newSort
void newSort(std::vector< std::pair< double, size_t > > &mass, std::vector< std::pair< double, size_t > > &dstKeys)
Definition knnCPU.cpp:189
knnNew::twoPowCodeLengthVar
const int twoPowCodeLengthVar
Definition knnCPU.cpp:48
knnNew::BinSearch
size_t BinSearch(const std::vector< std::pair< double, size_t > > &currentNN, double x, int low, int high)
Definition knnCPU.cpp:168
VMlib::TParticleCode::key
unsigned int key
Мортоновский код частицы
Definition Point2D.h:57