我是一个老C程序员。我正在尝试用Swift实现一些代码,并且需要一个二进制搜索算法,如果没有完全匹配,它将返回最接近的元素。
我搜索了一下,要么代码一次调用了太多Swift概念,以至于对我的C眼睛来说是不透明的,要么它不适合我的用例。
我决定移植一些旧的C代码来完成工作,并编写了以下内容:
public func bsearch(arr:[Any], target:Double, bcompare:(Any,Double)->Int)-> Int{
// v is array being searched
// target is what we're looking for
// bcompare is a pointer to user-supplied comparison function
// bcompare returns -1 if left element < right element, 0 if =, 1 if >
// target must be same type as v element being compared
// returns index of array element that is closest to <= target
// note! indexed returned may not match target value
var lo, hi, mid:Int
hi = v.count-1
if hi <= 0 {return -1}
lo = 0
while ((hi-lo) > 1) {
mid = (hi+lo)/2
if( bcompare(v[mid], target) == -1){
lo = mid + 1
}
else{
hi = mid
}
}
if bcompare(v[hi],target) == 0{
return hi
}
return lo
}
func eleCompare(left:locArrayele,right:Double)->Int{
if right < left.degrees{
return -1
}
else if right == left.degrees{
return 0
}
else {
return 1
}
}
在C中,您可以将搜索函数指针传递给结构,并告诉编译器如何解释您也传递给搜索函数的比较函数中的内存块。比较函数引用只是另一个内存指针,不需要参数。
我假设Swift“任何”声明相当于指针引用,并在编写上述代码时考虑到了这一想法。编译器抱怨当比较函数将目标称为双精度时将搜索目标声明为任何。为了满足编译器,我将目标声明为双精度,代码编译良好。
我现在的问题是实际测试代码。无论我如何尝试调用搜索函数,编译器都不满意。这个测试片段是我能让编译器满意的最接近的。
class locArrayele{
public var degrees = CLLocationDegrees()
public var ix = Int()
init( degrees:CLLocationDegrees, i:Int){
self.degrees = degrees
self.ix = i
}
}
public var latArray : [locArrayele] = []
.
.
.
ix = bsearch(v: latArray, target:35.0, bcompare: eleCompare )
print(" when lat is 35, closest ix is \(ix))
显然,编译器希望我向eleCompare提供参数,这是我希望bsearch在执行时执行的任务。
我如何调用代码?我意识到我在使用Swift,但我只是想让一些东西工作。优雅可以在我对语言感到舒适的时候出现。
您需要使您的bsearch()
通用。您有两种类型可以改变:第一种类型是数组v
包含的类型,另一种是目标的类型。
将您的第一行更改为:
public func bsearch<T, U>(v: [T], target: U, bcompare: (T, U) -> Int) -> Int {
调用时不必使用2种不同的类型,但可以。
此示例有一个[String]
类型的单词数组,它正在搜索具有5个字母的单词,因此Int
中的目标。
let words = ["a", "to", "the", "seven", "butter"]
func compareNameLength(left: String, right: Int) -> Int {
if left.count < right {
return -1
} else if left.count == right {
return 0
} else {
return 1
}
}
// search for the 5 letter word
let i = bsearch(v: words, target: 5, bcompare: compareNameLength)
print(words[i])
seven
此示例有一个包含素数的[Int]
,它正在搜索最接近数字的素数而不进行遍历,因此目标是Int
。
let primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
func compareInt(left: Int, right: Int) -> Int {
if left < right {
return -1
} else if left == right {
return 0
} else {
return 1
}
}
// search for closest prime to 8
let p = bsearch(v: primes, target: 8, bcompare: compareInt)
print(primes[p])
7