Скала вдохновителя решатель, который является самым скала-иш


Я пытаюсь выразить классической ТДД ката вдохновителя в наиболее идиоматические Скала я. Вот scalatest, тестов :

package eu.byjean.mastermind

import org.junit.runner.RunWith
import org.scalatest.junit.JUnitRunner
import org.scalatest.FlatSpec
import org.scalatest.matchers.ShouldMatchers

@RunWith(classOf[JUnitRunner])
class MastermindSpec extends FlatSpec with ShouldMatchers {
  behavior of "Mastermid"

  it should "find no good and no misplaced for a wrong guess" in {
    Mastermind.check (guess='red)(secret='blue) should equal (0,0)
  }

  it should "find all good if guess equals secret of one" in {
    Mastermind.check('blue)('blue) should equal (1,0)    
  }

  it should "find one good if guess has one good in a secret of two" in {
    Mastermind.check('blue,'red)('blue,'green) should equal (1,0)    
    Mastermind.check('green,'red)('blue,'red) should equal (1,0)
  }

  it should "find two good if guess has two good in a secret of three" in {
    Mastermind.check('blue,'red,'red)('blue,'green,'red) should equal (2,0)       
  }

  it should "find one misplaced blue in a guess of two" in {
    Mastermind.check('blue,'red)('green,'blue) should equal (0,1)
  }

  it should "find two misplaced in a guess of four" in {
    Mastermind.check('blue,'blue,'red,'red)('green,'yellow,'blue,'blue) should equal (0,2)
  }
  it should "find two misplaced colors in a guess of four" in {
    Mastermind.check('green,'blue,'yellow,'red)('green,'yellow,'blue,'blue) should equal (1,2)
  }
}

и моя текущая реализация

package eu.byjean.mastermind

object Mastermind {
  def check(guess: Symbol*)(secret: Symbol*): (Int, Int) = {
    val (goodPairs, badPairs) = guess.zip(secret).partition { case (x, y) => x == y }
    val(guessMiss,secMiss)=badPairs.unzip
    val misplaced=guessMiss.sortBy(_.toString).zip(secMiss.sortBy(_.toString())).filter{case (x,y)=>x==y}    
    (goodPairs.size, misplaced.size)    
  }

В императивной форме, некоторые люди используют карту, и количество для каждого цвета количество вхождений цвет в тайне и в предположение (насколько неуместным идти конечно). Я попытался подход, используя метод использовать-foldleft в списке badPairs кортежа, которые приводят меня к переменной проблемы именования и называя карте.обновляется два раза в метод использовать-foldleft замком, который не кажется правильным

Любые мысли о том, как улучшить приведенный выше код. Он не чувствует себя идеально. как бы вы улучшили его по следующим осям:

  • ошибки: я пропустил что-то очевидное ?
  • производительность : эта версия с zip, распаковать, отсортировать, молнии опять же, скорее всего, не самый быстрый
  • читабельность : как бы мне определить неявный заказ на символ, так что я не придется пройти _.метод toString ,
  • идиоматические скала: есть ли в мире более "скала-иш" способ решения этой ?

Спасибо



621
2
задан 17 июля 2011 в 03:07 Источник Поделиться
Комментарии
2 ответа

Все это сжать и распаковки выглядит очень запутанным. Я думаю, что проблема здесь становится слишком много в восторге, что можно сделать с коллекцией Скала, вместо того чтобы сосредоточиться на задаче.

Одним из способов снижения зип стоимость, чтобы сделать ее на вид. Таким образом, никаких посредников коллекция создается, хотя это зависит немного о методах, называется. В любом случае молния является одним из этих методов.

Он не будет работать по вашему делу, однако, поскольку вы затем перейдите в раздел и распаковать ... я бы остерегался называть такие методы на вид, потому что они могут оказаться более дорогими, не меньше.

Я думаю, что подход карта лучше, ведь это позволяет избежать вывода(N записей N) сортировки. В частности, может быть построена за o(n), и посмотрел в постоянное время. Это как я бы сделал это:

object Mastermind {
def check(guess: Symbol*)(secret: Symbol*): (Int, Int) = {
val numOfGoodPairs = guess.view zip secret count { case (a, b) => a == b }
val guessesForSymbol = guess.groupBy(identity).mapValues(_.size)
val secretsForSymbol = secret.groupBy(identity).mapValues(_.size)
val unorderedGuesses = for {
symbol <- guessesForSymbol.keys.toSeq
secrets <- secretsForSymbol get symbol
guesses = guessesForSymbol(symbol)
} yield secrets min guesses
val numOfMisplaced = unorderedGuesses.sum - numOfGoodPairs
(numOfGoodPairs, numOfMisplaced)
}
}

В первой строке должно быть очень быстро ... это очередной итерации как догадаться и тайну, считая каждый раз, когда они равны.

Вычислительной обе карты является более дорогим, но оно должно быть дешевле, чем сортировка. Обратите внимание, что mapValues вернуть вид ценностей-это не копирование каких-либо данных. Это особенно интересно, потому что он будет только вычислить размер элементов карты для ключи, присутствующие в обоих догадаться и тайну. Это небольшая оптимизация, но вы получите его практически бесплатно.

Мы не самые сложные, просто вычитая количество правильных угадываний из числа неупорядоченных догадки.

2
ответ дан 25 июля 2011 в 03:07 Источник Поделиться

Это хуже производительность, но я надеюсь, что это немного более читаемым:

def check(guess: Symbol*)(secret: Symbol*): (Int, Int) = {
def goodBad(f: Seq[Symbol] => Seq[Symbol], s1: Seq[Symbol], s2:Seq[Symbol]) =
f(s1) zip f(s2) partition {case (x, y) => x == y }
val (goodPairs, badPairs) = goodBad(identity, guess, secret)
val (guessMiss, secMiss) = badPairs unzip
val misplaced = goodBad(_.sortBy(_.toString), guessMiss, secMiss)._1
(goodPairs.size, misplaced.size)
}

Главная проблема заключается в том, что Скала Tuple2 просто слишком тупой: вы не можете сделать много с ним, кроме как по шаблону, нет карты или копию способ и т. д.

В строкуна основе сортировки не приятно, но я не знаю лучшего способа.

Но ты не парься слишком много о производительности. Часто вам придется делать выбор между быстрой и красивой, и в этом контексте я бы выбрал "довольно".

0
ответ дан 17 июля 2011 в 07:07 Источник Поделиться