Đây là một câu hỏi phức tạp đáng ngạc nhiên, vì hai tính năng của Haskell và GHC:
- đánh giá Lazy
- Danh sách fusion
Danh sách tổng hợp có nghĩa là trong một số trường hợp, GHC có thể viết lại mã xử lý danh sách vào một vòng lặp không phân bổ các ô danh sách. Vì vậy, tùy thuộc vào ngữ cảnh mà nó được sử dụng, cùng một mã có thể không phải trả thêm chi phí.
Đánh giá lười biếng có nghĩa là nếu kết quả của một thao tác không được tiêu thụ, thì bạn không phải trả chi phí tính toán nó. Vì vậy, ví dụ, đây là giá rẻ, bởi vì bạn chỉ phải xây dựng mười yếu tố đầu tiên của danh sách:
example = take 10 ([1..1000000] ++ [1000001])
Trong thực tế, trong mã rằng take 10 có thể kết hợp được với danh sách append, do đó, nó giống như chỉ [1..10].
Nhưng hãy giả sử rằng chúng tôi đang tiêu thụ tất cả các thành phần của tất cả các danh sách mà chúng tôi thực hiện và trình biên dịch không kết hợp hoạt động danh sách của chúng tôi. Bây giờ cho câu hỏi của bạn:
Nếu tôi thêm phần tử vào Danh sách trong Haskell, Haskell trả về danh sách mới (đầy đủ?) Và không thao tác bản gốc. Bây giờ chúng ta hãy nói rằng tôi có một danh sách của một triệu yếu tố và tôi nối thêm một phần tử ở cuối. Haskell có "sao chép" toàn bộ danh sách (1 triệu phần tử) và thêm phần tử vào bản sao đó không? Hoặc là có một "thủ thuật" gọn gàng đang diễn ra đằng sau hậu trường để tránh sao chép toàn bộ danh sách?
Có các thủ thuật để tránh sao chép toàn bộ danh sách, nhưng bằng cách nối vào cuối danh sách, bạn sẽ đánh bại chúng. Điều cần hiểu là các cấu trúc dữ liệu chức năng thường được thiết kế sao cho các hoạt động "sửa đổi" chúng sẽ khai thác chia sẻ cấu trúc để tái sử dụng càng nhiều cấu trúc cũ càng tốt. Vì vậy, ví dụ, phụ thêm hai danh sách có thể được định nghĩa như thế này:
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : xs ++ ys
Nhìn vào định nghĩa này, bạn có thể nói rằng danh sách ys sẽ được tái sử dụng trong kết quả. Vì vậy, nếu chúng ta có xs = [1..3], ys = [4..5] và xs ++ ys, tất cả các đánh giá đầy đủ và giữ lại trong bộ nhớ cùng một lúc, nó sẽ trông giống như bộ nhớ khôn ngoan này:
+---+---+ +---+---+ +---+---+
xs = | 1 | -----> | 2 | -----> | 3 | -----> []
+---+---+ +---+---+ +---+---+
+---+---+ +---+---+
ys = | 4 | -----> | 5 | -----> []
+---+---+ +---+---+
^
|
+------------------------------------+
|
+---+---+ +---+---+ +---+---+ |
xs ++ ys = | 1 | -----> | 2 | -----> | 3 | -------+
+---+---+ +---+---+ +---+---+
Đó là chặng đường dài để nói điều này: nếu bạn làm xs ++ ys , và nó không hợp nhất, và bạn tiêu thụ toàn bộ danh sách, sau đó sẽ tạo ra một bản sao của xs nhưng tái sử dụng bộ nhớ cho ys.
Nhưng bây giờ chúng ta hãy nhìn lại chút này của câu hỏi của bạn:
Bây giờ chúng ta hãy nói rằng tôi có một danh sách của một triệu yếu tố và tôi thêm một yếu tố ở cuối. Haskell có "sao chép" toàn bộ danh sách (1 triệu phần tử) và thêm phần tử vào bản sao đó không?
Điều đó sẽ giống như [1..1000000] ++ [1000001] và có, nó sẽ sao chép cả triệu yếu tố. Nhưng mặt khác, [0] ++ [1..1000000] sẽ chỉ sao chép [0]. Quy tắc chung là:
- Thêm phần tử ở đầu danh sách hiệu quả nhất.
- Việc thêm các phần tử vào cuối danh sách thường không hiệu quả, đặc biệt nếu bạn lặp đi lặp lại.
Các giải pháp chung để phân loại này của vấn đề là:
- Sửa đổi thuật toán của bạn để bạn sử dụng danh sách theo mô hình truy cập chúng hỗ trợ một cách hiệu quả.
- Không sử dụng danh sách; sử dụng một số cấu trúc dữ liệu chuỗi khác có hiệu quả hỗ trợ mẫu truy cập bạn cần cho sự cố trong tầm tay. Một câu trả lời nêu danh sách khác biệt, nhưng những người khác đáng nói là:
Tôi đồng ý với những gì bạn nói nhưng Big O ký hiệu của bạn là không đúng. O (500000500000) == O (1) == thời gian không đổi (xem http://en.wikipedia.org/wiki/Big_O_notation#Multiplication_by_a_constant). Chắc chắn, bạn có thể tranh luận rằng nếu bạn cố gắng "nối thêm một triệu phần tử" thì nó luôn chạy trong O (1) vì không có biến nào còn lại và thao tác "nối thêm một triệu lần" thực sự chạy trong thời gian không đổi. Nhưng tôi không nghĩ đó là điều bạn muốn nói. –
@ JohannesWeiß Tốt hơn? – bheklilr
Vâng, @bheklilr, cảm ơn :) –