Skip to content

Instantly share code, notes, and snippets.

@notcome
Created Jan 24, 2019
Embed
What would you like to do?
Tuned Swift for completely unscientific benchmark
// roughly 1.8x of best tuned solution.
// quite concerning since I have written a pool manually and added a GC for better cache locality.
import Foundation
struct Node {
var x: Int
var y: Int
var left: Int = -1
var right: Int = -1
init(x: Int) {
self.x = x
self.y = Int(arc4random())
}
}
class Tree {
var root: Int = -1
var pool: [Node] = []
var count: Int = 0
public func contains(_ x: Int) -> Bool {
let (lower, middle, upper) = split(root: root, value: x)
root = merge(lower, middle, upper)
return middle != -1
}
public func insert(_ x: Int) {
var (lower, middle, upper) = split(root: root, value: x)
if middle == -1 {
middle = pool.count
pool.append(Node(x: x))
count += 1
}
root = merge(lower, middle, upper)
}
public func erase(_ x: Int) {
let (lower, middle, upper) = split(root: root, value: x)
if middle != -1 {
count -= 1
}
root = merge(lower, upper)
if count * 2 < pool.count && pool.count >= 8192 {
compact()
}
}
private func move(node: Int, dest: inout [Node]) -> Int {
if node == -1 {
return -1
}
let index = dest.count
dest.append(pool[node])
dest[index].left = move(node: dest[index].left, dest: &dest)
dest[index].right = move(node: dest[index].right, dest: &dest)
return index
}
private func compact() {
var newPool = [Node]()
newPool.reserveCapacity(count)
root = move(node: root, dest: &newPool)
pool = newPool
}
private func merge(_ lower: Int, _ upper: Int) -> Int {
guard lower != -1 else {
return upper
}
guard upper != -1 else {
return lower
}
if pool[lower].y < pool[upper].y {
pool[lower].right = merge(pool[lower].right, upper)
return lower
} else {
pool[upper].left = merge(lower, pool[upper].left)
return upper
}
}
private func merge(_ lower: Int, _ middle: Int, _ upper: Int) -> Int {
let lower = merge(lower, middle)
return merge(lower, upper)
}
typealias BinarySplit = (lower: Int, upper: Int)
typealias TernarySplit = (lower: Int, middle: Int, upper: Int)
private func splitBinary(root: Int, value: Int) -> BinarySplit {
guard root != -1 else {
return (-1, -1)
}
if pool[root].x < value {
let (lower, upper) = splitBinary(root: pool[root].right, value: value)
pool[root].right = lower
return (root, upper)
} else {
let (lower, upper) = splitBinary(root: pool[root].left, value: value)
pool[root].left = upper
return (lower, root)
}
}
private func split(root: Int, value: Int) -> TernarySplit {
let (lower, equalGreater) = splitBinary(root: root, value: value)
let (equal, greater) = splitBinary(root: equalGreater, value: value + 1)
return (lower: lower, middle: equal, upper: greater)
}
}
let tree = Tree()
var cur = 5;
var res = 0
for i in 1..<1000000 {
let a = i % 3
cur = (cur * 57 + 43) % 10007
switch a {
case 0: tree.insert(cur)
case 1: tree.erase(cur)
case 2: if tree.contains(cur) { res += 1 }
default: break
}
}
print(res)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment