Tại sao bộ lọc ở phía trước foldLeft chậm ở Scala?

Question

tôi đã viết một câu trả lời cho câu hỏi đầu tiên Project Euler:

Thêm tất cả các số tự nhiên dưới một ngàn mà là bội số của 3 hoặc 5.

Việc đầu tiên mà đến với tôi là:

(1 until 1000).filter(i => (i % 3 == 0 || i % 5 == 0)).foldLeft(0)(_ + _) 

nhưng nó chậm (phải mất 125   ms), vì vậy tôi viết lại nó, chỉ cần nghĩ đến việc 'một cách khác' so với 'cách nhanh'

(1 until 1000).foldLeft(0){ 
    (total, x) => 
     x match { 
      case i if (i % 3 == 0 || i % 5 ==0) => i + total // Add 
      case _ => total //skip 
     } 
} 

Điều này nhanh hơn nhiều (chỉ 2   ms). Tại sao? Tôi đoán phiên bản thứ hai chỉ sử dụng trình tạo phạm vi và không hiển thị bộ sưu tập được nhận dạng đầy đủ theo bất kỳ cách nào, thực hiện tất cả trong một lần, nhanh hơn và ít bộ nhớ hơn. Tôi có đúng không?

Đây mã trên IdeOne: http://ideone.com/GbKlP

Answer 1

Sự cố, như những người khác đã nói, là filter tạo bộ sưu tập mới. Thay thế withFilter thì không, nhưng không có foldLeft. Ngoài ra, việc sử dụng .view, .iterator hoặc .toStream tất cả sẽ tránh tạo bộ sưu tập mới theo nhiều cách khác nhau, nhưng tất cả đều chậm hơn ở đây so với phương pháp đầu tiên bạn sử dụng.

Nhưng, sau đó ...Xem, 1 until 1000 là một Range, có kích thước thực sự là rất nhỏ, bởi vì nó không lưu trữ từng phần tử. Ngoài ra, là cực kỳ được tối ưu hóa và thậm chí là specialized, không phải là trường hợp của bất kỳ bộ sưu tập nào khác. Kể từ khi foldLeft được triển khai dưới dạng foreach, miễn là bạn ở lại với một Range bạn có thể tận hưởng các phương pháp được tối ưu hóa của nó.

(_: Range).foreach:

@inline final override def foreach[@specialized(Unit) U](f: Int => U) { 
    if (length > 0) { 
     val last = this.last 
     var i = start 
     while (i != last) { 
      f(i) 
      i += step 
     } 
     f(i) 
    } 
} 

(_: Range).view.foreach

def foreach[U](f: A => U): Unit = 
    iterator.foreach(f) 

(_: Range).view.iterator

override def iterator: Iterator[A] = new Elements(0, length) 

protected class Elements(start: Int, end: Int) extends BufferedIterator[A] with Serializable { 
    private var i = start 

    def hasNext: Boolean = i < end 

    def next: A = 
    if (i < end) { 
     val x = self(i) 
     i += 1 
     x 
    } else Iterator.empty.next 

    def head = 
    if (i < end) self(i) else Iterator.empty.next 

    /** $super 
    * '''Note:''' `drop` is overridden to enable fast searching in the middle of indexed sequences. 
    */ 
    override def drop(n: Int): Iterator[A] = 
    if (n > 0) new Elements(i + n, end) else this 

    /** $super 
    * '''Note:''' `take` is overridden to be symmetric to `drop`. 
    */ 
    override def take(n: Int): Iterator[A] = 
    if (n <= 0) Iterator.empty.buffered 
    else if (i + n < end) new Elements(i, i + n) 
    else this 
} 

(_: Range).view.iterator.foreach

def foreach[U](f: A => U) { while (hasNext) f(next()) } 

Và đó, tất nhiên, thậm chí không đếm filter giữa view và foldLeft:

override def filter(p: A => Boolean): This = newFiltered(p).asInstanceOf[This] 

protected def newFiltered(p: A => Boolean): Transformed[A] = new Filtered { val pred = p } 

trait Filtered extends Transformed[A] { 
    protected[this] val pred: A => Boolean 
    override def foreach[U](f: A => U) { 
    for (x <- self) 
     if (pred(x)) f(x) 
    } 
    override def stringPrefix = self.stringPrefix+"F" 
} 

Answer 2

Nhìn qua các mã, nó trông giống như filter không xây dựng một Seq mới mà trên đó các foldLeft được gọi. Thứ hai bỏ qua bit đó. Nó không phải là quá nhiều bộ nhớ, mặc dù điều đó không thể nhưng giúp đỡ, nhưng bộ sưu tập được lọc không bao giờ được xây dựng ở tất cả. Tất cả công việc đó không bao giờ được thực hiện.

Phạm vi sử dụng TranversableLike.filter, trông như thế này:

def filter(p: A => Boolean): Repr = { 
    val b = newBuilder 
    for (x <- this) 
    if (p(x)) b += x 
    b.result 
} 

Tôi nghĩ rằng đó là += trên dòng 4 đó là sự khác biệt. Lọc theo số foldLeft sẽ loại bỏ nó.

Answer 3

Cố gắng làm cho bộ sưu tập lười biếng đầu tiên, vì vậy

(1 until 1000).view.filter... 

thay vì

(1 until 1000).filter... 

Điều đó sẽ tránh được chi phí xây dựng một bộ sưu tập trung. Bạn cũng có thể nhận được hiệu suất tốt hơn từ việc sử dụng sum thay vì foldLeft(0)(_ + _), luôn có thể một số loại bộ sưu tập có thể có cách hiệu quả hơn để tổng số. Nếu không, nó vẫn sạch hơn và khai báo hơn ...

Answer 4

filter tạo một chuỗi hoàn toàn mới mà sau đó gọi là foldLeft. Hãy thử:

(1 until 1000).view.filter(i => (i % 3 == 0 || i % 5 == 0)).reduceLeft(_+_)

Điều này sẽ ngăn chặn cho biết tác dụng, chỉ đơn thuần gói điều gốc. Trao đổi foldLeft với reduceLeft chỉ là mỹ phẩm (trong trường hợp này).

Answer 5

Thách thức hiện nay là, bạn có thể nghĩ ra một cách hiệu quả hơn chưa? Không phải là giải pháp của bạn quá chậm trong trường hợp này, nhưng nó có quy mô như thế nào không? Điều gì sẽ xảy ra nếu thay vì 1000, nó là 1000000000? Có một giải pháp có thể tính toán trường hợp sau cũng nhanh như trước đây.