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
|
//===--- TwoSum.swift -----------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2021 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
// This test is solves 2SUM problem:
// Given an array and a number C, find elements A and B such that A+B = C
import TestsUtils
public let benchmarks =
BenchmarkInfo(
name: "TwoSum",
runFunction: run_TwoSum,
tags: [.validation, .api, .Dictionary, .Array, .algorithm],
legacyFactor: 2)
let array = [
959, 81, 670, 727, 416, 171, 401, 398, 707, 596, 200, 9, 414, 98, 43,
352, 752, 158, 593, 418, 240, 912, 542, 445, 429, 456, 993, 618, 52, 649,
759, 190, 126, 306, 966, 37, 787, 981, 606, 372, 597, 901, 158, 284, 809,
820, 173, 538, 644, 428, 932, 967, 962, 959, 233, 467, 220, 8, 729, 889,
277, 494, 554, 670, 91, 657, 606, 248, 644, 8, 366, 815, 567, 993, 696,
763, 800, 531, 301, 863, 680, 703, 279, 388, 871, 124, 302, 617, 410, 366,
813, 599, 543, 508, 336, 312, 212, 86, 524, 64, 641, 533, 207, 893, 146,
534, 104, 888, 534, 464, 423, 583, 365, 420, 642, 514, 336, 974, 846, 437,
604, 121, 180, 794, 278, 467, 818, 603, 537, 167, 169, 704, 9, 843, 555,
154, 598, 566, 676, 682, 828, 128, 875, 445, 918, 505, 393, 571, 3, 406,
719, 165, 505, 750, 396, 726, 404, 391, 532, 403, 728, 240, 89, 917, 665,
561, 282, 302, 438, 714, 6, 290, 939, 200, 788, 128, 773, 900, 934, 772,
130, 884, 60, 870, 812, 750, 349, 35, 155, 905, 595, 806, 771, 443, 304,
283, 404, 905, 861, 820, 338, 380, 709, 927, 42, 478, 789, 656, 106, 218,
412, 453, 262, 864, 701, 686, 770, 34, 624, 597, 843, 913, 966, 230, 942,
112, 991, 299, 669, 399, 630, 943, 934, 448, 62, 745, 917, 397, 440, 286,
875, 22, 989, 235, 732, 906, 923, 643, 853, 68, 48, 524, 86, 89, 688,
224, 546, 73, 963, 755, 413, 524, 680, 472, 19, 996, 81, 100, 338, 626,
911, 358, 887, 242, 159, 731, 494, 985, 83, 597, 98, 270, 909, 828, 988,
684, 622, 499, 932, 299, 449, 888, 533, 801, 844, 940, 642, 501, 513, 735,
674, 211, 394, 635, 372, 213, 618, 280, 792, 487, 605, 755, 584, 163, 358,
249, 784, 153, 166, 685, 264, 457, 677, 824, 391, 830, 310, 629, 591, 62,
265, 373, 195, 803, 756, 601, 592, 843, 184, 220, 155, 396, 828, 303, 553,
778, 477, 735, 430, 93, 464, 306, 579, 828, 759, 809, 916, 759, 336, 926,
776, 111, 746, 217, 585, 441, 928, 236, 959, 417, 268, 200, 231, 181, 228,
627, 675, 814, 534, 90, 665, 1, 604, 479, 598, 109, 370, 719, 786, 700,
591, 536, 7, 147, 648, 864, 162, 404, 536, 768, 175, 517, 394, 14, 945,
865, 490, 630, 963, 49, 904, 277, 16, 349, 301, 840, 817, 590, 738, 357,
199, 581, 601, 33, 659, 951, 640, 126, 302, 632, 265, 894, 892, 587, 274,
487, 499, 789, 954, 652, 825, 512, 170, 882, 269, 471, 571, 185, 364, 217,
427, 38, 715, 950, 808, 270, 746, 830, 501, 264, 581, 211, 466, 970, 395,
610, 930, 885, 696, 568, 920, 487, 764, 896, 903, 241, 894, 773, 896, 341,
126, 22, 420, 959, 691, 207, 745, 126, 873, 341, 166, 127, 108, 426, 497,
681, 796, 430, 367, 363
]
@inline(never)
public func run_TwoSum(_ n: Int) {
var i1: Int?
var i2: Int?
var dict: Dictionary<Int, Int> = [:]
for _ in 1...n {
for sum in 500..<600 {
dict = [:]
i1 = nil
i2 = nil
for n in 0..<array.count {
if let m = dict[sum - array[n]] {
i1 = m
i2 = n
break
}
dict[array[n]] = n
}
check(i1 != nil && i2 != nil)
check(sum == array[i1!] + array[i2!])
}
}
}
|
