Scala Ersatz für Arrays.binarysearch-Methode?

Gibt es einen Ersatz in der Scala für die Java int Arrays.binarySearch(Object[] array, object)?

Das problem ist, dass Scala-Arrays sind keine kovariante, also müsste ich ließ meine stringArray: Array[String] wie das erste:

stringArray.asInstanceOf[Array[Object]]

Gibt es eine bessere Lösung?

InformationsquelleAutor soc | 2010-11-19

18

Gibt es noch nichts gebaut, soweit ich weiß, aber Sie können die pimp-my-library-pattern dies zu erreichen, relativ leicht. Etwa so:
```
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
```
Können Sie die anderen java.util.Arrays Objekt-Methoden in der gleichen Klasse, wenn Sie brauchen Sie auch.

Im Allgemeinen finde ich es eine gute Idee, um früher immer beim importieren einer Sammlung Ihrer Lieblings-Scala-Dienstprogramme. Es ist so leicht, die Funktionalität hinzufügen, wie diese, können Sie auch tun es in der Regel eher halten als Eingabe .asInstanceOf[Array[AnyRef]], und mit ein wenig Mühe können Sie es sich deutlich produktiver.
- Was def indexOf (elem: A, from: Int) : Int sollte dies nicht benehmen wie die binarysearch-Methode (obwohl vielleicht langsamer?)
- Nicht mit, der Signatur, als binarySearch hängt davon ab, Schlüssel Comparable. Wenn ich mich Recht erinnere, Java gerade CASTET und gibt einen Laufzeit-Fehler, das ist nicht die Art von Sache, die wir wollen, aus der Scala. Außerdem funktioniert es nur auf Sammlungen, die sind bestellt, die, wieder, kann nicht statisch durchgesetzt, im moment, ohne eine explosion in der Anzahl der Klassen (es wurden Ideen).
- Wenn binarySearch hängt davon ab, die Elemente Comparable, sollten wir nicht fügen Sie eine Einschränkung wie T <: Comparable[T]?
InformationsquelleAutor Rex Kerr
42

Scala 2.11 Hinzugefügt scala.Sammlung.Suchen der standard-Bibliothek. Es nutzt binäre Suche für indizierte Sequenzen und lineare Suche sonst.
```
import scala.collection.Searching._
Array(1, 2, 3, 4, 5).search(3)
```
- Wie kann ich die search-Methode, die mein array ist sortiert und es können binäre Suche?
- Ihre Sammlung muss sortiert werden, verwenden search. Das ist, wenn man sich auf search auf eine Sequenz, die nicht sortiert ist, sind die Ergebnisse undefiniert.
- danke für die Erklärung, aber die scheint es verwendet die Methode der linearen Suche auf mein array vom Typ Array[String] es ist Größenordnungen langsamer als java.util.Arrays.binarysearch-Methode()
- Ich habe nicht getestet, der Umsetzung, aber ich wäre sehr überrascht, wenn es nicht funktioniert wie beworben. Möchten Sie vielleicht post eine neue Frage mit details von dem, was Sie getestet haben und die Ergebnisse, die Sie gesehen haben.
- Scheint ein bug in der scala 2.11 das war die version, die ich hatte, issues.scala-lang.org/browse/SI-9605
- Beachten Sie, dass das Verhalten unterscheidet sich vom Java - Collections.binarySearch (oder Arrays.binarySearch), wenn das element ist nicht vorhanden in der Sammlung. Java gibt -1 -insertionPoint, während Scala gibt eine index - > 0. So, auf der Suche nach 3 im [1, 2, 4, 5] zurückkehren würde -3 in Java und 2 im Scala. Ich persönlich bevorzuge die Java-return Wert, da ich unterscheiden kann zwischen dem element vorhanden vs nicht vorhanden in der Liste.
- Sie können leicht unterscheiden, diese Fälle mit der Scala-Suche-API, weil die SearchResult zurückgegeben wird, ist entweder ein Found oder eine InsertionPoint. Verwenden Sie eine match zu sagen, welcher Fall es ist, und das in beiden Fällen wird explizit für jeden zu Lesen den code.
- Du hast Recht, obwohl die explizite Rückgabe eines Either Typ wäre besser gewesen, IMO. Es ist auch nicht dokumentiert, was einem zurückgegeben wird, wenn es eine übereinstimmung gibt unter Duplikate. Nach einem Blick auf den source-code, es scheint willkürlich.
InformationsquelleAutor Joe Pallas
4

Arrays sind lustige Tiere. Wenn Sie versuchen, den code in dem Beispiel mit 'ObjectArrayTools' mit diesem:
```
Array(1, 2, 3, 4, 5).binarySearch(3)
```
Erhalten Sie
```
error: value binarySearch is not a member of Array[Int]
          Array(1, 2, 3, 4, 5).binarySearch(3)
```
Was ist Los mit Arrays in Scala finden Sie dieses Dokument. In jedem Fall können Sie diesen code verwenden, statt, obwohl es nutzt Seq anstelle von Array. Aber es hat den zusätzlichen bonus von mit einer Bestellung (das passiert einfach so, um auch ein Java-Komparator. So können Sie die bestellten Verhalten, wenn nötig.)
```
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)
```
Einige Beispiele:
```
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
```
- Zugriff auf die java-Liste, die durch den index kann sehr ineffizient sein
- Das hängt davon ab, was die Rückendeckung einer Liste. Zum Beispiel eine ArrayList wird unterstützt durch ein Array ist; Sie beide eine ähnliche Leistung in Bezug auf die immer ein element von index.
- Leider ist diese Lösung suboptimal. Collections.binarySearch überprüft, ob die zur Verfügung gestellten Liste implementiert RandomAccess-Schnittstelle ("Wenn die angegebene Liste nicht implementiert das interface RandomAccess und ist groß, diese Methode wird eine iterator-basierte binäre Suche ausführt, die O(n) link traversalen und O(log n) element-Vergleiche."). Keiner der Listen, die zur Verfügung gestellt von JavaConverters die diese Schnittstelle implementiert. (docs.oracle.com/javase/7/docs/api/java/util/...)
- Guten Fang. Ich hatte nicht realisiert, dass. Es sieht aus wie scala Hinzugefügt scala.collection.Searching im 2.11. Also anstatt die Sie verwenden könnten: import scala.collection.Searching._; Array(1, 2, 3, 4, 5).search(3)
InformationsquelleAutor hohonuuli

Es nicht schwer, nur schreiben Sie es in 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)

InformationsquelleAutor moshe beeri

Schon einige Jahre her, seit diese Frage stellte, dachte machen Sie einige Vergleich test, ich hoffe, es kann einigen helfen sich zu entscheiden:

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

Dem Ergebnis nach 3 Läufen (als Scala-compiler wirklich brauchen einige 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

Im Allgemeine java-binäre Suche durchgeführt, so besser; während scala Suche habe ziemlich schlecht. Es war auch noch eine spürbare performance, es scheint, dass generische Typisierung implizit zieht die Leistung hier schlecht(vielleicht kann jemand helfen, fix der generische Typ)...aber, indirekt zeigt es eine große Auswirkung auf die Leistung.

InformationsquelleAutor Han

-2

@moshe-beeri

Wenn Sie im Begriff waren, es zu schreiben, in der Scala, warum würden Sie schreiben es in Java in Scala? Warum eigentlich nicht schreiben Sie es in Scala aus?

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

InformationsquelleAutor Bagguley

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.