Cách để cải thiện mã này

Question

Tôi là một người mới sử dụng ngôn ngữ Scala, chỉ mới bắt đầu học ngôn ngữ.

Tôi đã giải quyết Problem 8 từ trang Dự án Euler.

Mã này trông như thế này (Tôi đã gỡ bỏ tất cả các mã để làm với việc đọc của một tập tin đầu vào):

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

Nó hoạt động tốt, kết quả là chính xác. Tuy nhiên, tôi không hoàn toàn hài lòng với giải pháp này. Tôi không thích chức năng phụ max_core và có cảm giác nó có thể được cải thiện. Sự hiểu biết của tôi về FP là, bạn nên lặp qua một danh sách, việc cắt dường như không phải là cách ở đây.

Câu hỏi đặt ra là: làm thế nào?

Answer 1

Trước tiên, tôi sẽ không phát minh lại bánh xe ... phương pháp tối đa đã được quy định tại RichInt, vì vậy bạn có thể viết a max b, cho a và b số nguyên.

ALso, slice không được chấp nhận, do đó thay vì lst.slice(0, num) Tôi sẽ sử dụng lst.take(num). Các phương thức không được chấp nhận có thể sẽ biến mất khi Scala 2.8 được khởi chạy.

CHỈNH SỬA: Thực tế, như Daniel chỉ ra, slice(Int, Int) không được dùng nữa. Tôi đã khá vội vàng khi ban đầu tôi viết điều này, và tôi đã nghĩ đến slice(Int), tương đương với drop(Int). Tôi vẫn tìm thấy số lst.take(num) để rõ ràng hơn lst.slice(0, num) :).

(nitpick) Dòng cuối cùng của bạn cũng không biên dịch khi bạn quên thêm Nil vào cuối chuỗi khuyết điểm của mình. 1::2::3::4, sẽ kết thúc bằng cách gọi :: trên số Int, không có phương pháp này. Đó là lý do tại sao bạn cần phải thêm Nil vào cuối (gọi số :: trên Nil).

Ngoài ra, thuật toán bạn đã sử dụng không rõ ràng ngay từ cái nhìn đầu tiên. Con đường tôi sẽ viết những dòng này là như sau:

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 

Tôi cảm thấy rằng dòng cuối cùng giải thích khá tốt những gì các thuật toán là phải làm - mất một cửa sổ trượt của danh sách, tính toán sản phẩm ở chỗ cửa sổ trượt và sau đó nhận được tối đa các sản phẩm tính toán (tôi đã thực hiện chức năng tối đa là sort(_ > _).head trong sự lười biếng, tôi có thể làm điều gì đó O (n) thay vì O (n log (n)) nếu hiệu suất là quan trọng ... nó vẫn chạy dưới một giây).

Lưu ý rằng chức năng trượt sẽ nằm trong thư viện Scala 2.8 (xem Daniel's post, từ đó tôi được truyền cảm hứng bằng văn bản định nghĩa trượt này).

EDIT: Rất tiếc ...xin lỗi về số /:. Tôi chỉ thích sự phù hợp của nó và thực tế là yếu tố ban đầu của màn hình xuất hiện trước danh sách. Bạn có thể viết tương đương product như sau, để được rõ ràng hơn:

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

-- Flaviu Cipcigan

Answer 2

Đây là cách tôi đã làm. Không có gì lạ mắt. Trong mã của bạn, bạn đã lấy độ dài của danh sách trong mỗi lần lặp mà là lãng phí. Tôi chỉ cần thêm một số số 1s (giống như số chữ số liên tiếp) vào cuối danh sách vì vậy tôi không cần phải kiểm tra độ dài của danh sách để chấm dứt vòng lặp.

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 = ... chuỗi // chữ số

val nums = str.map {_. asDigit}
(từ 0 đến nums.size-5) .map {i => nums.slice (i, i + 5) .product} MAX

và một số khác, hiệu quả hơn:

0.123.

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

BTW: hoạt động với 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)