Modi per migliorare questo codice

Question

Sono un principiante alla Scala, sto appena iniziando a imparare la lingua.

Ho risolto Problem 8 dalla pagina Project Euler.

Il codice simile a questo (ho rimosso tutto il codice a che fare con la lettura di un file di input):

 
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)) 

Funziona bene, il risultato è corretto. Tuttavia, non sono completamente soddisfatto di questa soluzione. Non mi piace la sottofunzione max_core e ho la sensazione che possa essere migliorata. La mia comprensione di FP è, si dovrebbe scorrere su una lista, l'affettatura sembra non essere la strada qui.

La domanda è: come?

Answer 1

In primo luogo, io non reinventare la ruota ... il metodo di massima già è definito in RichInt, in modo da poter scrivere a max b, per a e b interi.

Inoltre, slice è obsoleto, quindi anziché lst.slice(0, num) userei lst.take(num). Probabilmente i metodi deprecati spariranno quando verrà lanciato Scala 2.8.

EDIT: Infatti, come Daniel indicate, slice(Int, Int) non è obsoleto. Avevo abbastanza fretta quando ho inizialmente scritto questo, e stavo pensando a slice(Int), che equivale a drop(Int). Trovo ancora che lst.take(num) sia più chiaro di lst.slice(0, num) :).

(nitpick) Anche l'ultima riga non viene compilata poiché si è dimenticato di aggiungere Nil alla fine della sequenza di svantaggi. 1::2::3::4, finirebbe invocando :: su un Int, che non ha questo metodo. Ecco perché è necessario aggiungere Nil alla fine (invocare :: su Nil).

Inoltre, l'algoritmo che hai utilizzato non è evidente a prima vista. Il modo in cui vorrei scrivere questo è il seguente:

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 

sento che l'ultima riga spiega molto bene ciò che l'algoritmo dovrebbe fare - prendere una finestra scorrevole della lista, calcolare il prodotto in quella finestra scorrevole e quindi ottenere il massimo dei prodotti calcolati (ho implementato la massima funzione come sort(_ > _).head per pigrizia, avrei potuto fare qualcosa O (n) piuttosto che O (n log (n)) se la prestazione era critica ... continua a funzionare sotto un secondo però).

Si noti che la funzione di scorrimento sarà nella libreria di Scala 2.8 (vedere Daniel's post, da cui mi sono ispirato a scrivere questa definizione di scorrimento).

MODIFICA: Oops ...mi dispiace per lo /:. Mi piace solo la concisione di ciò e il fatto che l'elemento iniziale della piega viene prima della lista. Si potrebbe equivalentemente scrivere product come il seguente, per essere più espliciti:

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

-- Flaviu Cipcigan

Answer 2

Questo è il modo in cui l'ho fatto. Nulla di bello. Nel tuo codice, stavi prendendo la lunghezza della lista in ogni iterazione che è piuttosto dispendiosa. Aggiungo solo un numero di 1 s (uguale al numero di cifre consecutive) alla fine dell'elenco, quindi non è necessario controllare la lunghezza dell'elenco per terminare il ciclo.

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)) 

Answer 3

val = str ... // stringa di cifre

nums val = str.map {_. asDigit}
(da 0 a nums.size-5) .map {i => nums.slice (i, i + 5) .product} .MAX

e un altro, più efficiente:

0.123.

(da 0 a nums.size-5) .foldLeft (-1) {case (R, I) => r max nums.slice (i, i + 5) .product}

BTW: funziona con scala2 .8

Answer 4

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)