Modo efficiente per verificare se un traversable ha più di 1 elemento in Scala

Question

Ho bisogno di verificare se un Traversable (che so già essere nonEmpty) ha un singolo elemento o più.

Potrei usare size, ma (dimmi se ho torto) sospetto che questo potrebbe essere O (n), e attraversare la raccolta per calcolarlo.

ho potuto verificare se tail.nonEmpty, o se .head != .last

Quali sono i pro ei contro dei due approcci? C'è un modo migliore? (ad esempio, lo sarà anche il .last?)

Answer 1

Tutti gli approcci che tagliano gli elementi dall'inizio della raccolta e della coda di ritorno sono inefficienti. Ad esempio tail per List è O (1), mentre tail per Array è O (N). Lo stesso con drop.

propongo utilizzando take:

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

take è dichiarato di restituire tutta la collezione, se la lunghezza collezione è meno che l'argomento take s'. Quindi non ci saranno errori se la raccolta è vuota o ha un solo elemento. D'altra parte se la raccolta è enorme, take verrà eseguito comunque in tempo O (1). Internamente take inizierà a ripetere la tua collezione, fare due passi e interrompere, mettendo gli elementi nella nuova collezione da restituire.

UPD: ho cambiato condizione che corrisponda esattamente alla domanda

Answer 2

Non tutto sarà uguale, ma prendiamo lo scenario peggiore in cui si tratta di un List. last consumerà l'intero List solo per accedere a quell'elemento, così come lo sarà size.

tail.nonEmpty è ottenuto da un modello head :: tail corrispondenza, che non ha bisogno di consumare l'intero List. Se sai già che l'elenco non è vuoto, questa dovrebbe essere la scelta più ovvia.

Ma non tutti i tail operazioni richiedono tempo costante come un List: Scala Collections Performance

Answer 3

Che dire di pattern matching?

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

Answer 4

È possibile visualizzare un attraversabile. È possibile affettare pigramente lo TraversableView.

La stella iniziale è perché il REPL stampa un po 'di output.

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 

Il vantaggio è che non esiste una raccolta intermedia.

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) 

che restituisce un non ottimizzata Map, per esempio:

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