Способы улучшить этот код

Question

Я новичок в Scala, только начинаю изучать язык.

Я решил Задача 8 со страницы Project Euler.

Код выглядит следующим образом (я удалил весь код, связанный с чтением входного файла):

def max(n1: Int, n2: Int): Int = Math.max(n1, n2)

def max_product(digits: List[Int], num: Int): Int = {
    def max_core(lst: List[Int], curr_max: Int): Int = lst match {
        case a if lst.length >= num => 
            max_core(a.tail, max(lst.slice(0, num).reduceLeft(_*_), curr_max))
        case _ => curr_max
    }

    max_core(digits, 0)
}

println(max_product(1::2::3::4::2::3::Nil, 2))

Работает нормально, результат правильный. Однако я не совсем доволен этим решением. Мне не нравится подфункция max_core, и я чувствую, что ее можно улучшить. Насколько я понимаю, вы должны выполнять итерации по списку, нарезка, похоже, не подходит.

Вопрос: как?

Answer 1

Во-первых, я бы не стал изобретать велосипед ... метод max уже определен в RichInt, поэтому вы можете написать a max b, для a и b целых чисел.

ALso, slice устарело, поэтому вместо lst.slice(0, num) я бы использовал lst.take(num). Устаревшие методы, вероятно, исчезнут при запуске Scala 2.8.

РЕДАКТИРОВАТЬ: Действительно, как указал Даниил , slice(Int, Int) не считается устаревшим. Я очень спешил, когда впервые написал это, и думал о slice(Int), что эквивалентно drop(Int). Я все еще нахожу lst.take(num) более понятным, чем lst.slice(0, num) :).

(nitpick) Ваша последняя строка также не компилируется, так как вы забыли добавить Nil в конец вашей последовательности минусов. 1::2::3::4, в конечном итоге вызовет :: на Int, который не имеет этого метода. Вот почему вам нужно добавить Nil в конец (вызвать :: на Nil).

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

val numbers = /*"--the string of numbers--"*/.map(_.asDigit).toList

def sliding[A](xs: List[A], w: Int): List[List[A]] = {
  for(n <- List.range(0, xs.size - w)) 
    yield xs drop n take w
}

def product(xs: List[Int]): Int = (1 /: xs) (_ * _)

sliding(numbers, 5).map(product).sort(_ > _).head

Мне кажется, что последняя строка довольно хорошо объясняет, что должен делать алгоритм - взять скользящее окно списка, вычислить произведение в этом скользящем окне и затем получить максимум рассчитанных произведений (я реализовал максимум функционируя как sort(_ > _).head из-за лени, я мог бы сделать что-то O (n), а не O (n log (n)), если производительность была критической ... хотя она все еще работает менее секунды).

Обратите внимание, что функция скольжения будет в библиотеке Scala 2.8 (см. Пост Даниэля , откуда я был вдохновлен при написании этого определения скольжения).

РЕДАКТИРОВАТЬ: Упс ... извините за /:. Мне просто нравится его краткость и тот факт, что начальный элемент сгиба стоит перед списком. Вы можете эквивалентно написать product следующим образом, чтобы быть более точным:

def product(xs: List[Int]): Int = xs.foldLeft(1)(_ * _)

-- Flaviu Cipcigan

Answer 2

val bigNumber = """73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450""".replaceAll("\\s+","")

def getMax(m: Int, l:List[Seq[Int]]): Int = 
  if (l.head.isEmpty) m else
  getMax(m max l.foldLeft(1) ((acc, l) => acc * l.head), l map (_ tail))

def numDigits(bigNum: String, count: Int) = 
  (1 until count).foldLeft(List(bigNumber map (_ asDigit))) ((l, _) => l.head.tail :: l)

def solve(bigNum: String, count: Int) = getMax(0, numDigits(bigNum, count))

solve(bigNumber, 5)

Answer 3

val str = ... // строка цифр

val nums = str.map {_.asDigit}
(От 0 до nums.size-5) .map {i => nums.slice (i, i + 5) .product} .max

и еще один, более эффективный:

(0 до nums.size-5) .foldLeft (-1) {case (r, i) => r max nums.slice (i, i + 5) .product}

Кстати: работает с scala2.8

Answer 4

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

val s = ... // string of digits
val ds = s.map(_.asDigit).toList

def findMaxProduct(ds: List[Int], n: Int, max: Int): Int = ds match {
  case Nil => max
  case _ :: rest => findMaxProduct(rest, n, Math.max(max, ds.take(n).reduceLeft(_ * _)))
}

val n = 5 // number of consecutive digits
println(findMaxProduct(ds ::: List.make(n, 1), n, -1))