Created
September 12, 2017 05:26
-
-
Save Pho3nixHun/80ea27d0099914ffbe19da6a9b8c57fd to your computer and use it in GitHub Desktop.
Algorithms
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function test(func, target, iterations = 100000) { | |
| const start = Date.now(); | |
| for (let i = 0; i < iterations; i++) { | |
| func(target.slice(), i); | |
| } | |
| const end = Date.now(); | |
| return { duration: end - start, result: func(target.slice(), 0) }; | |
| } | |
| function truncate(text, maxLength = 32) { | |
| if(text.length <= maxLength) return text; | |
| return `${text.slice(0, maxLength/2-2)}...${text.slice(text.length - maxLength/2-1, text.length)}` | |
| } | |
| const A = [727, 412, 216, 613, 955, 863, 594, 518, 746, 132, 735, 323, 295, 379, 585, 844, 141, 527, 499, 980, 234, 872, 556, 579, 700, 164, 949, 612, 39, 390, 993, 279, 674, 521, 539, 298, 388, 887, 401, 70, 3, 452, 954, 350, 972, 515, 155, 641, 357, 526, 126, 862, 434, 947, 502, 215, 544, 560, 966, 68, 677, 658, 555, 937, 252, 536, 124, 895, 342, 267, 491, 892, 261, 324, 469, 640, 742, 974, 925, 905, 168, 343, 752, 363, 51, 467, 226, 592, 101, 938, 340, 15, 839, 576, 537, 158, 596, 704, 28, 945, 125, 361, 857, 801, 610, 6, 805, 611, 775, 292, 619, 48, 975, 34, 736, 994, 476, 939, 554, 272, 77, 150, 656, 65, 466, 460, 865, 203, 338, 32, 910, 894, 729, 193, 797, 242, 660, 915, 408, 181, 943, 838, 916, 7, 60, 815, 901, 632, 904, 733, 837, 559, 174, 426, 91, 495, 765, 26, 967, 784, 95, 178, 112, 417, 538, 710, 473, 591, 637, 867, 135, 139, 399, 273, 278, 319, 480, 911, 264, 253, 745, 53, 530, 372, 600, 976, 650, 90, 162, 213, 936, 430, 744, 435, 668, 829, 821, 990, 79, 803, 822, 826, 263, 697, 61, 254, 688, 856, 621, 666, 347, 176, 352, 442, 154, 464, 942, 929, 690, 326, 876, 899, 268, 962, 748, 186, 35, 921, 900, 134, 109, 787, 708, 764, 160, 712, 782, 136, 102, 346, 963, 550, 444, 762, 529, 770, 996, 271, 251, 792, 753, 80, 763, 58, 420, 89, 561, 693, 978, 642, 46, 504, 210, 47, 513, 757, 152, 457, 836, 948, 416, 74, 986, 532, 354, 250, 180, 508, 639, 545, 333, 67, 854, 542, 448, 110, 628, 812, 54, 232, 707, 223, 84, 779, 777, 593, 25, 802, 169, 159, 127, 294, 923, 995, 767, 454, 897, 173, 31, 197, 891, 629, 161, 497, 551, 291, 816, 188, 755, 107, 404, 520, 348, 1000, 122, 177, 382, 205, 817, 189, 85, 670, 400, 211, 29, 93, 751, 557, 672, 881, 754, 393, 62, 852, 196, 353, 331, 24, 599, 760, 531, 11, 281, 303, 968, 471, 14, 115, 574, 359, 106, 728, 204, 614, 768, 563, 42, 673, 144, 396, 649, 175, 312, 794, 462, 835, 373, 172, 913, 732, 884, 806, 131, 500, 17, 335, 842, 920, 718, 977, 439, 709, 57, 482, 850, 185, 257, 694, 501, 647, 38, 305, 433, 991, 489, 461, 458, 484, 703, 798, 201, 314, 783, 436, 737, 567, 443, 235, 13, 236, 296, 845, 475, 717, 828, 349, 731, 833, 695, 843, 882, 924, 45, 572, 392, 395, 795, 722, 451, 43, 880, 217, 811, 449, 360, 240, 184, 638, 675, 580, 558, 698, 565, 450, 76, 517, 886, 870, 999, 922, 431, 384, 5, 633, 740, 81, 888, 20, 799, 387, 820, 419, 378, 202, 221, 4, 682, 951, 59, 368, 391, 230, 18, 63, 855, 148, 669, 516, 909, 206, 858, 78, 772, 713, 566, 871, 270, 934, 965, 440, 598, 330, 819, 246, 898, 362, 41, 286, 983, 889, 681, 606, 405, 861, 397, 730, 394, 277, 785, 615, 953, 875, 243, 603, 389, 120, 800, 332, 528, 88, 171, 300, 719, 325, 233, 780, 370, 981, 685, 950, 315, 445, 128, 414, 71, 429, 83, 50, 477, 738, 791, 761, 244, 958, 691, 824, 302, 834, 345, 860, 973, 571, 98, 552, 809, 424, 403, 825, 671, 774, 534, 262, 280, 123, 364, 369, 601, 130, 299, 684, 36, 604, 248, 807, 651, 622, 893, 788, 827, 30, 313, 274, 485, 129, 73, 198, 156, 355, 914, 52, 624, 969, 308, 505, 952, 987, 336, 356, 407, 92, 183, 840, 256, 970, 167, 662, 229, 142, 351, 635, 209, 781, 714, 97, 699, 562, 577, 859, 247, 830, 679, 227, 877, 653, 514, 376, 586, 19, 304, 926, 82, 311, 631, 474, 21, 266, 583, 711, 191, 87, 427, 509, 237, 997, 385, 187, 182, 116, 428, 874, 912, 648, 409, 607, 259, 848, 940, 214, 118, 747, 465, 105, 133, 659, 609, 228, 663, 643, 587, 66, 398, 928, 533, 725, 179, 143, 689, 665, 832, 652, 831, 151, 935, 137, 616, 282, 339, 683, 636, 896, 620, 878, 917, 147, 374, 103, 492, 113, 328, 716, 411, 72, 907, 494, 964, 573, 459, 879, 40, 902, 418, 998, 119, 9, 310, 318, 667, 220, 705, 634, 157, 773, 564, 873, 918, 69, 75, 371, 692, 548, 37, 290, 446, 140, 276, 238, 425, 377, 486, 415, 64, 906, 199, 626, 927, 163, 992, 479, 602, 413, 410, 547, 776, 630, 582, 664, 623, 317, 931, 194, 166, 463, 721, 883, 367, 496, 285, 766, 121, 406, 814, 726, 512, 381, 423, 149, 212, 549, 192, 190, 522, 108, 481, 930, 49, 16, 145, 96, 27, 22, 337, 437, 100, 750, 12, 301, 723, 589, 358, 680, 804, 971, 258, 447, 438, 493, 283, 524, 402, 293, 646, 10, 260, 375, 540, 790, 422, 957, 231, 218, 383, 701, 498, 146, 329, 959, 605, 793, 960, 864, 919, 255, 988, 868, 946, 584, 541, 734, 455, 847, 207, 265, 117, 644, 702, 941, 170, 297, 908, 153, 979, 506, 222, 841, 1, 241, 588, 327, 523, 94, 456, 553, 739, 472, 743, 249, 2, 245, 769, 932, 866, 208, 961, 8, 44, 453, 487, 421, 756, 23, 386, 686, 519, 655, 511, 789, 720, 535, 869, 608, 625, 380, 984, 365, 771, 578, 525, 933, 269, 618, 982, 195, 851, 200, 657, 510, 341, 432, 322, 706, 810, 696, 715, 581, 307, 468, 654, 111, 678, 568, 320, 956, 507, 786, 749, 114, 796, 165, 288, 483, 627, 595, 758, 503, 885, 441, 741, 989, 890, 570, 724, 597, 316, 488, 478, 284, 846, 543, 759, 818, 56, 590, 617, 470, 104, 309, 645, 55, 33, 813, 676, 853, 569, 366, 138, 944, 661, 275, 575, 99, 985, 490, 687, 903, 321, 239, 289, 344, 808, 823, 86, 224, 287, 225, 546, 306, 778, 219, 849]; | |
| const tests = [ | |
| // Find smallest number | |
| target => { | |
| const map = {}; | |
| for (let i = 0; i < target.length; i++) map[target[i]] = true; | |
| for (let i = 1; i < Number.MAX_VALUE; i++) | |
| if (!map[i]) return i; | |
| }, | |
| // Bubble short | |
| target => { | |
| let swapped; | |
| do { | |
| swapped = false; | |
| for(let i = 0; i < target.length - 1; i++) { | |
| target[i] > target[i+1] | |
| && ([target[i], target[i+1]] = [target[i+1], target[i]]) | |
| && (swapped = true); | |
| } | |
| } while(swapped); | |
| return target; | |
| } | |
| ]; | |
| tests | |
| .map(f => test(f, A, 100)) | |
| .map(({ duration, result }, index) => `#${index}: ${duration}ms (${truncate(JSON.stringify(result))})`) | |
| .forEach(r => console.log(r)); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment