0

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

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

您可以在屏幕键盘上使用它来输入单词。通过按向左、向右、向上、向下或 OK 键使用您的电视遥控器来输入每个字符。

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

代码实现可以在

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

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

  1. 简单的 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

    }

  2. 分而治之 - 使用分而治之的机制。该算法类似于归并排序。* 如果长度> 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)

    }

  3. 折叠 - 使用底层操作是关联的（但不是可交换的）的属性。* 例如.. keystrokes("ABCDEFGHI", startChar = 'A') == keystrokes("ABC", startChar='A')+keystrokes("DEF", 'C') + keystrokes("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. 分而治之的方法比折叠更好吗？

  1. 折叠和分而治之比 foldLeft 更好（针对这个特定问题）

  2. 有没有办法可以将分而治之的方法或折叠方法表示为 Monad？我可以看到结合律得到满足……但我无法弄清楚这里是否存在幺半群……如果是的话……它对我有什么好处？

  3. 分而治之的方法是解决这个特定问题的最佳方法吗？

  4. 哪种方法更适合火花？

欢迎任何建议..

4

1 回答 1

0

这是我的做法：

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

这里的重点是使用par方法对 的序列进行并行化(Char, Char)，使其能够并行化map，并对 进行最优实现fold。

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

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

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

请注意，foldonString可能是使用 实现的，因此除非您以前使用过，否则foldLeft没有比您使用的附加值。foldLeft.par

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

1）是的，分而治之比折叠好... on String（但不是并行化String）

2) Fold 只能在某种并行化下比 FoldLeft 好，在这种情况下，它将与分治法一样好（或优于，如果对特定的并行化集合有更好的实现）。

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

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

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

于 2017-05-11T18:49:28.773 回答