CMTime Segment Finder (binary search) - kirseia/study GitHub Wiki

특정 시간에 포함되는 아이템을 모두 찾기

단, 아이템은 sorted CMTimeRange Array 라고 가정한다.

Source Ver.2

아래 ver.1 에 문제가 있어서 수정했음

        let timeRange1 = CMTimeRange(start: .zero, end: 2.5.time)
        let timeRange8 = CMTimeRange(start: 2.5.time, end: 10.0.time)
        let timeRange2 = CMTimeRange(start: 3.0.time, end: 5.0.time)
        let timeRange3 = CMTimeRange(start: 4.0.time, end: 5.5.time)
        let timeRange4 = CMTimeRange(start: 4.5.time, end: 7.0.time)
        let timeRange5 = CMTimeRange(start: 7.0.time, end: 7.5.time)
        let timeRange6 = CMTimeRange(start: 7.7.time, end: 8.0.time)
        let timeRange7 = CMTimeRange(start: 9.0.time, end: 15.0.time)

이런식으로 있다면 sort 가 start 기준으로만 되어있다고 할 때... end 를 찾을 때 문제가 발생한다. 따라서 binary search 로 lower/upper bound 를 찾는건 문제가 됨.

그래서 binary search 는 한쪽만 찾는 것으로 처리했다. 대신, 전체 시간 기준으로 앞쪽이면 앞부터, 뒤 쪽이면 뒤부터 찾는 방식을 도입했음.

import AVFoundation

extension Double {
    var time: CMTime {
        return CMTime(seconds: self, preferredTimescale: 1000)
    }
}

extension CMTime {
    public func isNearlyEqualTo(time: CMTime, _ tolerance: CMTime = CMTime(value: 1, timescale: 600)) -> Bool {
        let delta = CMTimeAbsoluteValue(self - time)
        return delta < tolerance
    }
    
}

protocol TimeRange {
    var range: CMTimeRange { get set }
}

// 비교용
class TimeRangeSearch<T> where T: TimeRange {
    var array: [T] = []
    
    func list(on time: CMTime) -> [T] {
        return array.filter { $0.range.containsTime(time) }
    }
}

// FastTimeRangeSearch 가 약 30%정도 빠름
// (단일 건으로는 엄청난 차이는 나지 않으나 매 frame 마다 호출될테니 효과는 있을 것으로 보임)
class FastTimeRangeSearch<T> where T: TimeRange {
    var array: [T] = [] {
        didSet {
            startSortArray = array.sorted { (lhs, rhs) -> Bool in
                return lhs.range.start < rhs.range.start
            }
            
            startTime = startSortArray.first?.range.start ?? .zero
            
            endSortArray = array.sorted(by: { (lhs, rhs) -> Bool in
                return lhs.range.end < rhs.range.end
            })
            
            endTime = endSortArray.last?.range.end ?? .zero
        }
    }
    
    init() {
        
    }
    
    init(array: [T]) {
        self.array = array
    }
    
    private var startSortArray: [T] = []
    private var endSortArray: [T] = []
    
    private var startTime: CMTime = .zero
    private var endTime: CMTime = .zero
    
    func list(on time: CMTime) -> [T] {
        // 양방향으로 binarySearch 는 불가해서 그나마 범위를 줄이기 위해 앞/뒤 먼저 찾을 범위를 선택
        let startSearch = abs((startTime - time).seconds) < abs((endTime - time).seconds)
        
        var lowerIndex = 0
        var upperIndex = array.count
        
        if startSearch {
            guard let _upperIndex = binarySearchDirection(time: time, isStart: true, range: 0 ..< self.array.count) else {
                return []
            }
            
            upperIndex = _upperIndex
        } else {
            guard let _lowerIndex = binarySearchDirection(time: time, isStart: false, range: 0 ..< self.array.count) else {
                return []
            }
            
            lowerIndex = _lowerIndex
        }
        
        var results: [T] = []
        for index in (lowerIndex..<upperIndex) {
            let item = startSortArray[index]
            if item.range.containsTime(time) {
                results.append(item)
            }
        }
        
        return results
    }
    
    private func binarySearchDirection(time: CMTime, isStart: Bool, range: Range<Int>) -> Int? {
        if range.lowerBound >= range.upperBound {
            let index = range.lowerBound - 1
            if index < 0 {
                return nil
            } else if index < array.count {
                if isStart {
                    return startSortArray[index].range.containsTime(time) ? index + 1 : nil
                } else {
                    return endSortArray[index].range.containsTime(time) ? index : nil
                }
            } else {
                return nil
            }
        }
        
        let midIndex:Int = range.lowerBound + (range.upperBound - range.lowerBound) / 2
        let targetArray = isStart ? startSortArray : endSortArray
        
        let item = targetArray[midIndex]
        let compareValue = isStart ? item.range.start : item.range.end
        
        if compareValue.isNearlyEqualTo(time: time, 0.01.time) {
            return isStart ? midIndex + 1 : midIndex
        } else if compareValue >= time {
            return binarySearchDirection(time: time, isStart: isStart, range: range.lowerBound ..< midIndex)
        } else {
            return binarySearchDirection(time: time, isStart: isStart, range: midIndex + 1 ..< range.upperBound)
        }
    }
}

Test Code

import XCTest
import AVFoundation
@testable import testFramework

class testFrameworkTests: XCTestCase {
    struct TimeData: TimeRange, Equatable {
        var range: CMTimeRange
        
        public static func == (lhs: TimeData, rhs: TimeData) -> Bool {
            return CMTimeRangeEqual(lhs.range, rhs.range)
        }
    }
    
    let timeRangeSearch = FastTimeRangeSearch<TimeData>()
    
    override func setUp() {
        let timeRange0 = TimeData(range: CMTimeRange.init(start: 0.time, end: 2.5.time))
        let timeRange1 = TimeData(range: CMTimeRange.init(start: 2.0.time, end: 10.0.time))
        let timeRange2 = TimeData(range: CMTimeRange.init(start: 3.0.time, end: 5.0.time))
        let timeRange3 = TimeData(range: CMTimeRange.init(start: 4.0.time, end: 5.5.time))
        let timeRange4 = TimeData(range: CMTimeRange.init(start: 4.5.time, end: 7.0.time))
        let timeRange5 = TimeData(range: CMTimeRange.init(start: 7.0.time, end: 7.5.time))
        let timeRange6 = TimeData(range: CMTimeRange.init(start: 7.7.time, end: 8.0.time))
        let timeRange7 = TimeData(range: CMTimeRange.init(start: 9.0.time, end: 15.0.time))
        
        timeRangeSearch.array = [timeRange0, timeRange1, timeRange2, timeRange3,
                                 timeRange4, timeRange5, timeRange6, timeRange7]
    }
    
    func testBinarySearch1() {
        let result1 = timeRangeSearch.list(on: 1.0.time)
        XCTAssertEqual(result1[0], timeRangeSearch.array[0])
    }
    
    func testBinarySearch2() {
        let result3 = timeRangeSearch.list(on: 100.0.time)
        XCTAssertEqual(result3.count, 0)
    }
    
    func testBinarySearch3() {
        let result4 = timeRangeSearch.list(on: 4.5.time)
        let data = timeRangeSearch.array
        XCTAssertEqual(result4, [data[1], data[2], data[3], data[4]])
    }
    
    func testBinarySearch4() {
        let result2 = timeRangeSearch.list(on: 5.7.time)
        let data = timeRangeSearch.array
        XCTAssertEqual(result2, [data[1], data[4]])
    }
    
}

Source Ver.1

import AVFoundation

extension Double {
    var time: CMTime {
        return CMTime(seconds: self, preferredTimescale: 600)
    }
}

extension CMTime {
    public func isNearlyEqualTo(time: CMTime, _ tolerance: CMTime = CMTime(value: 1, timescale: 600)) -> Bool {
        let delta = CMTimeAbsoluteValue(self - time)
        return delta < tolerance
    }
    
}


extension Array {
    func binarySsearch(time: CMTime) -> [Element] {
        guard self.first is CMTimeRange else {
            return []
        }
        
        guard let lowIndex = binarySearchDirection(time: time,
                                                   isStart: true,
                                                   range: 0 ..< self.count) else {
            return []
        }
        
        guard let upperIndex = binarySearchDirection(time: time,
                                                     isStart: false,
                                                     range: 0 ..< self.count) else {
            return []
        }
        
        if lowIndex > upperIndex {
            return []
        }
        
        let range = lowIndex...upperIndex
        print(range)
        
        return self.enumerated().filter({ (item) -> Bool in
            range.contains(item.offset)
        }).map({ (item) -> Element in
            return item.element
        })
    }
    
    func binarySearchDirection(time: CMTime, isStart:Bool, range: Range<Int>) -> Int? {
        guard self is [CMTimeRange] else {
            return nil
        }
        
        if range.lowerBound >= range.upperBound {
            let index = range.lowerBound + (isStart ? 0 : -1)
            if index < self.count, let timeRange = self[index] as? CMTimeRange {
                return timeRange.containsTime(time) ? index : nil
            } else {
                return nil
            }
        }
        
        let midIndex:Int = range.lowerBound + (range.upperBound - range.lowerBound) / 2
        
        guard let timeRange = self[midIndex] as? CMTimeRange else {
            preconditionFailure("impossible")
        }

        let compareValue = isStart ? timeRange.end : timeRange.start
        
        if compareValue.isNearlyEqualTo(time: time, 0.01.time) {
            return midIndex
        } else if compareValue >= time {
            return binarySearchDirection(time: time, isStart: isStart, range: range.lowerBound ..< midIndex)
        } else {
            return binarySearchDirection(time: time, isStart: isStart, range: midIndex + 1 ..< range.upperBound)
        }
        
    }
}

test code

    var data:[CMTimeRange] = []
    override func setUp() {
        // Put setup code here. This method is called before the invocation of each test method in the class.
        let timeRange1 = CMTimeRange(start: .zero, end: 2.5.time)
        let timeRange2 = CMTimeRange(start: 3.0.time, end: 5.0.time)
        let timeRange3 = CMTimeRange(start: 4.0.time, end: 5.5.time)
        let timeRange4 = CMTimeRange(start: 4.5.time, end: 7.0.time)
        let timeRange5 = CMTimeRange(start: 7.0.time, end: 7.5.time)
        let timeRange6 = CMTimeRange(start: 7.7.time, end: 8.0.time)
        let timeRange7 = CMTimeRange(start: 9.0.time, end: 15.0.time)
        
        
        data = [timeRange1, timeRange2, timeRange3,
                                  timeRange4, timeRange5, timeRange6, timeRange7]
        
        data.sort { (lhs, rhs) -> Bool in
            return lhs.start < rhs.start
        }
    }

    override func tearDown() {
        // Put teardown code here. This method is called after the invocation of each test method in the class.
    }

    func testBinarySearch1() {
        let result1 = data.binarySsearch(time: 1.0.time)
        XCTAssertEqual(result1[0], data[0])
        
        let result2 = data.binarySsearch(time: 5.7.time)
        XCTAssertEqual(result2.count, 1)
    }
    
    func testBinarySearch2() {
        let result3 = data.binarySsearch(time: 100.0.time)
        XCTAssertEqual(result3.count, 0)
    }
    
    func testBinarySearch3() {
        let result4 = data.binarySsearch(time: 4.5.time)
        XCTAssertEqual(result4, [data[1], data[2], data[3]])
    }