Hiệu suất đệ quy danh sách Scala

Question

Câu hỏi này là về cách mà Scala thực hiện khớp mẫu và đệ quy với các danh sách và hiệu suất của chúng.

Nếu tôi có một chức năng mà recurses qua một danh sách và tôi làm điều đó với phù hợp trên một nhược điểm, ví dụ như:

def myFunction(xs) = xs match { 
    case Nil => Nil 
    case x :: xs => «something» myFunction(xs) 
} 

Trong Haskell:

myFunction [] = [] 
myFunction (x:xs) = «something» : myFunction xs 

Tôi đang sử dụng cùng ngữ nghĩa như tôi sẽ làm với, ví dụ, Haskell. Tôi không nghĩ sẽ có bất kỳ câu hỏi nào về việc triển khai Haskell vì đó đơn giản là cách bạn xử lý các danh sách. Đối với một danh sách dài (tôi sẽ được hoạt động trên một danh sách với một vài nghìn nút), Haskell sẽ không nhấp nháy (tôi tưởng tượng mặc dù; tôi đã không bao giờ cố gắng).

Nhưng từ những gì tôi hiểu với Scala, báo cáo kết quả trận đấu sẽ gọi phương thức vắt unapply chia danh sách xung quanh các khuyết điểm và mở rộng ví dụ để một chức năng mà không làm gì vào danh sách:

def myFunction(xs) = xs match { 
    case Nil => Nil 
    case x :: xs => x :: myFunction(xs) 
} 

Trong Haskell:

myFunction [] = [] 
myFunction (x:xs) = x : myFunction xs 

nó sẽ gọi áp dụng phương pháp vắt để chống lại với nhau. Đối với một danh sách dài tôi tưởng tượng điều này sẽ rất tốn kém.

Để minh họa, trong trường hợp cụ thể của tôi, tôi muốn kiểm tra lại danh sách các ký tự và tích lũy nhiều thứ, trong đó chuỗi đầu vào là bất cứ thứ gì lên tới vài chục kilobyte.

Tôi có thực sự đang gọi các nhà thầu và bộ giải nén cho mỗi bước đệ quy nếu tôi muốn tái khám trong một danh sách dài không? Hoặc là có tối ưu? Hoặc cách tốt hơn để làm điều đó? Trong trường hợp này, tôi sẽ cần một vài biến tích lũy và rõ ràng là tôi sẽ không đệ quy lên một danh sách không làm gì cả ...

(Vui lòng giải thích Haskell, tôi đã không viết dòng trong hai năm.)

(Và có, tôi sẽ cho đệ quy đuôi.)

Answer 1

Đầu tiên, Haskell là không nghiêm ngặt, vì vậy các cuộc gọi hàm trên đuôi này có thể không bao giờ được đánh giá. Scala, mặt khác, sẽ tính toán tất cả các danh sách trước khi trở về. Một thực hiện gần gũi hơn với những gì xảy ra trong Haskell sẽ là:

def myFunction[T](l: List[T]): Stream[T] = l match { 
    case Nil => Stream.empty 
    case x :: xs => x #:: myFunction(xs) 
} 

Đó nhận List, đó là nghiêm ngặt, và trả về một Stream đó là không nghiêm ngặt.

Bây giờ, nếu bạn muốn tránh mô hình kết hợp và nhổ (mặc dù không được gọi trong trường hợp đặc biệt này - xem bên dưới), bạn có thể chỉ làm điều này:

def myFunction[T](xs: List[T]): Stream[T] = 
    if (xs.isEmpty) Stream.empty else xs.head #:: myFunction(xs.tail) 

Tôi chỉ nhận ra bạn có ý định đi cho đệ quy đuôi. Những gì bạn viết không phải là đệ quy đuôi, bởi vì bạn thêm x vào kết quả của đệ quy.Khi xử lý danh sách, bạn sẽ nhận được đuôi đệ quy nếu bạn tính toán kết quả ngược và sau đó đảo ngược:

def myFunction[T](xs: List[T]): List[T] = { 
    def recursion(input: List[T], output: List[T]): List[T] = input match { 
    case x :: xs => recursion(xs, x :: output) 
    case Nil => output 
    } 
    recursion(xs, Nil).reverse 
} 

ngoái, chúng ta hãy ngược một ví dụ để xem làm thế nào nó hoạt động:

class ListExample { 
    def test(o: Any): Any = o match { 
    case Nil => Nil 
    case x :: xs => xs 
    case _ => null 
    } 
} 

Tạo:

public class ListExample extends java.lang.Object implements scala.ScalaObject{ 
public ListExample(); 
    Code: 
    0: aload_0 
    1: invokespecial #10; //Method java/lang/Object."<init>":()V 
    4: return 

public java.lang.Object test(java.lang.Object); 
    Code: 
    0: aload_1 
    1: astore_2 
    2: getstatic  #18; //Field scala/Nil$.MODULE$:Lscala/Nil$; 
    5: aload_2 
    6: invokestatic #24; //Method scala/runtime/BoxesRunTime.equals:(Ljava/lang/Object;Ljava/lang/Object;)Z 
    9: ifeq 18 
    12: getstatic  #18; //Field scala/Nil$.MODULE$:Lscala/Nil$; 
    15: goto 38 
    18: aload_2 
    19: instanceof  #26; //class scala/$colon$colon 
    22: ifeq 35 
    25: aload_2 
    26: checkcast  #26; //class scala/$colon$colon 
    29: invokevirtual #30; //Method scala/$colon$colon.tl$1:()Lscala/List; 
    32: goto 38 
    35: aconst_null 
    36: pop 
    37: aconst_null 
    38: areturn 

public int $tag() throws java.rmi.RemoteException; 
    Code: 
    0: aload_0 
    1: invokestatic #42; //Method scala/ScalaObject$class.$tag:(Lscala/ScalaObject;)I 
    4: ireturn 

} 

Giải mã, trước tiên nó gọi phương thức equals trên tham số được truyền và đối tượng Nil. Trả về sau nếu đúng. Nếu không, nó gọi instanceOf[::] trên đối tượng. Nếu đúng, nó sẽ tạo đối tượng cho đối tượng đó và gọi phương thức tl trên đó. Không làm tất cả, tải cosntant null và trả về nó.

Vì vậy, bạn thấy, x :: xs không gọi bất kỳ bộ giải nén nào.

Đối với tích lũy, có một mẫu bạn có thể muốn xem xét:

val list = List.fill(100)(scala.util.Random.nextInt) 
case class Accumulator(negative: Int = 0, zero: Int = 0, positive: Int = 0) 
val accumulator = list.foldLeft(Accumulator())((acc, n) => 
    n match { 
    case neg if neg < 0 => acc.copy(negative = acc.negative + 1) 
    case zero if zero == 0 => acc.copy(zero = acc.zero + 1) 
    case pos if pos > 0 => acc.copy(positive = acc.positive + 1) 
    }) 

Các thông số mặc định và sao chép các phương pháp là một tính năng Scala 2.8 tôi đã sử dụng chỉ để làm ví dụ đơn giản, nhưng điểm đang sử dụng foldLeft phương pháp khi bạn muốn tích lũy mọi thứ trong danh sách.