Arrays.binarySearch 的 Scala 替代品？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4226947/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Scala replacement for Arrays.binarySearch?
提问by soc
Is there a replacement in Scala for Java's int Arrays.binarySearch(Object[] array, object)?
Scala 中有 Java 的替代品int Arrays.binarySearch(Object[] array, object)吗？
The problem is that Scala's Arrays are not covariant, so I would have to cast my stringArray: Array[String]like this first:
问题是 Scala 的数组不是协变的，所以我必须先stringArray: Array[String]像这样投射：
stringArray.asInstanceOf[Array[Object]]
Is there a better solution?
有更好的解决方案吗？
采纳答案by Rex Kerr
There isn't anything built in as far as I know, but you can use the pimp-my-library patternto accomplish this fairly easily. Like so:
据我所知，没有内置任何内容，但您可以使用pimp-my-library 模式轻松完成此操作。像这样：
class ObjectArrayTools[T <: AnyRef](a: Array[T]) {
def binarySearch(key: T) = {
java.util.Arrays.binarySearch(a.asInstanceOf[Array[AnyRef]],key)
}
}
implicit def anyrefarray_tools[T <: AnyRef](a: Array[T]) = new ObjectArrayTools(a)
scala> Array("a","fish","is","some","thing").binarySearch("some")
res26: Int = 3
scala> Array("a","fish","is","some","thing").binarySearch("bye")
res28: Int = -2
You can add the other java.util.Arraysobject methods into the same class if you need them too.
java.util.Arrays如果您也需要，您可以将其他对象方法添加到同一个类中。
In general, I find it a good idea to get used to always importing a collection of your favorite Scala utilities. It's so easy to add functionality like this that you may as well do it in general rather than keep typing .asInstanceOf[Array[AnyRef]], and with a little effort you can make yourself significantly more productive.
总的来说，我发现习惯于始终导入您最喜欢的 Scala 实用程序的集合是一个好主意。添加这样的功能非常容易，您可以在一般情况下进行，而不是继续输入.asInstanceOf[Array[AnyRef]]，并且只需稍加努力，您就可以显着提高自己的工作效率。
回答by Joe Pallas
Scala 2.11 added scala.collection.Searchingto the standard library. It uses binary search for indexed sequences and linear search otherwise.
Scala 2.11 添加scala.collection.Searching到标准库中。它对索引序列使用二进制搜索，否则使用线性搜索。
import scala.collection.Searching._
Array(1, 2, 3, 4, 5).search(3)
回答by hohonuuli
Arrays are funny beasts. If you try the code in the example provided with 'ObjectArrayTools' with this:
数组是有趣的野兽。如果您尝试使用“ObjectArrayTools”提供的示例中的代码：
Array(1, 2, 3, 4, 5).binarySearch(3)
You get
你得到
error: value binarySearch is not a member of Array[Int]
Array(1, 2, 3, 4, 5).binarySearch(3)
For what's going on with Arrays in Scala refer to this document. In any case, you could use this code instead, although it uses Seq instead of Array. However, it has the added bonus of using an Ordering (which just so happens to also be a Java Comparator. So you can customize the ordered behavior if needed.)
有关 Scala 中数组的情况，请参阅此文档。在任何情况下，您都可以改用此代码，尽管它使用 Seq 而不是 Array。但是，它具有使用 Ordering 的额外好处（恰好也是 Java Comparator。因此您可以根据需要自定义排序行为。）
import _root_.scala.collection.JavaConversions._
import java.util.{Collections, List => JList}
class SearchableSeq[T](a: Seq[T])(implicit ordering: Ordering[T]) {
val list: JList[T] = a.toList
def binarySearch(key: T): Int = Collections.binarySearch(list, key, ordering)
}
implicit def seqToSearchable[T](a: Seq[T])(implicit ordering: Ordering[T]) =
new SearchableSeq(a)(ordering)
Some examples:
一些例子：
scala> List(1, 2, 3, 4, 5).binarySearch(3)
res0: Int = 2
scala> List(1D, 2D, 3D, 4D, 5D).binarySearch(3.5)
res1: Int = -4
scala> List("a","fish","is","some","thing").binarySearch("bye")
res2: Int = -2
回答by moshe beeri
It not that hard to just write it in scala
用scala写它并不难
object BSearch {
def interative[T](array: Array[T], value: T)(implicit arithmetic: Numeric[T]): Int = {
var left: Int = 0;
var right: Int = array.length - 1;
while (right > left) {
val mid = left + (right - left) / 2
val comp = arithmetic.compare(array(mid), value)
if (comp == 0)
return mid; //negative if test < value
else if (comp > 0) //list(mid) > value
right = mid - 1;
else if (comp < 0) //list(mid) < value
left = mid + 1;
}
-1;
}
BSearch.interative(array, value)
回答by Han
Been some years since this question was raised, thought to make some comparison test, hopefully it can help some to decide:
提出这个问题已经有几年了，想做一些比较测试，希望可以帮助一些人做出决定：
import scala.collection.Searching._
import _root_.scala.collection.JavaConversions._
import java.util.{Collections, List => JList}
import scala.reflect.ClassTag
class ObjectArrayTools[T <: Int](a: Array[T]) {
def binarySearch(key: T) = {
java.util.Arrays.binarySearch(a.asInstanceOf[Array[Int]],key)
}
}
class SearchableSeq[T](a: Seq[T])(implicit ordering: Ordering[T]) {
val list: JList[T] = a.toList
def binarySearch2(key: T): Int = Collections.binarySearch(list, key, ordering)
}
object BinarySearch {
implicit def anyrefarray_tools[T <: Int](a: Array[T]) = new ObjectArrayTools(a)
implicit def seqToSearchable[T](a: Seq[T])(implicit ordering: Ordering[T]) =
new SearchableSeq(a)(ordering)
def main(args:Array[String]) {
val informationArray = Array(1,2,3,4,5,6,7,8,9,10,11,12,14,15,18,20,22,23,25,26)
val informationList = List(1,2,3,4,5,6,7,8,9,10,11,12,14,15,18,20,22,23,25,26)
//val sortedArray = sortList(informationArray)
val sortedArray = informationArray
val sortedList = informationList
for(x <- 0 to 2) {
val startTime = System.nanoTime
val result = binarySearch(sortedArray, 5)
val result2 = binarySearch(sortedArray, 19)
println(s"Custom search time elapsed: ${(System.nanoTime - startTime)}")
val startTime2 = System.nanoTime
val result3 = sortedArray.search(5)
val result4 = sortedArray.search(19)
println(s"Scala search time elapsed: ${(System.nanoTime - startTime2)}")
val startTime3 = System.nanoTime
val result5 = sortedArray.binarySearch(5)
val result6 = sortedArray.binarySearch(19)
println(s"Java search casting time elapsed: ${(System.nanoTime - startTime3)}")
val startTime4 = System.nanoTime
val result7 = sortedList.binarySearch2(5)
val result8 = sortedList.binarySearch2(19)
println(s"Java search as list time elapsed: ${(System.nanoTime - startTime4)}")
val startTime9 = System.nanoTime
val result10 = binarySearchWithImplicitConversion(sortedArray, 5)
val result11 = binarySearchWithImplicitConversion(sortedArray, 19)
println(s"Custom generic time elapsed: ${(System.nanoTime - startTime9)}")
println("---")
}
}
/*def sortList(list:Array[Int]):Array[Int] = {
import com.walcron.etc.Quicksort._
quickSort(list)
}*/
//def binarySearch[T <% Ordered[T]](list:Array[T], valueToBeSearch:T)(implicit t:ClassTag[T]):Int = {
def binarySearch(list:Array[Int], valueToBeSearch:Int):Int = {
def search(start:Int, end:Int):Int = {
val pos = ((end - start) / 2) + start
val curr = list(pos)
if(curr == valueToBeSearch) {
pos
}
else if((end - start) <= 1) {
-1 * (pos + 1) // Indicates the value should be inserted
}
else if(valueToBeSearch > curr) {
search(pos, end)
}
else {
search(start, pos)
}
}
search(0, list.length)
}
def binarySearchWithImplicitConversion[T <% Ordered[T]](list:Array[T], valueToBeSearch:T)(implicit t:ClassTag[T]):Int = {
def search(start:Int, end:Int):Int = {
val pos = ((end - start) / 2) + start
val curr = list(pos)
if(curr == valueToBeSearch) {
pos
}
else if((end - start) <= 1) {
-1 * (pos + 1) // Indicates the value should be inserted
}
else if(valueToBeSearch > curr) {
search(pos, end)
}
else {
search(start, pos)
}
}
search(0, list.length)
}
}
The returned result after 3 runs (as Scala compiler really do need some boost)
3 次运行后返回的结果（因为 Scala 编译器确实需要一些提升）
Custom search time elapsed: 873373
Scala search time elapsed: 9322723
Java search casting time elapsed: 126380
Java search as list time elapsed: 7375826
Custom generic time elapsed: 4421972
---
Custom search time elapsed: 10372
Scala search time elapsed: 34885
Java search casting time elapsed: 10861
Java search as list time elapsed: 104596
Custom generic time elapsed: 57964
---
Custom search time elapsed: 9121
Scala search time elapsed: 31667
Java search casting time elapsed: 11815
Java search as list time elapsed: 53387
Custom generic time elapsed: 60773
In general, java binary search performed way better; while scala's search did pretty bad. There was also another noticeable performance, it seems that generic typing implicitly drags the performance here badly(so maybe someone can help fix the generic type)...but indirectly it shows a big performance impact.
一般来说，java二进制搜索的表现要好得多；而 scala 的搜索做得很糟糕。还有另一个值得注意的性能，似乎泛型类型隐含地严重拖累了这里的性能（所以也许有人可以帮助修复泛型类型）......但它间接地显示了很大的性能影响。
回答by Bagguley
@moshe-beeri
@moshe-beeri
If you were going to write it in Scala, why would you write it in Java in Scala? Why not actually write it in Scala?
如果您打算用 Scala 编写它，为什么要在 Scala 中用 Java 编写它？为什么不在 Scala 中实际编写它？
def split(list:List[Char]): (List[Char], List[Char]) = {
val len = list.size
(list.slice(0, len/2), list.slice(len/2,len))
}
def search(target: Char, list: List[Char]):Boolean = {
list match {
case Nil => false
case head :: Nil => if (head == target) true else false
case _ => {
val c = split(list)
if (c._1.last >= target) search(target, c._1) else search(target, c._2)
}
}
}
