github.com\/denisskin\/flashsort<\/a><\/p>\n \u0414\u043b\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0434\u0430\u043d\u043d\u044b\u0445 \u043d\u0443\u0436\u043d\u043e \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439 flash_sort, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044e get_byte(void*, int) \u2013 \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f i-\u0433\u043e \u0431\u0430\u0439\u0442\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430.
\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0441\u0442\u0440\u043e\u043a\u0438: <\/p>\n
\/\/ sort array of strings char *names[10] = { "Hunter", "Isaac", "Christopher", "Bob", "Faith", "Alice", "Gabriel", "Denis", "****", "Ethan", }; static const char* get_char(const void *value, unsigned pos) { return *((char*)value + pos)? (char*)value + pos : NULL; } flashsort((void**)names, 10, get_char); <\/code><\/pre>\n \u0422\u0430\u043a\u0436\u0435 \u0432 \u0440\u0430\u0441\u043f\u043e\u0440\u044f\u0436\u0435\u043d\u0438\u0438 \u0438\u043c\u0435\u0435\u0442\u0441\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f flashsort_const<\/i> \u0434\u043b\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0434\u0430\u043d\u043d\u044b\u0445 \u0441\u0442\u0440\u043e\u0433\u043e \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b.
\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0447\u0438\u0441\u0435\u043b: <\/p>\n\/\/ sort integer values int nums[10] = {9, 6, 7, 0, 3, 1, 3, 2, 5, 8}; flashsort_const(nums, 10, sizeof(int), sizeof(int)); <\/code><\/pre>\n \u042d\u0442\u0443 \u0436\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043c\u043e\u0436\u043d\u043e \u0441 \u0443\u0441\u043f\u0435\u0445\u043e\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0438 \u0434\u043b\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u043f\u043e \u043a\u043b\u044e\u0447\u0443.
\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440: <\/p>\n
\/\/ sort key-value array by key typedef struct { int key; char *value; } KeyValue; KeyValue names[10] = { {8, "Hunter"}, {9, "Isaac"}, {3, "Christopher"}, {2, "Bob"}, {6, "Faith"}, {1, "Alice"}, {7, "Gabriel"}, {4, "Denis"}, {0, "none"}, {5, "Ethan"}, }; flashsort_const(names, 10, sizeof(KeyValue), sizeof(names->key)); <\/code><\/pre>\n \u0424\u0443\u043d\u043a\u0446\u0438\u044f flashsort_const<\/i> \u043f\u043e \u043f\u043e\u043d\u044f\u0442\u043d\u044b\u043c \u043f\u0440\u0438\u0447\u0438\u043d\u0430\u043c \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0447\u0443\u0442\u044c \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435 \u0435\u0435 \u0430\u043d\u0430\u043b\u043e\u0433\u0430 \u2013 \u0444\u0443\u043d\u043a\u0446\u0438\u0438, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0431\u044b\u043b\u0430 \u043e\u0431\u044a\u044f\u0432\u043b\u0435\u043d\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043c\u0430\u043a\u0440\u043e\u0441\u0430. \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0438 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 i-\u0433\u043e \u0431\u0430\u0439\u0442\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435.
\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043e\u0431\u044a\u044f\u0432\u0438\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0447\u0438\u0441\u0435\u043b \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043c\u0430\u043a\u0440\u043e\u0441\u0430 \u043c\u043e\u0436\u043d\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c: <\/p>\n\/\/ define function flashsort_int by macro #define FLASH_SORT_NAME flashsort_int #define FLASH_SORT_TYPE int #include "src\/flashsort_macro.h" int A[10] = {9, 6, 7, 0, 3, 1, 3, 2, 5, 8}; flashsort_int(A, 10); <\/code><\/pre>\n\u0411\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438<\/h3>\n
\u0412 \u044d\u0442\u043e\u043c \u0436\u0435 \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u0438 \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0438 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438, \u0433\u0434\u0435 \u0434\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043c\u0435\u0442\u043e\u0434\u043e\u043c qsort. <\/p>\n
cd benchmarks gcc ..\/src\/*.c benchmarks.c -o benchmarks.o && .\/benchmarks.o <\/code><\/pre>\n \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435, \u043c\u0435\u0442\u043e\u0434 flash_sort<\/i> \u0445\u043e\u0440\u043e\u0448\u043e \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0441\u0435\u0431\u044f \u043f\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441 qsort \u0432 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441\u043e \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0434\u0430\u043d\u043d\u044b\u043c\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0438\u0437 500\u041a \u0447\u0438\u0441\u0435\u043b \u0442\u0438\u043f\u0430 int \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0432 2.5 \u0440\u0430\u0437\u0430 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 quick-sort. \u041a\u0430\u043a \u0432\u0438\u0434\u043d\u043e \u0438\u0437 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0430, \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438, \u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0435 \u043d\u0430 N, \u0441 \u0440\u043e\u0441\u0442\u043e\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u043d\u0435 \u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f.<\/p>\n
Benchmarks sorting of integers<\/i> <\/p>\n------------------------------------------------------------------------------------------- Count Flash-sort | Quick-sort | elements Total time | Total time | N Tf Tf \/ N | Tq Tq \/ N | \u0394 ------------------------------------------------------------------------------------------- 100 0.000012 sec 1.225 \u00b5s | 0.000004 sec 0.428 \u00b5s | -65.10 % 194 0.000016 sec 0.814 \u00b5s | 0.000009 sec 0.439 \u00b5s | -46.04 % 374 0.000026 sec 0.690 \u00b5s | 0.000023 sec 0.604 \u00b5s | -12.40 % 724 0.000043 sec 0.592 \u00b5s | 0.000058 sec 0.795 \u00b5s | +34.29 % 1398 0.000099 sec 0.707 \u00b5s | 0.000155 sec 1.112 \u00b5s | +57.28 % 2702 0.000204 sec 0.753 \u00b5s | 0.000300 sec 1.111 \u00b5s | +47.44 % 5220 0.000410 sec 0.786 \u00b5s | 0.000620 sec 1.187 \u00b5s | +51.02 % 10085 0.000845 sec 0.838 \u00b5s | 0.001254 sec 1.243 \u00b5s | +48.41 % 19483 0.002205 sec 1.132 \u00b5s | 0.002672 sec 1.372 \u00b5s | +21.21 % 37640 0.004242 sec 1.127 \u00b5s | 0.005436 sec 1.444 \u00b5s | +28.15 % 72716 0.006886 sec 0.947 \u00b5s | 0.011171 sec 1.536 \u00b5s | +62.23 % 140479 0.011156 sec 0.794 \u00b5s | 0.022899 sec 1.630 \u00b5s | +105.26% 271388 0.018773 sec 0.692 \u00b5s | 0.045749 sec 1.686 \u00b5s | +143.70% 524288 0.037429 sec 0.714 \u00b5s | 0.093858 sec 1.790 \u00b5s | +150.76% <\/code><\/pre>\n ![](\"https:\/\/habrastorage.org\/files\/455\/e1e\/8d9\/455e1e8d94a54d6e9b7c88e785308fb5.png\"\/)
<\/p>\n
\u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u044b\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0432\u044b\u0434\u0430\u0435\u0442 \u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0441\u0442\u0440\u043e\u043a \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u043f\u0438\u0441\u043e\u043a \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0445\u0435\u0448\u0435\u0439, \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0432 base64.<\/p>\n
benchmark Sorting of hashes base64<\/i> <\/p>\n--------------------------------------------------------------------------------------------- Count Flash-sort | Quick-sort | elements Total time | Total time | N Tf Tf \/ N | Tq Tq \/ N | \u0394 --------------------------------------------------------------------------------------------- 147 0.000009 sec 0.609 \u00b5s | 0.000010 sec 0.694 \u00b5s | +13.97 % 274 0.000025 sec 0.918 \u00b5s | 0.000027 sec 0.991 \u00b5s | +7.95 % 512 0.000053 sec 1.036 \u00b5s | 0.000061 sec 1.195 \u00b5s | +15.37 % 955 0.000098 sec 1.024 \u00b5s | 0.000135 sec 1.416 \u00b5s | +38.32 % 1782 0.000164 sec 0.921 \u00b5s | 0.000279 sec 1.566 \u00b5s | +70.04 % 3326 0.000315 sec 0.947 \u00b5s | 0.000581 sec 1.745 \u00b5s | +84.31 % 6208 0.000629 sec 1.013 \u00b5s | 0.001210 sec 1.949 \u00b5s | +92.39 % 11585 0.001325 sec 1.144 \u00b5s | 0.002378 sec 2.053 \u00b5s | +79.50 % 21618 0.002904 sec 1.343 \u00b5s | 0.004712 sec 2.180 \u00b5s | +62.26 % 40342 0.006132 sec 1.520 \u00b5s | 0.009752 sec 2.417 \u00b5s | +59.03 % 75281 0.010780 sec 1.432 \u00b5s | 0.019778 sec 2.627 \u00b5s | +83.47 % 140479 0.023484 sec 1.672 \u00b5s | 0.043534 sec 3.099 \u00b5s | +85.37 % 262144 0.044967 sec 1.715 \u00b5s | 0.082878 sec 3.162 \u00b5s | +84.31 % <\/code><\/pre>\n ![](\"https:\/\/habrastorage.org\/files\/e36\/7d9\/5d3\/e367d95d3b8f4dc0b6a140067ff09911.png\"\/)
<\/p>\n
\u041e\u0434\u043d\u0430\u043a\u043e \u043c\u0435\u0442\u043e\u0434 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0431\u0435\u0437 \u044f\u0432\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0438\u043c\u0443\u0449\u0435\u0441\u0442\u0432\u0430: \u043b\u0438\u0448\u044c \u0447\u0443\u0442\u044c \u0448\u0443\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c quick-sort \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u0448\u0430\u043d\u043d\u044b\u0445 \u0430\u043d\u0433\u043b\u0438\u0439\u0441\u043a\u0438\u0445 \u0441\u043b\u043e\u0432.<\/p>\n
benchmark Sorting of english words <\/i> <\/p>\n--------------------------------------------------------------------------------------------- Count Flash-sort | Quick-sort | elements Total time | Total time | N Tf Tf \/ N | Tq Tq \/ N | \u0394 --------------------------------------------------------------------------------------------- 140 0.000016 sec 1.166 \u00b5s | 0.000014 sec 0.993 \u00b5s | -14.85 % 261 0.000030 sec 1.168 \u00b5s | 0.000029 sec 1.114 \u00b5s | -4.59 % 485 0.000055 sec 1.139 \u00b5s | 0.000061 sec 1.259 \u00b5s | +10.59 % 901 0.000141 sec 1.565 \u00b5s | 0.000158 sec 1.750 \u00b5s | +11.82 % 1673 0.000269 sec 1.608 \u00b5s | 0.000315 sec 1.884 \u00b5s | +17.17 % 3106 0.000536 sec 1.726 \u00b5s | 0.000655 sec 2.110 \u00b5s | +22.27 % 5766 0.001013 sec 1.756 \u00b5s | 0.001263 sec 2.191 \u00b5s | +24.76 % 10703 0.002007 sec 1.875 \u00b5s | 0.002525 sec 2.359 \u00b5s | +25.85 % 19868 0.004152 sec 2.090 \u00b5s | 0.005150 sec 2.592 \u00b5s | +24.04 % 36880 0.008459 sec 2.294 \u00b5s | 0.010266 sec 2.784 \u00b5s | +21.36 % 68458 0.017460 sec 2.550 \u00b5s | 0.021423 sec 3.129 \u00b5s | +22.70 % 127076 0.035615 sec 2.803 \u00b5s | 0.041683 sec 3.280 \u00b5s | +17.04 % 235885 0.075747 sec 3.211 \u00b5s | 0.086523 sec 3.668 \u00b5s | +14.23 % <\/code><\/pre>\n ![](\"https:\/\/habrastorage.org\/files\/a09\/cbe\/029\/a09cbe02946a417da05436daf68c0978.png\"\/)
<\/p>\n
\u041d\u0435\u043f\u043b\u043e\u0445\u043e \u043c\u0435\u0442\u043e\u0434 \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0441\u0435\u0431\u044f \u0432 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 \u0447\u0430\u0441\u0442\u043e-\u043f\u043e\u0432\u0442\u043e\u0440\u044f\u044e\u0449\u0438\u043c\u0438\u0441\u044f \u0434\u0430\u043d\u043d\u044b\u043c\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043b\u043e\u0433\u043e\u0432 \u043f\u043e\u043b\u0443\u043c\u0438\u043b\u043b\u0438\u043e\u043d\u0430 IP-\u0430\u0434\u0440\u0435\u0441\u043e\u0432 (\u0432\u0437\u044f\u0442\u044b\u0445 \u0438\u0437 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0439 \u0436\u0438\u0437\u043d\u0438) \u043c\u0435\u0442\u043e\u0434\u043e\u043c flash-sort \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0432 5 \u0440\u0430\u0437 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c \u0431\u044b\u0441\u0442\u0440\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430.<\/p>\n
benchmark Sorting of IP-addresses log<\/i> <\/p>\n--------------------------------------------------------------------------------------------- Count Flash-sort | Quick-sort | elements Total time | Total time | N Tf Tf \/ N | Tq Tq \/ N | \u0394 --------------------------------------------------------------------------------------------- 107 0.000010 sec 0.953 \u00b5s | 0.000011 sec 1.056 \u00b5s | +10.78 % 208 0.000013 sec 0.639 \u00b5s | 0.000010 sec 0.480 \u00b5s | -25.00 % 407 0.000024 sec 0.584 \u00b5s | 0.000033 sec 0.812 \u00b5s | +39.01 % 793 0.000039 sec 0.493 \u00b5s | 0.000073 sec 0.915 \u00b5s | +85.61 % 1547 0.000080 sec 0.517 \u00b5s | 0.000211 sec 1.367 \u00b5s | +164.15% 3016 0.000169 sec 0.560 \u00b5s | 0.000512 sec 1.697 \u00b5s | +202.80% 5881 0.000308 sec 0.523 \u00b5s | 0.000962 sec 1.636 \u00b5s | +212.67% 11466 0.000548 sec 0.478 \u00b5s | 0.001812 sec 1.581 \u00b5s | +230.48% 22354 0.001034 sec 0.463 \u00b5s | 0.004191 sec 1.875 \u00b5s | +305.26% 43584 0.002109 sec 0.484 \u00b5s | 0.008693 sec 1.994 \u00b5s | +312.26% 84974 0.004411 sec 0.519 \u00b5s | 0.016003 sec 1.883 \u00b5s | +262.81% 165670 0.008837 sec 0.533 \u00b5s | 0.037358 sec 2.255 \u00b5s | +322.75% 323000 0.016046 sec 0.497 \u00b5s | 0.081251 sec 2.516 \u00b5s | +406.36% 629739 0.030895 sec 0.491 \u00b5s | 0.164283 sec 2.609 \u00b5s | +431.75% <\/code><\/pre>\n ![](\"https:\/\/habrastorage.org\/files\/3ca\/7e9\/ce9\/3ca7e9ce9a5f4b62a9cf66a96a8676b2.png\"\/)
<\/p>\n
\u041f\u0440\u0438\u0447\u0435\u043c \u043d\u0430 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432\u0440\u0435\u043c\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0440\u0430\u0441\u0442\u0435\u0442 \u0441\u0442\u0440\u043e\u0433\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u043e \u043e\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<\/p>\n
\u0412 \u0437\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/h3>\n
\u041d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0442\u043e \u0447\u0442\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u0442\u0443\u0442 \u043c\u0435\u0442\u043e\u0434 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0432\u0441\u0435\u0433\u0434\u0430 \u0434\u0435\u043b\u0430\u0435\u0442 \u0441\u0442\u0440\u043e\u0433\u043e O(N) \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043e\u043a, \u0432\u0441\u0435 \u0436\u0435 \u043d\u0430\u0438\u0432\u043d\u043e \u0431\u044b\u043b\u043e \u0431\u044b \u043e\u0436\u0438\u0434\u0430\u0442\u044c, \u0447\u0442\u043e \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0442\u0438\u043f\u043e\u0432 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432\u043e \u0432\u0441\u0435\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u0412\u043f\u043e\u043b\u043d\u0435 \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0435\u0433\u043e \u0440\u0430\u0431\u043e\u0442\u044b \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u0432\u0438\u0441\u0435\u0442\u044c \u0438 \u043e\u0442 \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445.
\u0412\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0432 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442\u044c \u0437\u0430 \u043d\u0435\u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0445\u043e\u0442\u044f \u0431\u044b \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u043d\u0430 \u044d\u0442\u0430\u043f\u0435 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0435\u043c\u0443 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043e\u0431\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f \u043a \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u043c \u0443\u0447\u0430\u0441\u0442\u043a\u0430\u043c \u043f\u0430\u043c\u044f\u0442\u0438.
\u041e\u0434\u043d\u0430\u043a\u043e \u043f\u043e\u043b\u0430\u0433\u0430\u044e, \u0447\u0442\u043e \u0432\u0441\u0435 \u0436\u0435 \u0435\u0449\u0435 \u0435\u0441\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0440 \u0434\u043b\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u0433\u043e \u0442\u0443\u0442 \u043c\u0435\u0442\u043e\u0434\u0430. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043d\u0430 \u043f\u0435\u0440\u0432\u043e\u043c \u044d\u0442\u0430\u043f\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043f\u043e\u043c\u0438\u043c\u043e \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u0430 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043f\u043e\u043f\u0430\u0434\u0430\u044e\u0449\u0438\u0445 \u0432 \u043a\u043e\u0440\u0437\u0438\u043d\u0443, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0432\u0435\u0441\u0442\u0438 \u0435\u0449\u0435 \u043a\u0430\u043a\u0443\u044e-\u0442\u043e \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u0443\u044e \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u043a\u0443 \u0438 \u0443\u0436\u0435 \u043d\u0430 \u0435\u0435 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0438 \u0432\u044b\u0431\u0438\u0440\u0430\u0442\u044c \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u0434\u043b\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432\u043d\u0443\u0442\u0440\u0438 \u043a\u043e\u0440\u0437\u0438\u043d\u044b. \u0423\u0432\u0435\u0440\u0435\u043d, \u0447\u0442\u043e \u0432 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u043c \u0441\u0447\u0435\u0442\u0435 \u0445\u043e\u0440\u043e\u0448\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435\u043c \u043c\u043e\u0433\u043b\u0430 \u0431\u044b \u0441\u0442\u0430\u0442\u044c \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0430 \u043f\u043e\u0434\u043e\u0431\u043d\u043e\u0433\u043e \u0433\u0438\u0431\u0440\u0438\u0434\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u044f\u044e\u0449\u0435\u0433\u043e \u0432 \u0441\u0435\u0431\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044e \u043f\u043e\u0434 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0435 \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u043f\u0430\u043c\u044f\u0442\u0438 \u0438\u043b\u0438 \u043d\u0430 \u0434\u0438\u0441\u043a\u0435.
\u041e\u0434\u043d\u0430\u043a\u043e \u044d\u0442\u0438 \u0432\u043e\u043f\u0440\u043e\u0441\u044b \u0432\u044b\u0445\u043e\u0434\u044f\u0442 \u0437\u0430 \u0440\u0430\u043c\u043a\u0438 \u0441\u0442\u0430\u0442\u044c\u0438, \u0446\u0435\u043b\u044c\u044e \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0431\u044b\u043b\u043e \u043b\u0438\u0448\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u201c\u043d\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435\u043c\u201d \u0432 \u0447\u0438\u0441\u0442\u043e\u043c \u0438\u0445 \u0432\u0438\u0434\u0435. \u0412 \u043b\u044e\u0431\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0441\u0447\u0438\u0442\u0430\u044e, \u0447\u0442\u043e \u0432 \u0432\u043e\u043f\u0440\u043e\u0441\u0430\u0445 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0434\u0430\u043d\u043d\u044b\u0445 \u0435\u0449\u0435 \u043f\u043e\u043a\u0430 \u0440\u0430\u043d\u043e \u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0442\u043e\u0447\u043a\u0443. <\/p>\n
<\/div>\n
\u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 https:\/\/habrahabr.ru\/post\/280848\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":" \u041f\u0440\u0438\u0432\u0435\u0442 \u0432\u0441\u0435\u043c! <\/p>\n
\u0423 \u043c\u0435\u043d\u044f \u0435\u0441\u0442\u044c \u043e\u0434\u043d\u043e \u0445\u043e\u0431\u0431\u0438 \u2013 \u044f \u043e\u0447\u0435\u043d\u044c \u043b\u044e\u0431\u043b\u044e \u0438\u0437\u043e\u0431\u0440\u0435\u0442\u0430\u0442\u044c \u0432\u0435\u043b\u043e\u0441\u0438\u043f\u0435\u0434\u044b.
\u041e\u0431 \u0438\u0437\u043e\u0431\u0440\u0435\u0442\u0435\u043d\u0438\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u0442\u0430\u043a\u043e\u0433\u043e \u0432\u0435\u043b\u043e\u0441\u0438\u043f\u0435\u0434\u0430 \u0445\u043e\u0447\u0443 \u0432\u0430\u043c \u0441\u0435\u0433\u043e\u0434\u043d\u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0437\u0430\u0442\u044c. <\/p>\n
\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u2013 \u0437\u0430\u0434\u0430\u0447\u0430, \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0434\u0430\u043b\u0435\u043a\u043e \u0443\u0436\u0435 \u043d\u0435 \u043f\u0435\u0440\u0432\u044b\u0439 \u0433\u043e\u0434. \u041e\u043d\u0430 \u043f\u0440\u0435\u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u043d\u0430\u0441 \u0441 \u043f\u0435\u0440\u0432\u044b\u0445 \u043a\u0443\u0440\u0441\u043e\u0432 \u0442\u0435\u0445\u043d\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0432\u0443\u0437\u043e\u0432, \u0430 \u043a\u043e\u043c\u0443 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u043f\u043e\u0432\u0435\u0437\u043b\u043e, \u0442\u043e \u0438 \u0441\u043e \u0448\u043a\u043e\u043b\u044c\u043d\u043e\u0439 \u0441\u043a\u0430\u043c\u044c\u0438. \u041e\u0431\u044b\u0447\u043d\u043e \u044d\u0442\u043e \u043c\u0435\u0442\u043e\u0434\u044b \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u201c\u043f\u0443\u0437\u044b\u0440\u044c\u043a\u043e\u043c\u201d, \u201c\u0434\u0435\u043b\u0435\u043d\u0438\u0435\u043c\u201d, \u201c\u0431\u044b\u0441\u0442\u0440\u0430\u044f\u201d, \u201c\u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438\u201d \u0438 \u043f\u0440\u043e\u0447\u0438\u0435. <\/p>\n
![\"\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430](\"https:\/\/habrastorage.org\/files\/d86\/e0c\/8fa\/d86e0c8fa5f347cfbdcf925d9d735fe2.png\")
\u0412\u043e\u0442, \u043a \u043f\u0440\u0438\u043c\u0435\u0440\u0443, \u043f\u043e\u0434\u043e\u0431\u043d\u043e\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043c\u0435\u0442\u043e\u0434\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u201c\u043f\u0443\u0437\u044b\u0440\u044c\u043a\u043e\u043c\u201d \u043c\u0435\u043d\u044f \u0443\u0447\u0438\u043b\u0438 \u0432 \u043e\u0434\u043d\u043e\u0439 \u043a\u0440\u0443\u043f\u043d\u043e\u0439 IT-\u043a\u043e\u043c\u043f\u0430\u043d\u0438\u0438. \u042d\u0442\u043e\u0442 \u043c\u0435\u0442\u043e\u0434 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0441\u044f \u043c\u0430\u0442\u0451\u0440\u044b\u043c\u0438 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0441\u0442\u0430\u043c\u0438 \u0442\u0430\u043c \u043f\u043e\u0432\u0441\u0435\u043c\u0435\u0441\u0442\u043d\u043e.<\/i><\/p>\n
\u0422\u0430\u043a \u0432\u043e\u0442, \u043c\u043d\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u0431\u044b\u043b\u043e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e, \u043f\u043e\u0447\u0435\u043c\u0443 \u0443\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u0442\u0430\u043a \u043c\u0430\u043b\u043e \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u043c\u0435\u0442\u043e\u0434\u0430\u043c \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0431\u0435\u0437 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f (\u043f\u043e\u0440\u0430\u0437\u0440\u044f\u0434\u043d\u0430\u044f, \u0431\u043b\u043e\u0447\u043d\u0430\u044f \u0438 \u0442.\u043f.). \u0412\u0435\u0434\u044c \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u043e\u0442\u043d\u043e\u0441\u044f\u0442\u0441\u044f \u043a \u043a\u043b\u0430\u0441\u0441\u0443 \u0431\u044b\u0441\u0442\u0440\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432, \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u044e\u0442\u0441\u044f \u0437\u0430 \u041e(N) \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043e\u043a \u0438 \u043f\u0440\u0438 \u0443\u0434\u0430\u0447\u043d\u043e \u043f\u043e\u0434\u043e\u0431\u0440\u0430\u043d\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u043c\u043e\u0433\u0443\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c\u0441\u044f \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-277611","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/277611","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=277611"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/277611\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=277611"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=277611"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=277611"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![](\"https:\/\/habrastorage.org\/files\/8ad\/14e\/610\/8ad14e61002543fe94873cff2de5511b.png\")
<\/p>\n![](\"https:\/\/habrastorage.org\/files\/caf\/014\/49c\/caf01449cb0e46d28eb923ff324e6e82.png\")
<\/p>\n![](\"https:\/\/habrastorage.org\/files\/b01\/452\/7d9\/b014527d91bb44a39ae4f2035df26ac4.png\")
<\/p>\n![](\"https:\/\/habrastorage.org\/files\/144\/d5e\/bcf\/144d5ebcf53d470f8f3e35cd8f45ecbc.png\")
<\/p>\n