>

스칼라로 작성된 간단한 아나그램 파인더에 대한 생각을 듣고 싶습니다. 나는 주로 심각한 스칼라를 쓰는 첫 번째 방법으로 이것을 썼고 Scalaz 라이브러리를 사용 해보고 싶었습니다.

기능적 언어에 대한 경험이 적은 Java 배경에서 왔습니다. 내가 피드백에 대해 이상적으로 좋아하는 것 :

  • 필수 성을 떨어 뜨리기위한 개선 사항
  • Scalaz와 같은 다른 라이브러리 코드 사용

내가 모든 테스트 사례를 다루지 않았 음을 알았지 만 이것이 나에게 달려 가기에 충분했습니다.

일반 알고리즘 :
  • 단어 목록을 구문 분석하십시오. 각 단어를 소문자로 바꾸고 알파벳순으로 정렬하여 단어의 '서명'으로 취급하십시오.
  • 키를 서명으로하고 값을 동일한 서명을 가진 단어의 집합 (또는 목록)으로 서명과 단어를지도에 삽입합니다
  • 검색은 단순히 서명을 기반으로 단어를 찾는 것입니다
서명 클래스

case class Stem(word: String) {
  val stem: List[Char] = word.toLowerCase.trim.toList.sortWith((e1, e2) => (e1 < e2))
  override def equals(p1: Any) = p1 match {
    case s: Stem => s.stem == stem
    case _ => false
  }
  override def hashCode = stem.hashCode
  override def toString = stem.mkString("Stem(", "", ")")
}

참고:

stem 가 아닌 단어를 매개 변수로 사용하여 알파벳 순서로 조작 할 수 있다고 확신합니다.  들. 나는 equals 를 생략 할 수 있었을 것이라고 확신합니다  그리고 hashCode  그런 다음 방법을 수행 할 수 없었습니다. 내가 case class 를 사용하고 있기 때문에 아마 생각  여기 요?

애너그램 파인더 클래스

import scalaz._
import Scalaz._
class AnagramFinder(words: List[String]) {
  implicit def string2Stem(s: String): Stem = Stem(s)
  val mapping = createMapping(words)
  def createMapping(words: List[String]) = {
    var anagrams: Map[Stem, Set[String]] = Map()
    words.foreach(s => anagrams = anagrams |+| Map(Stem(s) -> Set(s)))
    anagrams
  }
  def find(word: String): Option[Set[String]] = mapping.get(word)
}

참고:

정말 anagrams |+| Map(Stem(s) -> Set(s)) 를 갖고 싶었습니다.  내 foreach 에서 , 그러나 (a) 대신 변경 가능한 맵을 사용하면 좋을 것입니다. 그러나 (b) 내가 고생 한 변경 가능한 맵에 대한 반 그룹 구현을 작성해야했습니다.

또한 anagrams |+| Map(Stem(s) -> Set(s))  내 암시 적 String to Stem 메소드를 선택하지 않습니다. 왜요?

애너그램 개체

object Anagrams {
  def apply(wordListFile: String, word: String) = {
    val finder = new AnagramFinder(scala.io.Source.fromFile(wordListFile).mkString.split('\n').toList)
    finder.find(word)
  }
}

참고 사항: 단어 목록을 val 로 초기화해야한다는 것을 알고 있습니다.  호출간에 재사용 할 수있는 객체의 필드이지만 실제로 시작하기위한 것이 었습니다.

부록 : 테스트

class StemTest extends org.scalatest.FunSuite {
  test("Stem of noel is e,l,n,o") {
    assert(Stem("noel").stem == List('e','l','n','o'))
  }
  test("Stem of Hello is H,e,l,l,o") {
    assert(Stem("Hello").stem == List('H', 'e', 'l', 'l', 'o'))
  }
  test("Stems of abc and cba are equal") {
    assert(Stem("abc") == Stem("cba"))
  }
}
class AnagramFinderTest extends FunSuite {
  test("List of words should create appropriate map") {
    val testMap:Map[Stem, Set[String]] = Map(Stem("abc") -> Set("cba"), Stem("def") -> Set("def"), Stem("ggz") -> Set("zgg"))
    val givenList = List("cba", "def", "zgg")
    val mapping = new AnagramFinder(givenList).mapping
    assert(mapping == testMap)
  }
  test("Same stemmed words should both exist in the map") {
    val testMap:Map[Stem, Set[String]] = Map(Stem("abc") -> Set("abc", "cba"))
    val givenList = List("abc", "cba")
    val mapping = new AnagramFinder(givenList).mapping
    assert(mapping == testMap)
  }
  test("Finding words") {
    val givenList = List("abc", "cba", "bob", "bca")
    val anagramFinder = new AnagramFinder(givenList)
    val foundAnagrams = anagramFinder.find("abc").get
    val expected = Set("abc", "bca", "cba")
    assert(foundAnagrams.forall(s => expected contains s))
    assert(expected.forall(s => foundAnagrams contains s))
  }
  test("Full test") {
    val expected = Some(Set("act", "cat", "Cat"))
    val actual = Anagrams("/usr/share/dict/words", "cat")
    assert(expected == actual)
  }
}

  • 답변 # 1

    코드 개선을위한 몇 가지 제안 :

    xs.sortWith((e1, e2) => (e1 < e2))   xs.sorted 와 동일

    Stem.word 에 관심이 없다면  컴패니언의 적용 방법에 배치 할 수 있습니다 :

    object Stem {
      def apply(word: String): Stem = {
        val stem: List[Char] = word.toLowerCase.trim.toList.sorted
        new Stem(stem)
      }
    }
    case class Stem private(stem: List[Char])
    
    

    <시간>

    source.mkString.split('\n')   source.getLines 와 동일

    <시간>

    무언가를 요약하거나 누산기를 사용할 때마다 fold  당신이 찾고있는 것입니다 :

    (Map.empty[Stem, Set[String]] /: words) {
      case (map, word) => map + (Stem(word) -> Set(word))
    }
    
    

    스칼라 즈의 도움으로 :

    words.map(word => Map(Stem(word) -> Set(word))) reduceLeft { _|+|_ }
    
    

    reduce   fold 입니다 : xs.tail.fold(xs.head)(f)

    /:   foldLeft 의 동의어입니다 : (init /: xs)(f) == (xs foldLeft init)(f)

    <시간>

    내재적 변환 String => Stem   string -> set 에서 작동하지 않습니다   -> 때문에  이미 암시 적 변환이 필요하며 한 번에 여러 변환을 적용 할 수 없습니다. 튜플 표기법 (string, set) 를 사용하는 경우 , 암시 적 변환이 적용됩니다.

  • 이전 javascript - 스크롤 할 때 컨테이너 안에있을 때 div를 고정하십시오
  • 다음 algorithm - 고유 한 정수 합