打开弦乐

Question

我很好奇 Java 和 Scala 如何实现字符串开关：

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

似乎 Java 打开哈希码然后进行单个字符串比较：

 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

相比之下，Scala 似乎可以与所有情况进行比较：

 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

是否有可能说服 Scala 使用哈希码技巧？我宁愿选择 O(1) 解决方案而不是 O(n) 解决方案。在我的真实代码中，我需要与 33 个可能的关键字进行比较。

Answer 1

我认为问题在于您是从 Java 的角度考虑 Scala（我认为您也在过早地优化，但是嘿）。

我认为您想要的解决方案是记住您的映射。您有一个映射自 String -> Int 的函数，对吧？所以这样做：

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

(此记忆代码取自here.

然后你可以这样记忆你的代码：

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

多田！现在你正在做哈希值比较。尽管我要补充一点，大多数记忆示例（包括这个）都是玩具，在大多数用例中都无法生存。真实世界 memoization should include an upper limit 到您愿意缓存的数量，并且在您的代码中，您的代码中可能的有效案例数量很少，而无效案例数量巨大，我会考虑制作一个通用的 class 预构建地图并有一个专门的查找 "in my cache, you win, not in my cache, default." 可以很容易地通过调整 memoizer 将 List 输入预缓存并更改 "not-in-cache" 代码为 return 默认值。

Answer 2

显然，这种情况似乎是 Scala 编译器缺乏优化。当然，match 构造比 Java 中的 switch/case 强大得多（多得多），并且优化它要困难得多，但它可以检测到这些特殊情况简单的哈希比较将适用。

另外，我不认为这种情况会在惯用的 Scala 中出现很多次，因为你总是与 case 类匹配，除了具有不同的值之外还有一些意义。

Answer 3

这个问题激发了我学习Scala宏的灵感，不妨分享一下我的解决方法。

下面是我使用宏的方法：

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

关联值自动统计。如果这不是您想要的，您可以更改实现以接受 ArrowAssocs，但这对我来说太复杂了。

下面是宏的实现方式：

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

请注意，此解决方案不处理哈希冲突。由于我在实际问题中关心的特定字符串不会发生冲突，所以我还没有穿过那个特定的桥。

打开弦乐

Switching on Strings

java

string

scala

hashcode

switch-statement