arrays - array.count 和 array[0 ...< index] 会减慢二进制搜索的速度吗?
问题描述
今天我做了一个工作测试,被要求搜索一个整数数组,这就是问题:
本练习的目标是检查数组中是否存在数字。
规格:
这些项目是按升序排列的整数。
该数组最多可包含 100 万个项目
实现函数existsInArray(_ numbers: [Int], _ k: Int)如果k属于numbers则返回true,否则函数应该返回false。
例子:
let numbers = [-9, 14, 37, 102] existsInArray(numbers, 102) // returns true existsInArray(numbers, 36) //returns false
注意:尽量节省 CPU 周期
好的,所以我给出了我的答案,即下面的代码并等待结果
func existsInArray(_ numbers: [Int], _ k: Int) -> Bool {
if numbers.isEmpty {
return false
}
let numbersHalfIndex: Int = (numbers.count/2)
if k == numbers[numbersHalfIndex] {
return true
} else if k != numbers[0] && numbers.count == 1 {
return false
} else if k <= numbers[numbersHalfIndex] {
let leftHalfNumbersArray = numbers[0 ..< numbersHalfIndex]
return existsInArray(Array(leftHalfNumbersArray), k)
} else if k > numbers[numbersHalfIndex] {
let rightHalfNumbersArray = numbers[numbersHalfIndex ..< numbers.count]
return existsInArray(Array(rightHalfNumbersArray), k)
} else {
return false
}
}
事实证明,“解决方案无法在合理的时间内使用 100 万个项目”,现在我不知道我做错了什么,因为二进制搜索的速度非常快。
我唯一的猜测是number.count或numbers[0 ...< numbersHalfIndex]或numbers[numbersHalfIndex ...< number.count] 可能会使一切都比预期的要慢。
我是绊倒还是什么?
编辑:如果有人好奇,我测试了我的代码和 Martin R 代码,看看使用 ArraySlice 对时间的影响有多大。我使用了一个从 0 开始按升序排列的 100.000.000 个元素的数组。这是我捕获时间的方法:
print("////////// MINE //////////")
var startTime = CFAbsoluteTimeGetCurrent()
print(existsInArray(numbers, 0))
var timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
print("Time elapsed for mine: \(timeElapsed) s.")
print("////////// Martin R //////////")
counter = 0
startTime = CFAbsoluteTimeGetCurrent()
print(existsInArrayOptimal(numbers, 0))
timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
print("Time elapsed for Martin R: \(timeElapsed) s.")
结果如下:
////////// 矿 //////////
真的
我的时间过去了:
1.2008800506591797 秒。
///////// 马丁 R //////////
真的
Martin R 经过的时间:0.00012993812561035156 秒。
它快了大约 1000 倍!
解决方案
访问number.count
不是问题,因为这是数组的 O(1) 操作。切片numbers[0 ...< numbersHalfIndex]
也不是问题。但是Array(leftHalfNumbersArray)
从切片创建一个新数组,并复制所有元素。
有两种可能的方法可以避免这种情况:
- 更新数组索引(用于当前搜索范围的下限和上限),而不是创建向下递归传递的数组。
- 将数组切片向下传递。切片与原始数组共享元素(只要它们没有变异)。
第二种方法的演示:
func existsInArray(_ numbers: ArraySlice<Int>, _ k: Int) -> Bool {
if numbers.isEmpty {
return false
}
let numbersHalfIndex = numbers.startIndex + numbers.count / 2
if k == numbers[numbersHalfIndex] {
return true
} else if k < numbers[numbersHalfIndex] {
return existsInArray(numbers[..<numbersHalfIndex], k)
} else {
return existsInArray(numbers[(numbersHalfIndex + 1)...], k)
}
}
请注意,数组切片与原始数组共享它们的索引,因此索引不一定从零开始。这就是为什么numbers.startIndex
用于指数计算。
还有一个包装函数,它接受一个“真实的”数组参数:
func existsInArray(_ numbers: [Int], _ k: Int) -> Bool {
return existsInArray(numbers[...], k)
}
正如@Leo 建议的那样,您可以将其实现为一个集合方法,而不是实现两个单独的方法。集合索引不一定是整数,但对于 a 来说RandomAccessCollection
,索引计算保证为 O(1)。您还可以将其推广到任意可比较元素的集合而不是整数。
这是一个可能的实现:
extension RandomAccessCollection where Element: Comparable {
/// Returns a Boolean value indicating whether the collection contains the
/// given element. It is assumed that the collection elements are sorted
/// in ascending (non-decreasing) order.
///
/// - Parameter element: The element to find in the collection.
/// - Returns: `true` if the element was found in the collection; otherwise,
/// `false`.
///
/// - Complexity: O(log(*n*)), where *n* is the size of the collection.
func binarySearch(for element: Element) -> Bool {
if isEmpty {
return false
}
let midIndex = index(startIndex, offsetBy: count / 2)
if element == self[midIndex] {
return true
} else if element < self[midIndex] {
return self[..<midIndex].binarySearch(for: element)
} else {
return self[index(after: midIndex)...].binarySearch(for: element)
}
}
}
用法:
let numbers = [-9, 14, 37, 102]
print(numbers.binarySearch(for: 102)) // true
print(numbers.binarySearch(for: 36)) // false
或者,一种更新搜索范围索引的非递归方法:
extension RandomAccessCollection where Element: Comparable {
func binarySearch(for element: Element) -> Bool {
var lo = startIndex
var hi = endIndex
while lo < hi {
let mid = index(lo, offsetBy: distance(from: lo, to: hi) / 2)
if element == self[mid] {
return true
} else if element < self[mid] {
hi = mid
} else {
lo = index(after: mid)
}
}
return false
}
}
推荐阅读
- python - Docker 图像未正确加载 FastText 向量
- c# - SQL Server localDB 无法创建文件
- javascript - 如何使用 HTML 使文本可拖动到视频上?
- python - tkinter:如何从树视图中删除所有条目并清除列名
- python - Pandas 从字符串中提取带小数的数字
- ruby-on-rails - 用于私人视频的 Vimeo API
- python-2.7 - FIO通过子进程运行时生成空文件
- c# - 命名管道尝试将 msg C# 服务器发送到 C++ 客户端
- r - RStudio - 能够对多个目录中的文件进行字符串替换?
- sql - 新列上的数据类型不匹配