查找屏幕键盘 scala 的击键

Question

我正在尝试使用 Scala 解决最近的面试问题..

您有一个屏幕键盘，它是一个 6 行、每行 5 列的网格。从A到Z的字母和空白space首先排列在网格行中。

您可以使用此屏幕键盘输入文字。使用电视遥控器按向左、向右、向上、向下或确定键输入每个字符。

问题：给定一个输入字符串，找到需要在遥控器上按下以键入输入的击键序列。

代码实现可以在

找到

https://github.com/mradityagoyal/scala/blob/master/OnScrKb/src/main/scala/OnScrKB.scala

我尝试使用三种不同的方法来解决这个问题..

简单 forldLeft。

def keystrokesByFL(input: String, startChar: Char = 'A'): String = {
val zero = ("", startChar)
//(acc, last) + next => (acc+ aToB , next) 
def op(zero: (String, Char), next: Char): (String, Char) = zero match {
  case (acc, last) => (acc + path(last, next), next)
}
val result = input.foldLeft(zero)(op)
result._1

}

分而治之 - 使用分而治之机制。该算法类似于归并排序。 * 如果长度 > 3，我们将输入单词一分为二 * 我们递归调用子例程，从拆分中获取左右两半的路径。 * 最后.. 我们添加第一个击键 + 从第一个字符串末尾到第二个字符串开头的击键 + 第二个字符串的击键。 * 本质上，我们将输入字符串分成两个较小的一半，直到大小为 4。对于小于 4 的大小，我们使用右折叠。
```
def keystrokesByDnQ(input: String, startChar: Char = 'A'): String = {
def splitAndMerge(in: String, startChar: Char): String = {
  if (in.length() < 4) {
    //if length is <4 then dont split.. as you might end up with one side having only 1 char. 
    keystrokesByFL(in, startChar)
  } else {
    //split
    val (x, y) = in.splitAt(in.length() / 2)
    splitAndMerge(x, startChar) + splitAndMerge(y, x.last)
  }
}
splitAndMerge(input, startChar)
```
}

Fold - 使用属性底层操作是关联的（但不是可交换的）。 * 例如.. keystrokes("ABCDEFGHI", startChar = 'A') == keystrokes("ABC", startChar='A')+keystrokes("DEF", 'C') + 击键("GHI", 'F')

def keystrokesByF(input: String, startChar: Char = 'A'): String = {
  val mapped = input.map { x => PathAcc(text = "" + x, path = "") } // map each character in input to case class PathAcc("CharAsString", "")
  val z = PathAcc(text = ""+startChar, path = "") //the starting char. 

  def op(left: PathAcc, right: PathAcc): PathAcc = {
  PathAcc(text = left.text + right.text, path = left.path + path(left.text.last, right.text.head) + right.path)
  }
  val foldresult = mapped.fold(z)(op)

  foldresult.path
}

我的问题： 1. 分而治之比弃牌好吗？

折叠和分而治之比 foldLeft 更好（对于这个特定问题）
有没有一种方法可以将分而治之方法或折叠方法表示为 Monad？我可以看到结合律得到满足......但我无法弄清楚这里是否存在幺半群......如果是......它对我有什么帮助？
分而治之的方法是解决这个特定问题的最佳方法吗？
哪种方法更适合 spark？

欢迎提出任何建议..

Answer 1

我会这样做：

def keystrokes(input: String, start: Char): String =
 ((start + input) zip input).par.map((path _).tupled).fold("")(_ ++ _)

这里的重点是用par的方法将(Char, Char)的序列并行化，这样就可以并行化map，对[=14]取最优的实现=].

该算法只是简单地将String中的字符两个两个（表示要走的路径的单位），计算它们之间的路径，然后连接结果。请注意，fold("")(_ ++ _) 基本上是 mkString（尽管并行收集上的 mkString 是由 seq.mkString 实现的，因此效率要低得多）。

您的实施非常想念的是任务的并行化。即使在分而治之的方法中，您也永远不会运行并行编码，因此您将等待上半部分完成后再开始下半部分（即使它们是完全独立的）。

假设你使用并行化，fold在并行序列上的经典实现正是你描述的分而治之算法，但可能优化得更好（例如，它可能选择块大小的另一个值 3，我倾向于在这些问题上信任 scala-collection 实现者。

请注意 String 上的 fold 可能是用 foldLeft 实现的，因此与 foldLeft 相比没有任何附加值，除非你使用 .par之前。

回到您的问题（我将主要重复刚才所说的内容）：

1) 是的，在 String 上分而治之优于折叠...（但在并行化 String 上则不然）

2) Fold 只能通过某种并行化比 FoldLeft 更好，在这种情况下，它将与（或更好，如果对特定并行化集合有更好的实现）分而治之征服。

3) 我看不出单子与这里有什么关系。 fold 的运算符和零确实必须形成一个幺半群（否则，如果运算符不是关联的，你将在操作排序方面遇到一些问题，如果零不是中性元素，则会出现不需要的噪音）。

4) 是的，据我所知，一旦并行化

5) Spark 本质上是并行的，因此主要问题是最终将所有部分重新组合在一起。我的意思是 RDD 未排序，因此您需要保留一些信息，以了解应将哪条输入放在集群中的哪个位置。一旦你正确地做到了这一点（使用分区等，这本身可能就是一个完整的问题），使用 map 和 fold 仍然可以作为一种魅力（Spark 被设计为具有 API 尽可能接近 scala-collection，所以这里真的很好）。

查找屏幕键盘 scala 的击键

find keystrokes for On Screen Keyboard scala

algorithm

mergesort

scala

fold

foldleft