einschalten Strings

Question

Ich war gespannt, wie Java und Scala Schalter auf Strings implementieren:

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

Es scheint, wie Java-Schalter auf der Hash-Code und führt dann einen einzelnen String-Vergleich:

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  

Im Gegensatz dazu scheint Scala gegen alle Fälle zu vergleichen:

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  

Kann man Scala davon überzeugen, den Hashcode-Trick anzuwenden? Ich würde lieber eine O (1) Lösung zu einer O (n) Lösung bevorzugen. In meinem echten Code muss ich mit 33 möglichen Keywords vergleichen.

Answer 1

Definitiv scheint es, dass dieser Fall ein Mangel an Optimierung vom Scala Compiler ist. Sicher, das match Konstrukt ist viel (viel viel) leistungsfähiger als der Schalter/Fall in Java, und es ist viel schwieriger, es zu optimieren, aber es könnte diese speziellen Fälle erkennen, in denen ein einfacher Hash-Vergleich gelten würde.

Ich denke auch nicht, dass dieser Fall viele Male im idiomatischen Scala angezeigt wird, weil Sie immer mit Fallklassen zusammenpassen, die eine Bedeutung haben, abgesehen davon, dass sie unterschiedliche Werte haben.

Answer 2

Ich denke das Problem ist, dass Sie über Scala von einem Java-Gesichtspunkt denken (ich denke, dass Sie auch vorzeitig optimieren, aber hey).

Ich würde denken, dass die Lösung, die Sie wollen, ist stattdessen Ihre Zuordnung memoize. Sie haben eine Funktion, die von String -> Int abbildet, oder? So tun:

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

(diese memoizing Code aus here genommen wird

Dann können Sie Ihren Code wie folgt memoize:.!

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 Jetzt sind Sie tun Hash-Wert-Vergleiche Obwohl ich hinzufügen werde, dass die meisten Memoization Beispiele (diese enthalten) sind Spielzeuge und werden die meisten Anwendungsfälle nicht überleben.Echte memoization should include an upper limit auf die Menge, die Sie bereit sind zu cachen, und im Falle Ihres Codes, wo Sie eine winzige haben Anzahl der möglichen gültigen Fälle und eine große Anzahl von ungültigen Fällen würde ich überlegen, eine allgemeine Klasse zu erstellen, die die Map vorab erstellt und eine spezialisierte Suche hat, die besagt: "in meinem Cache, gewinnst du, nicht in meinem Cache, Standard." was sehr gut gemacht werden kann leicht durch das Anpassen des Memoizers, um eine List der Eingabe zum precache zu nehmen und den "nicht-im-cache" Code zu ändern, um einen Standard zurückzugeben.

Answer 3

Dieses Problem inspirierte mich, über Scala Makros zu lernen, und ich könnte meine Lösung auch teilen.

Hier ist, wie ich das Makro zu verwenden:

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

Die zugehörigen Werte werden automatisch hochgezählt. Wenn dies nicht das ist, was Sie wollen, können Sie die Implementierung ändern, um stattdessen ArrowAssoc s zu akzeptieren, aber das war viel zu kompliziert für mich.

Und hier ist, wie das Makro implementiert:

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

Beachten Sie, dass diese Lösung nicht Hash-Kollisionen umgehen kann. Da die speziellen Saiten, die mir in meinem eigentlichen Problem wichtig sind, nicht kollidieren, habe ich diese bestimmte Brücke noch nicht überquert.