| //===--- DictTest.swift ---------------------------------------------------===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2017 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 |
| // |
| //===----------------------------------------------------------------------===// |
| |
| import TestsUtils |
| |
| @inline(never) |
| public func run_Dictionary(scale: Int) { |
| let Input = [ |
| // Text from http://en.wikipedia.org/wiki/Hash_table |
| "hash", "table", |
| "in", "computing", "a", "hash", "table", "also", "hash", "map", "is", |
| "a", "data", "structure", "used", "to", "implement", "an", "associative", |
| "array", "a", "structure", "that", "can", "map", "keys", "to", "values", |
| "a", "hash", "table", "uses", "a", "hash", "function", "to", "compute", |
| "an", "index", "into", "an", "array", "of", "buckets", "or", "slots", |
| "from", "which", "the", "correct", "value", "can", "be", "found", |
| "ideally", "the", "hash", "function", "will", "assign", "each", "key", |
| "to", "a", "unique", "bucket", "but", "this", "situation", "is", |
| "rarely", "achievable", "in", "practice", "usually", "some", "keys", |
| "will", "hash", "to", "the", "same", "bucket", "instead", "most", "hash", |
| "table", "designs", "assume", "that", "hash", "collisions", "different", |
| "keys", "that", "are", "assigned", "by", "the", "hash", "function", "to", |
| "the", "same", "bucket", "will", "occur", "and", "must", "be", |
| "accommodated", "in", "some", "way", "in", "a", "well", "dimensioned", |
| "hash", "table", "the", "average", "cost", "number", "of", |
| "instructions", "for", "each", "lookup", "is", "independent", "of", |
| "the", "number", "of", "elements", "stored", "in", "the", "table", |
| "many", "hash", "table", "designs", "also", "allow", "arbitrary", |
| "insertions", "and", "deletions", "of", "key", "value", "pairs", "at", |
| "amortized", "constant", "average", "cost", "per", "operation", "in", |
| "many", "situations", "hash", "tables", "turn", "out", "to", "be", |
| "more", "efficient", "than", "search", "trees", "or", "any", "other", |
| "table", "lookup", "structure", "for", "this", "reason", "they", "are", |
| "widely", "used", "in", "many", "kinds", "of", "computer", "software", |
| "particularly", "for", "associative", "arrays", "database", "indexing", |
| "caches", "and", "sets", |
| |
| "hashing", |
| "the", "idea", "of", "hashing", "is", "to", "distribute", "the", |
| "entries", "key", "value", "pairs", "across", "an", "array", "of", |
| "buckets", "given", "a", "key", "the", "algorithm", "computes", "an", |
| "index", "that", "suggests", "where", "the", "entry", "can", "be", |
| "found", "index", "f", "key", "array", "size", "often", "this", "is", |
| "done", "in", "two", "steps", "hash", "hashfunc", "key", "index", "hash", |
| "array", "size", "in", "this", "method", "the", "hash", "is", |
| "independent", "of", "the", "array", "size", "and", "it", "is", "then", |
| "reduced", "to", "an", "index", "a", "number", "between", "and", "array", |
| "size", "using", "the", "modulus", "operator", "in", "the", "case", |
| "that", "the", "array", "size", "is", "a", "power", "of", "two", "the", |
| "remainder", "operation", "is", "reduced", "to", "masking", "which", |
| "improves", "speed", "but", "can", "increase", "problems", "with", "a", |
| "poor", "hash", "function", |
| |
| "choosing", "a", "good", "hash", "function", |
| "a", "good", "hash", "function", "and", "implementation", "algorithm", |
| "are", "essential", "for", "good", "hash", "table", "performance", "but", |
| "may", "be", "difficult", "to", "achieve", "a", "basic", "requirement", |
| "is", "that", "the", "function", "should", "provide", "a", "uniform", |
| "distribution", "of", "hash", "values", "a", "non", "uniform", |
| "distribution", "increases", "the", "number", "of", "collisions", "and", |
| "the", "cost", "of", "resolving", "them", "uniformity", "is", |
| "sometimes", "difficult", "to", "ensure", "by", "design", "but", "may", |
| "be", "evaluated", "empirically", "using", "statistical", "tests", "e", |
| "g", "a", "pearson", "s", "chi", "squared", "test", "for", "discrete", |
| "uniform", "distributions", "the", "distribution", "needs", "to", "be", |
| "uniform", "only", "for", "table", "sizes", "that", "occur", "in", "the", |
| "application", "in", "particular", "if", "one", "uses", "dynamic", |
| "resizing", "with", "exact", "doubling", "and", "halving", "of", "the", |
| "table", "size", "s", "then", "the", "hash", "function", "needs", "to", |
| "be", "uniform", "only", "when", "s", "is", "a", "power", "of", "two", |
| "on", "the", "other", "hand", "some", "hashing", "algorithms", "provide", |
| "uniform", "hashes", "only", "when", "s", "is", "a", "prime", "number", |
| "for", "open", "addressing", "schemes", "the", "hash", "function", |
| "should", "also", "avoid", "clustering", "the", "mapping", "of", "two", |
| "or", "more", "keys", "to", "consecutive", "slots", "such", "clustering", |
| "may", "cause", "the", "lookup", "cost", "to", "skyrocket", "even", "if", |
| "the", "load", "factor", "is", "low", "and", "collisions", "are", |
| "infrequent", "the", "popular", "multiplicative", "hash", "3", "is", |
| "claimed", "to", "have", "particularly", "poor", "clustering", |
| "behavior", "cryptographic", "hash", "functions", "are", "believed", |
| "to", "provide", "good", "hash", "functions", "for", "any", "table", |
| "size", "s", "either", "by", "modulo", "reduction", "or", "by", "bit", |
| "masking", "they", "may", "also", "be", "appropriate", "if", "there", |
| "is", "a", "risk", "of", "malicious", "users", "trying", "to", |
| "sabotage", "a", "network", "service", "by", "submitting", "requests", |
| "designed", "to", "generate", "a", "large", "number", "of", "collisions", |
| "in", "the", "server", "s", "hash", "tables", "however", "the", "risk", |
| "of", "sabotage", "can", "also", "be", "avoided", "by", "cheaper", |
| "methods", "such", "as", "applying", "a", "secret", "salt", "to", "the", |
| "data", "or", "using", "a", "universal", "hash", "function", |
| |
| "perfect", "hash", "function", |
| "if", "all", "keys", "are", "known", "ahead", "of", "time", "a", |
| "perfect", "hash", "function", "can", "be", "used", "to", "create", "a", |
| "perfect", "hash", "table", "that", "has", "no", "collisions", "if", |
| "minimal", "perfect", "hashing", "is", "used", "every", "location", "in", |
| "the", "hash", "table", "can", "be", "used", "as", "well", "perfect", |
| "hashing", "allows", "for", "constant", "time", "lookups", "in", "the", |
| "worst", "case", "this", "is", "in", "contrast", "to", "most", |
| "chaining", "and", "open", "addressing", "methods", "where", "the", |
| "time", "for", "lookup", "is", "low", "on", "average", "but", "may", |
| "be", "very", "large", "proportional", "to", "the", "number", "of", |
| "entries", "for", "some", "sets", "of", "keys" |
| ] |
| |
| var Dict: Dictionary<String, Bool> = [:] |
| let N = 5*scale |
| |
| // Check performance of filling the dictionary: |
| for _ in 1...N { |
| Dict = [:] |
| for word in Input { |
| Dict[word] = true |
| } |
| } |
| CheckResults(Dict.count == 270, |
| "IncorrectResults in DictTest: \(Dict.count) != 270.") |
| |
| // Check performance of searching in the dictionary: |
| // Fill the dictionary with words from the first half of the text |
| Dict = [:] |
| for i in 0 ..< Input.count/2 { |
| let word = Input[i] |
| Dict[word] = true |
| } |
| |
| // Count number of words from the first half in the entire text |
| var count = 0 |
| for _ in 1...N { |
| for word in Input { |
| if Dict[word] != nil { |
| count += 1 |
| } |
| } |
| } |
| CheckResults(count == N*541, |
| "IncorrectResults in DictTest: \(count) != \(N*541).") |
| } |
| |
| class Box<T : Hashable> : Hashable { |
| var value: T |
| |
| init(_ v: T) { |
| value = v |
| } |
| |
| var hashValue: Int { |
| return value.hashValue |
| } |
| |
| static func ==<T: Equatable>(lhs: Box<T>, rhs: Box<T>) -> Bool { |
| return lhs.value == rhs.value |
| } |
| } |
| |
| @inline(never) |
| public func run_DictionaryOfObjects(scale: Int) { |
| let Input = [ |
| // Text from http://en.wikipedia.org/wiki/Hash_table |
| "hash", "table", |
| "in", "computing", "a", "hash", "table", "also", "hash", "map", "is", |
| "a", "data", "structure", "used", "to", "implement", "an", "associative", |
| "array", "a", "structure", "that", "can", "map", "keys", "to", "values", |
| "a", "hash", "table", "uses", "a", "hash", "function", "to", "compute", |
| "an", "index", "into", "an", "array", "of", "buckets", "or", "slots", |
| "from", "which", "the", "correct", "value", "can", "be", "found", |
| "ideally", "the", "hash", "function", "will", "assign", "each", "key", |
| "to", "a", "unique", "bucket", "but", "this", "situation", "is", |
| "rarely", "achievable", "in", "practice", "usually", "some", "keys", |
| "will", "hash", "to", "the", "same", "bucket", "instead", "most", "hash", |
| "table", "designs", "assume", "that", "hash", "collisions", "different", |
| "keys", "that", "are", "assigned", "by", "the", "hash", "function", "to", |
| "the", "same", "bucket", "will", "occur", "and", "must", "be", |
| "accommodated", "in", "some", "way", "in", "a", "well", "dimensioned", |
| "hash", "table", "the", "average", "cost", "number", "of", |
| "instructions", "for", "each", "lookup", "is", "independent", "of", |
| "the", "number", "of", "elements", "stored", "in", "the", "table", |
| "many", "hash", "table", "designs", "also", "allow", "arbitrary", |
| "insertions", "and", "deletions", "of", "key", "value", "pairs", "at", |
| "amortized", "constant", "average", "cost", "per", "operation", "in", |
| "many", "situations", "hash", "tables", "turn", "out", "to", "be", |
| "more", "efficient", "than", "search", "trees", "or", "any", "other", |
| "table", "lookup", "structure", "for", "this", "reason", "they", "are", |
| "widely", "used", "in", "many", "kinds", "of", "computer", "software", |
| "particularly", "for", "associative", "arrays", "database", "indexing", |
| "caches", "and", "sets", |
| |
| "hashing", |
| "the", "idea", "of", "hashing", "is", "to", "distribute", "the", |
| "entries", "key", "value", "pairs", "across", "an", "array", "of", |
| "buckets", "given", "a", "key", "the", "algorithm", "computes", "an", |
| "index", "that", "suggests", "where", "the", "entry", "can", "be", |
| "found", "index", "f", "key", "array", "size", "often", "this", "is", |
| "done", "in", "two", "steps", "hash", "hashfunc", "key", "index", "hash", |
| "array", "size", "in", "this", "method", "the", "hash", "is", |
| "independent", "of", "the", "array", "size", "and", "it", "is", "then", |
| "reduced", "to", "an", "index", "a", "number", "between", "and", "array", |
| "size", "using", "the", "modulus", "operator", "in", "the", "case", |
| "that", "the", "array", "size", "is", "a", "power", "of", "two", "the", |
| "remainder", "operation", "is", "reduced", "to", "masking", "which", |
| "improves", "speed", "but", "can", "increase", "problems", "with", "a", |
| "poor", "hash", "function", |
| |
| "choosing", "a", "good", "hash", "function", |
| "a", "good", "hash", "function", "and", "implementation", "algorithm", |
| "are", "essential", "for", "good", "hash", "table", "performance", "but", |
| "may", "be", "difficult", "to", "achieve", "a", "basic", "requirement", |
| "is", "that", "the", "function", "should", "provide", "a", "uniform", |
| "distribution", "of", "hash", "values", "a", "non", "uniform", |
| "distribution", "increases", "the", "number", "of", "collisions", "and", |
| "the", "cost", "of", "resolving", "them", "uniformity", "is", |
| "sometimes", "difficult", "to", "ensure", "by", "design", "but", "may", |
| "be", "evaluated", "empirically", "using", "statistical", "tests", "e", |
| "g", "a", "pearson", "s", "chi", "squared", "test", "for", "discrete", |
| "uniform", "distributions", "the", "distribution", "needs", "to", "be", |
| "uniform", "only", "for", "table", "sizes", "that", "occur", "in", "the", |
| "application", "in", "particular", "if", "one", "uses", "dynamic", |
| "resizing", "with", "exact", "doubling", "and", "halving", "of", "the", |
| "table", "size", "s", "then", "the", "hash", "function", "needs", "to", |
| "be", "uniform", "only", "when", "s", "is", "a", "power", "of", "two", |
| "on", "the", "other", "hand", "some", "hashing", "algorithms", "provide", |
| "uniform", "hashes", "only", "when", "s", "is", "a", "prime", "number", |
| "for", "open", "addressing", "schemes", "the", "hash", "function", |
| "should", "also", "avoid", "clustering", "the", "mapping", "of", "two", |
| "or", "more", "keys", "to", "consecutive", "slots", "such", "clustering", |
| "may", "cause", "the", "lookup", "cost", "to", "skyrocket", "even", "if", |
| "the", "load", "factor", "is", "low", "and", "collisions", "are", |
| "infrequent", "the", "popular", "multiplicative", "hash", "3", "is", |
| "claimed", "to", "have", "particularly", "poor", "clustering", |
| "behavior", "cryptographic", "hash", "functions", "are", "believed", |
| "to", "provide", "good", "hash", "functions", "for", "any", "table", |
| "size", "s", "either", "by", "modulo", "reduction", "or", "by", "bit", |
| "masking", "they", "may", "also", "be", "appropriate", "if", "there", |
| "is", "a", "risk", "of", "malicious", "users", "trying", "to", |
| "sabotage", "a", "network", "service", "by", "submitting", "requests", |
| "designed", "to", "generate", "a", "large", "number", "of", "collisions", |
| "in", "the", "server", "s", "hash", "tables", "however", "the", "risk", |
| "of", "sabotage", "can", "also", "be", "avoided", "by", "cheaper", |
| "methods", "such", "as", "applying", "a", "secret", "salt", "to", "the", |
| "data", "or", "using", "a", "universal", "hash", "function", |
| |
| "perfect", "hash", "function", |
| "if", "all", "keys", "are", "known", "ahead", "of", "time", "a", |
| "perfect", "hash", "function", "can", "be", "used", "to", "create", "a", |
| "perfect", "hash", "table", "that", "has", "no", "collisions", "if", |
| "minimal", "perfect", "hashing", "is", "used", "every", "location", "in", |
| "the", "hash", "table", "can", "be", "used", "as", "well", "perfect", |
| "hashing", "allows", "for", "constant", "time", "lookups", "in", "the", |
| "worst", "case", "this", "is", "in", "contrast", "to", "most", |
| "chaining", "and", "open", "addressing", "methods", "where", "the", |
| "time", "for", "lookup", "is", "low", "on", "average", "but", "may", |
| "be", "very", "large", "proportional", "to", "the", "number", "of", |
| "entries", "for", "some", "sets", "of", "keys" |
| ] |
| |
| var Dict: Dictionary<Box<String>, Box<Bool>> = [:] |
| let N = 5*scale |
| |
| // Check performance of filling the dictionary: |
| for _ in 1...N { |
| Dict = [:] |
| for word in Input { |
| Dict[Box(word)] = Box(true) |
| } |
| } |
| CheckResults(Dict.count == 270, |
| "IncorrectResults in DictTest: \(Dict.count) != 270.") |
| |
| // Check performance of searching in the dictionary: |
| // Fill the dictionary with words from the first half of the text |
| Dict = [:] |
| for i in 0 ..< Input.count/2 { |
| let word = Input[i] |
| Dict[Box(word)] = Box(true) |
| } |
| |
| // Count number of words from the first half in the entire text |
| var count = 0 |
| for _ in 1...N { |
| for word in Input { |
| if Dict[Box(word)] != nil { |
| count += 1 |
| } |
| } |
| } |
| CheckResults(count == N*541, |
| "IncorrectResults in DictTestAllObjects: \(count) != \(N*541).") |
| } |
