Switching trên Strings

Question

Tôi đã tò mò muốn xem như thế nào Java và Scala thực hiện công tắc trên dây:

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

Nó có vẻ như Java chuyển mạch trên hashcode và sau đó thực hiện một chuỗi so sánh duy nhất:

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  

Ngược lại, Scala có vẻ so sánh với tất cả các trường hợp:

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  

Có thể thuyết phục Scala sử dụng mẹo băm không? Tôi thà thích một giải pháp O (1) cho một giải pháp O (n). Trong mã thực sự của tôi, tôi cần so sánh với 33 từ khóa có thể.

Answer 1

Chắc chắn có vẻ như trường hợp này là thiếu tối ưu hóa từ trình biên dịch Scala. Chắc chắn, cấu trúc match là nhiều (nhiều) mạnh mẽ hơn chuyển đổi/trường hợp trong Java, và nó khó hơn nhiều để tối ưu hóa nó, nhưng nó có thể phát hiện các trường hợp đặc biệt này trong đó một phép so sánh băm đơn giản sẽ được áp dụng.

Ngoài ra, tôi không nghĩ trường hợp này sẽ hiển thị nhiều lần trong Scala thành ngữ, bởi vì bạn luôn phù hợp với các trường hợp có ý nghĩa ngoài việc có giá trị khác nhau.

Answer 2

Tôi nghĩ rằng vấn đề là bạn đang suy nghĩ về Scala từ một quan điểm Java (tôi nghĩ bạn cũng đang tối ưu hóa sớm, nhưng hey).

Tôi nghĩ rằng giải pháp bạn muốn thay vào đó là ghi nhớ bản đồ của bạn. Bạn có một chức năng ánh xạ từ String -> Int, phải không? Vì vậy, làm như sau:

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

(đang memoizing này được lấy từ here

Sau đó, bạn có thể memoize mã của bạn như thế này:.!

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 Bây giờ bạn đang làm so sánh giá trị hash Mặc dù tôi sẽ thêm rằng hầu hết các ví dụ ghi nhớ (ví dụ này bao gồm) là đồ chơi và sẽ không tồn tại trong hầu hết các trường hợp sử dụng.Thế giới thực memoization should include an upper limit với số tiền bạn sẵn sàng lưu vào bộ nhớ cache và trong trường hợp mã của bạn số lượng các trường hợp hợp lệ có thể và một số lượng lớn các trường hợp không hợp lệ, tôi sẽ cân nhắc tạo một lớp chung để tạo bản đồ trước và có tra cứu chuyên ngành cho biết "trong bộ nhớ cache của tôi, bạn giành được, không có trong bộ nhớ cache của tôi". dễ dàng bằng cách tinh chỉnh trình ghi nhớ để lấy một số List của đầu vào để đặt trước và thay đổi mã "không phải trong bộ nhớ cache" để trả về mặc định.

Answer 3

Sự cố này đã truyền cảm hứng cho tôi để tìm hiểu về các macro Scala và tôi cũng có thể chia sẻ giải pháp của mình.

Sau đây là cách tôi sử dụng macro:

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

Các giá trị có liên quan được tính tự động. Nếu đây không phải là những gì bạn muốn, bạn có thể thay đổi việc triển khai để chấp nhận ArrowAssoc s thay vào đó, nhưng điều này quá phức tạp đối với tôi.

Và đây là cách vĩ mô được thực hiện:

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

Lưu ý rằng giải pháp này không xử lý va chạm băm. Vì các chuỗi cụ thể mà tôi quan tâm trong vấn đề thực tế của tôi không va chạm, tôi đã không vượt qua cây cầu cụ thể đó.