Accensione Strings

Question

ero curioso di vedere come Java e Scala implementano gli interruttori sulle stringhe:

class Java 
{ 
    public static int java(String s) 
    { 
     switch (s) 
     { 
     case "foo": return 1; 
     case "bar": return 2; 
     case "baz": return 3; 
     default: return 42; 
     } 
    } 
} 

object Scala { 
    def scala(s: String): Int = { 
    s match { 
     case "foo" => 1 
     case "bar" => 2 
     case "baz" => 3 
     case _ => 42 
    } 
    } 
} 

Sembra Java accende il codice hash e poi fa un singolo confronto di stringhe:

0: aload_0  
1: dup   
2: astore_1  
3: invokevirtual #16 // Method java/lang/String.hashCode:()I 
6: lookupswitch { // 3 
      97299: 40 
      97307: 52 
      101574: 64 
     default: 82 
    } 
40: aload_1  
41: ldc   #22 // String bar 
43: invokevirtual #24 // Method java/lang/String.equals:(Ljava/lang/Object;)Z 
46: ifne   78 
49: goto   82 
52: aload_1  
53: ldc   #28 // String baz 
55: invokevirtual #24 // Method java/lang/String.equals:(Ljava/lang/Object;)Z 
58: ifne   80 
61: goto   82 
64: aload_1  
65: ldc   #30 // String foo 
67: invokevirtual #24 // Method java/lang/String.equals:(Ljava/lang/Object;)Z 
70: ifne   76 
73: goto   82 
76: iconst_1  
77: ireturn  
78: iconst_2  
79: ireturn  
80: iconst_3  
81: ireturn  
82: bipush  42 
84: ireturn  

al contrario, Scala sembra confrontare con tutti i casi:

0: aload_1  
1: astore_2  
2: ldc   #16 // String foo 
4: aload_2  
5: invokevirtual #20 // Method java/lang/Object.equals:(Ljava/lang/Object;)Z 
8: ifeq   16 
11: iconst_1  
12: istore_3  
13: goto   47 
16: ldc   #22 // String bar 
18: aload_2  
19: invokevirtual #20 // Method java/lang/Object.equals:(Ljava/lang/Object;)Z 
22: ifeq   30 
25: iconst_2  
26: istore_3  
27: goto   47 
30: ldc   #24 // String baz 
32: aload_2  
33: invokevirtual #20 // Method java/lang/Object.equals:(Ljava/lang/Object;)Z 
36: ifeq   44 
39: iconst_3  
40: istore_3  
41: goto   47 
44: bipush  42 
46: istore_3  
47: iload_3  
48: ireturn  

È possibile convincere Scala a utilizzare il trucco hashcode? Preferirei preferire una soluzione O (1) a una soluzione O (n). Nel mio codice reale, ho bisogno di confrontarmi con 33 possibili parole chiave.

Answer 1

Sicuramente sembra che questo caso sia una mancanza di ottimizzazione dal compilatore Scala. Certo, il costrutto match è molto (molto) potente rispetto allo switch/caso in Java, ed è molto più difficile ottimizzarlo, ma potrebbe rilevare questi casi speciali in cui si applicherebbe un semplice confronto di hash.

Inoltre, non penso che questo caso mostrerà molte volte in Scala idiomatica, perché si combina sempre con classi di casi che hanno un significato oltre ad avere un valore diverso.

Answer 2

Penso che il problema sia che stai pensando a Scala da un punto di vista Java (penso che tu stia anche ottimizzando prematuramente, ma hey).

Penso che la soluzione che si desidera sia quella di memorizzare la mappatura. Hai una funzione che esegue il mapping da String -> Int, giusto? Fate così:

class Memoize1[-T, +R](f: T => R) extends (T => R) { 
    import scala.collection.mutable 
    private[this] val vals = mutable.Map.empty[T, R] 

    def apply(x: T): R = { 
    if (vals.contains(x)) { 
     vals(x) 
    } 
    else { 
     val y = f(x) 
     vals += ((x, y)) 
     y 
    } 
    } 
} 

object Memoize1 { 
    def apply[T, R](f: T => R) = new Memoize1(f) 
} 

(questo codice memoizing è tratto da here

Poi si può Memoize il codice in questo modo:.!

object Scala { 
    def scala(s: String): Int = { 
    s match { 
     case "foo" => 1 
     case "bar" => 2 
     case "baz" => 3 
     case _ => 42 
    } 
    } 

    val memoed = Memoize1(Scala.scala) 

    val n = memoed("foo") 
} 

Tada Ora si sta facendo hash value confronti Sebbene aggiungo che molti esempi di memoizzazione (incluso questo) sono giocattoli e non sopravvivono alla maggior parte dei casi d'uso: Real-world memoization should include an upper limit alla quantità che si desidera memorizzare nella cache e nel caso del codice in cui si ha un piccolo numero di possibili casi validi e un numero enorme di casi non validi, prenderei in considerazione la creazione di una classe generale che precompila la mappa e ha una ricerca specializzata che dice "nella mia cache, vinci, non nella mia cache, predefinita". Che può essere fatto molto facilmente modificando il memoizer per prendere un List di input su precache e modificare il codice "not-in-cache" per restituire un valore predefinito.

Answer 3

Questo problema mi ha ispirato a conoscere le macro di Scala e potrei anche condividere la mia soluzione.

Ecco come io uso la macro:

switch(s, 42, "foo", "bar", "baz") 

i valori associati vengono contati automaticamente. Se questo non è ciò che desideri, puoi cambiare l'implementazione per accettare invece ArrowAssoc s, ma per me è stato troppo complicato.

Ed ecco come la macro viene implementato:

import scala.language.experimental.macros 
import scala.reflect.macros.blackbox.Context 
import scala.collection.mutable.ListBuffer 

object StringSwitch { 

    def switch(value: String, default: Long, cases: String*): Long = 
    macro switchImpl 

    def switchImpl(c: Context)(value: c.Expr[String], default: c.Expr[Long], 
          cases: c.Expr[String]*): c.Expr[Long] = { 
    import c.universe._ 

    val buf = new ListBuffer[CaseDef] 
    var i = 0 
    for (x <- cases) { 
     x match { 
     case Expr(Literal(Constant(y))) => 
      i += 1 
      buf += cq"${y.hashCode} => if ($x.equals($value)) $i else $default" 

     case _ => throw new AssertionError("string literal expected") 
     } 
    } 
    buf += cq"_ => $default" 

    c.Expr(Match(q"$value.hashCode", buf.toList)) 
    } 
} 

Si noti che questa soluzione non gestisce le collisioni hash. Dal momento che le stringhe particolari a cui tengo nel mio vero problema non si scontrano, non ho ancora attraversato quel particolare ponte.