Tại sao Danh sách Scala không có trường kích thước?

Question

Xuất phát từ nền Java, tôi tự hỏi tại sao List trong Scala không có trường size giống như Java tương đương LinkedList. Sau khi tất cả, với một lĩnh vực kích thước bạn sẽ có thể xác định kích thước của danh sách trong thời gian không đổi, vậy tại sao là trường kích thước giảm?

(Câu hỏi này đề cập đến các lớp học tập mới trong Scala 2.8 và sau đó. Ngoài ra, tôi đang đề cập đến bất biến List, không phải là người có thể thay đổi.)

Answer 1

Người ta không thể nói lĩnh vực kích thước là giảm, dạng danh sách như vậy mà không có kích thước đã tồn tại 50 năm kể từ khi LISP mà họ đang có mặt khắp nơi và họ đang rất phổ biến ở ML và Haskell quá, cả hai đều có ảnh hưởng trong scala.

Lý do cơ bản là danh sách đó là cấu trúc đệ quy. Một không trống List là Cons(head: A, tail: List[A]) - ngoại trừ rằng Cons thực ra được gọi là :: để cho phép ký hiệu thuận tiện. Bạn có thể truy cập đuôi (danh sách không có phần tử đầu của nó) và đó cũng là một danh sách. Và điều này được thực hiện chỉ là về tất cả các thời gian. Vì vậy, việc đếm số trong danh sách sẽ không có nghĩa là chỉ thêm một số nguyên, nhưng càng nhiều số nguyên càng có nhiều phần tử. Điều này là khả thi, nhưng chắc chắn không miễn phí.

Nếu bạn so sánh với java LinkedList, LinkedList có triển khai đệ quy (dựa trên Nút, ít nhiều giống như Nhược điểm, nhưng có liên kết theo cả hai hướng). Nhưng LinkedList không phải là một Node, nó sở hữu chúng (và giữ số lượng của chúng). Vì vậy, trong khi nó có một triển khai đệ quy, bạn không thể xử lý nó một cách đệ quy. Bạn muốn đuôi của một LinkedList như một LinkedList, bạn sẽ phải loại bỏ phần đầu và thay đổi danh sách của bạn hoặc sao chép tất cả các phần tử đuôi vào một LinkedList mới. Vì vậy, scala của List và java LinkedList là cấu trúc rất khác nhau.

Answer 2

Bạn đã kiểm tra các lĩnh vực length?

Answer 3

Danh sách định nghĩa kích thước:

> List(1, 2, 3).size 
res4: Int = 3 

trong đó có o tuyến tính (n) thời gian thực hiện. Nếu bạn thực sự cần một thời gian không đổi, bạn nên xem xét ListBuffer có thể thay đổi để cung cấp việc triển khai kích thước thời gian không đổi.

Answer 4

Bởi vì duy trì lĩnh vực này

1. sẽ Thêm overhead bộ nhớ cho tất cả các danh sách;
2. Thêm phí thời gian trên mỗi lần tạo danh sách.

Trong Java thông thường, LinkedList được tạo và sau đó thao tác mà không tạo danh sách mới bằng cách thêm/xóa phần tử; ở Scala có rất nhiều số List được tạo.

Vì vậy, nó đã được quyết định rằng chi phí không phải là giá trị nó.

Answer 5

Tôi có thiếu gì đó không? Kích thước có ở đó:

Welcome to Scala version 2.9.1.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_29). 
Type in expressions to have them evaluated. 
Type :help for more information. 

scala> import scala.collection.immutable.List 
import scala.collection.immutable.List 

scala> val a = List(1,2,3) 
a: List[Int] = List(1, 2, 3) 

scala> a size 
res0: Int = 3 

Answer 6

"bất lợi" của độ phức tạp O (n) không lớn như bạn nghĩ. Martin Odersky đã đề cập trong một cuộc nói chuyện rằng (nếu tôi nhớ chính xác) 90% của tất cả các danh sách được tạo ra trong tất cả các chương trình bằng bất kỳ ngôn ngữ máy tính nào có kích thước từ 4 trở xuống.Do đó, thời gian truy cập O (n) cho size không phải là chi phí lớn cho hầu hết các danh sách được tạo và, như những người khác đã đề cập ở đây, tiết kiệm bộ nhớ nhiều hơn bù đắp cho điều này.