Более функциональный способ написания этой палиндром экстрактор?


Я писал этот палиндром экстрактор. И хотя он работает, и я могу решить проблему с ним, он чувствует себя очень Java-подобном. Мне было интересно, какие изменения я могу сделать для того, чтобы быть более функциональной.

import collection.mutable._

object Level1 {
    def palindrome(input:String) = input.reverse == input

    def extractPalindromes(input:String) = 
    {
        var counter = 0
        val palindromes = new ListBuffer[String]()
        while(counter < input.length)
        {
            var localCounter = 2
            while((counter + localCounter) < input.length)
            {
                //println("counter:"+counter+" localCounter:"+localCounter)
                val tempString = input.substring(counter, input.length - localCounter)
                if(palindrome(tempString)) palindromes += tempString
                localCounter += 1
            }       
            counter += 1
        }
        palindromes
    }

    def main(args:Array[String]) = {
        val input = "I like racecars that go fast"
        extractPalindromes(input).filter(_.length > 4).foreach(println)
    }
}


6637
7
задан 7 октября 2011 в 09:10 Источник Поделиться
Комментарии
5 ответов

Это может быть как простой, как:

scala> val str =  "I like racecars that go fast"
str: java.lang.String = I like racecars that go fast

scala> for { i <- 2 to str.size; s <- str.sliding(i) if s == s.reverse} yield s
res5: scala.collection.immutable.IndexedSeq[String] = Vector(cec, aceca, racecar)

12
ответ дан 7 октября 2011 в 10:10 Источник Поделиться

Улучшение на ответ @Zwirb это:

Если вы не только ищете палиндром максимальной длины, то лучше попробовать сначала самой длинной горки. Лень (срабатывает на вид) уменьшится сложности, а также.

(for { i <- (str.size to 2 by -1).view ; s <- str.sliding(i) if s == s.reverse} yield s) headOption

3
ответ дан 16 ноября 2011 в 08:11 Источник Поделиться

Поскольку у нас есть выполнение работы, теперь мы можем оптимизировать его. Каждый шаги будут показаны, чтобы имитировать сеанс обзора кода (хотя и шизофреник один).

Фаза 1 : лимит создания объектов.

обратная создает новую строку. Но после просмотра создается только новый (легкий) вид.
Действительно, заменив ул. сползая по ул. вид.раздвижные сократить время процесса. Для 6 клавиши, это не так уж плохо.

2 этап : доработать алгоритм.

На самом деле это должна быть фаза 0, но вы никогда не знаете, когда идеи всплывают.
Каждый палиндром содержит матрешка вложенных палиндромы.
Это означает, что все п предприятий могут быть обнаружены с н-2 размера, просто проверяя 2 новых чаров на границах.

Введем вспомогательный

def collectPalindrome(str: String, from: Int, to: Int): List[String] =
if (str(from) == str(to)) {
str.slice(from, to+1) :: (if (from > 0 && to < str.size - 1) collectPalindrome(str, from-1, to+1) else Nil)
} else Nil

Не лишним создание объекта. Так что это двойная победа !
Поскольку собранные размеры увеличиваются в 2, нам нужно 2 прохода :

def extractPalindromes (str: String) : List[String] =
{
val evenSized: List[String] = ((for (i <- (0 to str.size - 2)) yield collectPalindrome(str,i,i+1)) flatten).toList
val oddSized: List[String] = ((for (i <- (0 to str.size - 3)) yield collectPalindrome(str,i,i+2)) flatten).toList
evenSized ++ oddSized
}

Результат ввода genlin :

Reference (Zwirb)    : 233 s
Stopping at longest : 232 s (nb : only extract 1 palindrome)
So benchmarking proves my claim wrong.
Idem + .view. : 120 s (nb : only extract 1 palindrome)
New algorithm : 0.006 s

Этап 3 : Оптимизация.

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


  • помощника более описательное название : collectIncreasingPalindromes

  • перемещения связаны проверки на вершине. Помощник стал robuster и более читабельным.

  • скрыть этот помощник

  • Сухой

  • документ

  • наконец-то я предпочитаю карту. Затем карту + выровнять = помощью flatMap

Результат :

def extractPalindromes (str: String): List[String] = {

//@brief Collect nested palindromes increasing by 1 char at each end.
def collectIncreasing(from: Int, until: Int): List[String] =
if ( from < 0 || until > str.size //Out of bounds
|| str(from) != str(until-1) ) Nil
else str.slice(from, until) :: collectIncreasing(from-1, until+1)

//@brief Start to collect from given size, for each position
def collect (n: Int) = (0 to str.size - n) flatMap
(i => collectIncreasing (i, i+n))

(collect (2) ++ collect (3)).toList // Even sized then odd sized palindromes
}

Этап 4 : Распараллелить.

Благодаря функциональному подходу, она должна быть просто вопрос перехода на параллельных коллекций.

Этап 5 : бросьте вызов другу

2
ответ дан 18 ноября 2011 в 08:11 Источник Поделиться

Вот общее представление о том, как я бы, наверное, подойти к проблеме:

def extractPalindromes(input:String) = 
{
var minLength = 4;
val palindromes = new ListBuffer[String]()
if (palindrome(input)) palindromes += input
if (input.length > minLength) {
palindromes += extractPalindromes(input.substring(1, input.length-1))
palindromes += extractPalindromes(input.substring(0, input.length-1))
}
palindromes
}

Будьте предупреждены, однако, что я обычно не пишу на Scala, так что я, несомненно, получил по крайней мере некоторые детали неправильно. Я особенно не уверены в часть, который пытается объединить два ListBuffer вместе, используя += (и minlength действительно должны быть постоянной или параметром). В общем понятии, как это работает должно быть правильно, хотя:


если входной ток палиндром, добавим его в список
найти палиндромы с первого удаляемого символа
найти палиндромы с последнего символа удалены
собрать все эти результаты и вернуть их

Обратите внимание, что вместо того, чтобы генерировать все палиндромы, затем отфильтровать какие-либо слишком короткие, я написал это, чтобы генерировать только те не менее указанной минимальной длины (4 в данном случае). Как отмечалось выше, минимальная длина должна быть константа или параметр, а не ВАР, но это должно быть довольно незначительной корректировке.

1
ответ дан 7 октября 2011 в 10:10 Источник Поделиться

Данного решения просты, но имеют квадратичную сложность. Я пытался улучшить его, сохраняя его строго функционален.

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

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

Итак, вот она:

def palindromes(input: String): Set[String] = {                                                                 
type PalPointers = (Set[Int], Set[Int])
type Candidates = Map[String, PalPointers]

def increment = (_: Int) + 1
def decrement = (_: Int) - 1
def withinBounds = input.indices contains (_: Int)
def filterPositions(forwardSet: Set[Int], reverseSet: Set[Int]): PalPointers = {
val hasReverse = (forward: Int) => reverseSet exists (forward <=)
val hasForward = (reverse: Int) => forwardSet exists (reverse >=)
(forwardSet filter hasReverse, reverseSet filter hasForward)
}
def hasViablePositions = (_: PalPointers) match {
case (forwardSet, reverseSet) => forwardSet.nonEmpty && reverseSet.nonEmpty
}

def getSolutions(candidates: Candidates): Set[String] = {
def getEven(candidate: String) = {
val (forwardSet, reverseSet) = candidates(candidate)
if ((forwardSet & (reverseSet map decrement)).nonEmpty) Set(candidate + candidate.reverse)
else Set.empty
}

def getOdd(candidate: String) = {
val (forwardSet, reverseSet) = candidates(candidate)
if ((forwardSet & reverseSet).nonEmpty) Set(candidate + candidate.init.reverse)
else Set.empty
}

for {
candidate <- candidates.keySet
palindrome <- getEven(candidate) ++ getOdd(candidate)
} yield palindrome
}

def findPal(currentSolution: Set[String], currentCandidates: Candidates) : Set[String] = {
val newCandidates = for {
(candidate, (leftToRightSet, rightToLeftSet)) <- currentCandidates
nextCh <- leftToRightSet map increment filter withinBounds map input
isNextCh = (i: Int) => withinBounds(i) && input(i) == nextCh
forwardSetCandidate = leftToRightSet map increment filter isNextCh
reverseSetCandidate = rightToLeftSet map decrement filter isNextCh
palPointers = filterPositions(forwardSetCandidate, reverseSetCandidate)
if hasViablePositions(palPointers)
} yield (candidate + nextCh, palPointers)

if (newCandidates.isEmpty) currentSolution
else findPal(currentSolution ++ getSolutions(newCandidates), newCandidates)
}

def setup(charPointers: List[(Char, Int)], candidates: Candidates): Candidates = charPointers match {
case (ch, pos) :: tail =>
val candidate = ch.toString
val (forwardSet, reverseSet) = (candidates getOrElse (candidate, (Set.empty, Set.empty): PalPointers))
setup(tail, candidates.updated(candidate, (forwardSet + pos, reverseSet + pos)))
case Nil =>
candidates map {
case (key, (forwardSet, reverseSet)) => key -> filterPositions(forwardSet, reverseSet)
} filter {
case (_, positions) => hasViablePositions(positions)
}
}

val initialCandidates = setup(input.zipWithIndex.toList, Map.empty)
val initialSolutions = getSolutions(initialCandidates)
findPal(initialSolutions filter (_.length > 1), initialCandidates)
}

Я хотел бы знать, насколько эффективно все это действительно манипуляция, поэтому я сопоставив ее все. Мое решение-два порядка величины быстрее, чем один вопрос, а три, чем принято решение для входных greplin. С большой-ой отличается, это приведет к изменению в зависимости от характеристик входных и размер входных.

1
ответ дан 8 октября 2011 в 11:10 Источник Поделиться