Замена Scala для Arrays.binarySearch?

Question

Есть ли в Scala замена для Java int Arrays.binarySearch(Object[] array, object)?

Проблема в том, что массивы Scala не являются ковариантными, поэтому мне придется сначала разыграть stringArray: Array[String] следующим образом:

stringArray.asInstanceOf[Array[Object]]

Есть ли лучшее решение?

Answer 1

Scala 2.11 добавлено scala.collection.Searching в стандартную библиотеку. В противном случае используется двоичный поиск по индексированным последовательностям и линейный поиск.

import scala.collection.Searching._
Array(1, 2, 3, 4, 5).search(3)

Answer 2

Насколько я знаю, нет ничего встроенного, но вы можете использовать шаблон 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

Вы можете добавить другие java.util.Arrays методы объекта в тот же класс, если они вам тоже нужны.

В целом, я считаю хорошей идеей привыкнуть всегда импортировать коллекцию ваших любимых утилит Scala. Добавить такую ​​функциональность настолько просто, что вы можете делать это в целом, а не продолжать вводить .asInstanceOf[Array[AnyRef]], и, приложив немного усилий, вы сможете значительно повысить свою продуктивность.

Answer 3

Массивы - это забавные звери.Если вы попробуете код в примере с ObjectArrayTools следующим образом:

Array(1, 2, 3, 4, 5).binarySearch(3)

Вы получите

error: value binarySearch is not a member of Array[Int]
          Array(1, 2, 3, 4, 5).binarySearch(3)

Что происходит с массивами в Scala, см. thisдокумент .В любом случае, вы можете использовать этот код вместо этого, хотя он использует Seq вместо Array.Тем не менее, он обладает дополнительным бонусом использования упорядочения (которое также является 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)

Некоторые примеры:

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

Answer 4

Прошло несколько лет с тех пор, как этот вопрос был поднят, предполагалось провести некоторый сравнительный тест, надеюсь, он поможет некоторым решить:

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)
  }
}

Возвращенный результат после 3 запусков (поскольку компилятору Scala действительно нужны некоторыеboost)

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

В общем, бинарный поиск Java работал лучше;в то время как поиски скалы были довольно плохими.Была также другая заметная производительность: кажется, что универсальная типизация неявно перетаскивает производительность здесь (так что, возможно, кто-то может помочь исправить универсальный тип) ... но косвенно это оказывает большое влияние на производительность.

Answer 5

@ moshe-beeri

Если вы собирались написать это на Scala, зачем писать на Java на Scala?Почему бы не написать это в 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)
        }
    }
}

Answer 6

Это не так сложно просто написать это в 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)