Data.Sequence.Seq nhanh như thế nào so với []?

Question

Xóa rõ ràng Seq thực hiện tương tự hoặc tốt hơn như [] cho tất cả các hoạt động có thể có. Nhưng vì cấu trúc của nó phức tạp hơn các danh sách, với kích thước nhỏ, chi phí không đổi của nó có thể sẽ làm cho nó chậm hơn. Tôi muốn biết số tiền, cụ thể:

1. Bao nhiêu chậm hơn là <| so với :?
2. Tốc độ chậm hơn gấp/vượt qua số Seq so với xếp chồng/di chuyển ngang số [] (không bao gồm chi phí của chức năng gấp/vượt qua)?
3. Kích thước (xấp xỉ) là gì \xs x -> xs ++ [x] trở nên chậm hơn |>?
4. Kích thước (xấp xỉ) mà ++ trở nên chậm hơn >< là bao nhiêu?
5. Chi phí gọi viewl và khớp mẫu trên kết quả so với kết hợp mẫu trên danh sách là gì?
6. Bộ nhớ có bao nhiêu bộ nhớ n -element Seq chiếm so với danh sách liên kết n? (Không tính bộ nhớ bị chiếm đóng bởi các phần tử, chỉ cấu trúc.)

Tôi biết rằng khó đo lường, vì Seq chúng tôi nói về sự phức tạp phân bổ, nhưng tôi muốn biết ít nhất một số thô .

Answer 1

này nên được một sự khởi đầu - http://www.haskell.org/haskellwiki/Performance#Data.Sequence_vs._lists

Một chuỗi sử dụng giữa 5/6 và 4/3 lần so với không gian nhiều như danh sách tương đương (giả định một overhead của một từ mỗi nút, như trong GHC). Nếu chỉ sử dụng các hoạt động deque, việc sử dụng không gian sẽ gần cuối dưới của phạm vi, bởi vì tất cả các nút bên trong sẽ là số ba. Việc sử dụng phân tách và nối thêm nhiều sẽ dẫn đến các chuỗi sử dụng khoảng không gian tương tự như danh sách. Cụ thể:

• danh sách độ dài n bao gồm n nút điều khiển, mỗi nút chiếm 3 từ.
• một chuỗi độ dài n có khoảng n/(k-1) nút, trong đó k là độ trung bình của các nút bên trong (mỗi 2 hoặc 3). Có một con trỏ, kích thước và chi phí cho mỗi nút, cộng với một con trỏ cho mỗi phần tử, tức là n (3/(k-1) + 1) từ.

Danh sách là yếu tố không liên tục nhỏ hơn cho hoạt động ở đầu (khuyết điểm và đầu), làm cho nó trở thành lựa chọn hiệu quả hơn cho các mẫu truy cập giống như ngăn xếp và giống như luồng. Data.Sequence là nhanh hơn cho mỗi mẫu truy cập khác, chẳng hạn như hàng đợi và truy cập ngẫu nhiên.

Answer 2

Tôi có thêm một kết quả cụ thể để thêm vào câu trả lời ở trên. Tôi đang giải một phương trình Langevin. Tôi đã sử dụng List và Data.Sequence. Rất nhiều chèn ở phía sau của danh sách/chuỗi đang diễn ra trong giải pháp này.

Tóm lại, tôi không thấy bất kỳ cải thiện nào về tốc độ, trên thực tế hiệu suất bị giảm xuống theo Trình tự. Hơn nữa với Data.Sequence, tôi cần phải tăng bộ nhớ có sẵn cho Haskell RTS.

Vì tôi chắc chắn không phải là cơ quan về tối ưu hóa; Tôi đăng cả hai trường hợp dưới đây. Tôi rất vui khi biết liệu điều này có thể được cải thiện hay không. Cả hai mã đều được biên dịch với cờ -O2.

1. Solution with List, mất khoảng 13,01 giây
2. Solution with Data.Sequence, mất khoảng 15,13 giây