Effiziente Weise zu prüfen, ob ein Traversable mehr als 1 Element in Scala hat

Question

Ich muss überprüfen, ob ein Traversable (von dem ich bereits weiß nonEmpty) ein einzelnes Element oder mehr hat.

Ich könnte size verwenden, aber (sag mir, wenn ich falsch liege) Ich vermute, dass dies O (n) sein könnte, und durchqueren die Sammlung, um es zu berechnen.

könnte ich, wenn tail.nonEmpty überprüfen, oder wenn .head != .last

Welche Vor- und Nachteile der beiden Ansätze sind? Gibt es einen besseren Weg? (Zum Beispiel wird .last eine vollständige Iteration auch tun?)

Answer 1

Alle Ansätze, die Elemente von Anfang der Sammlung schneiden und Schwanz zurückkehren sind ineffizient. Zum Beispiel ist tail für List O (1), während tail für Array O (N) ist. Gleiches mit drop.

Ich schlage vor, mit take:

list.take(2).size == 1 // list is singleton 

take deklariert ganze Sammlung zurück, wenn Sammlung Länge weniger ist, dass take das Argument. Daher wird kein Fehler auftreten, wenn die Sammlung leer ist oder nur ein Element enthält. Auf der anderen Seite, wenn die Sammlung ist riesig take wird in O (1) Zeit trotzdem laufen. Intern take wird mit dem Iterieren Ihrer Sammlung beginnen, zwei Schritte ausführen und brechen, um Elemente in die neue Sammlung zurückzugeben.

UPD: I Zustand geändert genau die

Answer 2

Nicht alle werden gleich sein, aber nehmen wir ein Worst-Case-Szenario, wo es eine List ist. last wird die gesamte List nur für den Zugriff auf dieses Element, wie auch size verbrauchen.

tail.nonEmpty wird von einer head :: tail Musterübereinstimmung erhalten, die nicht die gesamte List verbrauchen muss. Wenn Sie bereits wissen, dass die Liste nicht leer ist, sollte dies die offensichtliche Wahl sein.

Aber nicht alle tail Operationen nehmen konstante Zeit wie ein List: Scala Collections Performance

Answer 3

Was Pattern-Matching Frage überein?

itrbl match { case _::Nil => "one"; case _=>"more" } 

Answer 4

Sie können eine Traversable anzeigen. Sie können die TraversableView träge schneiden.

Der erste Stern ist, weil die REPL einige Ausgaben ausgibt.

scala> val t: Traversable[Int] = Stream continually { println("*"); 42 } 
* 
t: Traversable[Int] = Stream(42, ?) 

scala> t.view.slice(0,2).size 
* 
res1: Int = 2 

scala> val t: Traversable[Int] = Stream.fill(1) { println("*"); 42 } 
* 
t: Traversable[Int] = Stream(42, ?) 

scala> t.view.slice(0,2).size 
res2: Int = 1 

Der Vorteil ist, dass es keine Zwischensammlung gibt.

scala> val t: Traversable[_] = Map((1 to 10) map ((_, "x")): _*) 
t: Traversable[_] = Map(5 -> x, 10 -> x, 1 -> x, 6 -> x, 9 -> x, 2 -> x, 7 -> x, 3 -> x, 8 -> x, 4 -> x) 

scala> t.take(2) 
res3: Traversable[Any] = Map(5 -> x, 10 -> x) 

, dass ein nicht optimiert Map gibt, zum Beispiel:

scala> res3.getClass 
res4: Class[_ <: Traversable[Any]] = class scala.collection.immutable.HashMap$HashTrieMap 

scala> Map(1->"x",2->"x").getClass 
res5: Class[_ <: scala.collection.immutable.Map[Int,String]] = class scala.collection.immutable.Map$Map2