topn.swift

//
//  main.swift
//  topN_2
//
//  Created by Ryan Warsaw on 12/14/17.
//  Copyright © 2017 Ryan Warsaw. All rights reserved.
//

import Foundation

let generateAmount = 10000000; // This is the amount of fake number data we want to generate (randomly).
var dummyNumbersArray: [Int] = []; // This is where we store the fake number data as we generate it.
let nth = 15; // The amount of largest numbers we want to find, given the array of dummy numbers.
var result: [Int] = []; // Where we store and manage the largest number candidates.

// Randomly generate the input for us to work with.
for _ in stride(from: 1, through: generateAmount, by: 1) {
    dummyNumbersArray.append(Int(arc4random_uniform(UInt32.max)))
}

/**
 * We're essentially hacking a binary search function, even if it doesn't find the key it'll tell us exactly
 * where it should be inserted within the ordered list of numbers, which is exactly what we need for this use case.
 **/
func binarySearch<T: Comparable>(_ arr: [T], key: T) -> (lowerBound: Int, upperBound: Int, found: Bool) {
    var lowerBound = 0
    var upperBound = arr.count
    while lowerBound < upperBound {
        let middle = lowerBound + (upperBound - lowerBound) / 2
        if arr[middle] == key {
            return (lowerBound: middle, upperBound: upperBound, found: true)
        } else if arr[middle] < key {
            lowerBound = middle + 1
        } else {
            upperBound = middle
        }
    }
    return (lowerBound: lowerBound, upperBound: upperBound, found: false)
}

/**
 * For testing purposes, we generate a dummy array then iterate through it as a way to emulate the environment
 * that would be expected if you were say, processing a file stream of large size number by number.
 **/
dummyNumbersArray.forEach { number in
    if result.count >= 1 {
        if result.count >= nth {
            // Dramatically reduce the amount of data going through binary search, by eliminating values smaller than
            // than the smallest number in the results array of (N)th size.
            if result[nth - 1] < number {
                let search = binarySearch(result, key: number)
                result.insert(number, at: search.lowerBound)
                result.removeFirst()
            }
        } else {
            let search = binarySearch(result, key: number)
            result.insert(number, at: search.lowerBound)
        }
    } else {
        result.append(number)
    }
}

print(Array(result.reversed()))