tại sao Data.Sequence.reverse O (n)?

Question

Các tài liệu nói Data.Sequence.reverse là O (n). Không thể một loại chuỗi hữu hạn được "đảo ngược" bằng cách đặt cờ? (Có hiệu quả, mà dấu chấm hết cho "bắt đầu đếm" từ.)

Answer 1

Nếu bạn chỉ có một cờ, bạn sẽ gặp sự cố. Giả sử tôi muốn

xs <> reverse xs 

Tôi có thể tính toán điều đó như thế nào? Chỉ với một lá cờ, tôi phải thực hiện một sự đảo ngược đắt tiền trước khi phụ thêm. Để thực sự thực hiện điều này ngay, bạn cần thêm cờ, trải rộng trên cây. Tất cả xung quanh cây. Mỗi nút trong cây cần mang thông tin đảo ngược. Điều này là chắc chắn có thể, nhưng nó hơi đắt tiền. Thậm chí tệ hơn, mọi bước của mọi hoạt động đều phải quản lý các cờ đảo ngược một cách thích hợp, đó là một chút ác mộng đối với bất cứ ai phải viết và duy trì mã. Ý tưởng này đã được thực hiện trong một bài báo ở đâu đó (tôi không nhớ cái nào) nhưng nó không có niềm vui trong thực tế.

Nếu bạn có thuật toán dựa vào việc đảo ngược, bạn nên sử dụng loại trình tự tùy chỉnh có nhiều cờ và chỉ bao gồm các thao tác bạn cần (nếu bạn đặt loại của mình trên Data.Sequence, có lẽ bạn nên ăn cắp một chút từ mỗi trường kích thước). Nhưng tôi không nghĩ rằng các thuật toán như vậy là rất phổ biến.

Answer 2

Vâng, bạn có thể định nghĩa

data S a = S { forward :: Seq a , backward :: Seq a } 

và sau đó thực hiện tất cả các hoạt động với bất biến mà

forall a :: Type, s :: S a : reverse (forward s) == backward s . 

này tăng gấp đôi chi phí của mỗi nhưng cung cấp thời gian không đổi reverse.

Answer 3

Có, có thể.

Tuy nhiên, điều này cho biết thêm một mức giá nhỏ cho mỗi lần tra cứu (trước hết phải kiểm tra cờ!) Và khoản hoàn trả chỉ đến với người dùng sử dụng reverse rất nhiều. Nhóm thứ hai này có lẽ được đánh giá là nhỏ. Vì việc ném cờ thích hợp lên loại có thể được thực hiện phía máy khách, nên có nghĩa là không phải là để trả giá này trong thư viện cho mỗi lần sử dụng mọi chức năng. Thay vào đó, lập trình viên có ý định gọi reverse rất nhiều buộc phải thực hiện lựa chọn cân bằng hiệu suất này nếu họ muốn, điều đó có vẻ hoàn toàn hợp lý với tôi.

Answer 4

Tôi nghĩ rằng có thể được thực hiện trong O(1) nếu kết nối >< chấp nhận nối xs >< reversed ys mà không bị phạt (một số yêu cầu hack vào cấu trúc cây ngón tay).

Nhìn để Data.Sequence mọi hoạt động có một đối tác ngược lại (ví dụ takeWhileL ~ takeWhileR.) Hoặc mất O(n) (hoặc tồi tệ nhất;. Ví dụ zip mất O(min(n1,n2)) sau đó, đảo ngược seq1 khi n1<n2 và như vậy) trừ >< hoạt động.

Trong mọi trường hợp, xs >< ys sẽ mất O(min(|xs|,|ys|)) là trường hợp xấu nhất (hai trong bốn trường hợp có thể). Đây là trong thực tế tốt hơn một chút so với O(n) (bình thường hóa theo một hướng duy nhất và đảo ngược bao giờ là cần thiết).

Sau đó, câu hỏi là:

có thể được thực hiện tốt hơn so với xs >< reversed ysO(min(|xs|,|ys|))?

(lý tưởng O(log(min(|xs|,|ys|))))

Tất nhiên, nếu bạn không sử dụng >< hoạt động, hoạt động ngược lại mất O(1) (ví dụ. Sử dụng một lá cờ để kiểm tra khi sử dụng trái hoặc đối tác bên phải).

Mặt khác, nếu hiệu suất chuỗi đảo ngược được ghép nối là rất quan trọng, có thể tồn tại một số cấu trúc tối ưu khác hoặc bạn có thể cân nhắc sử dụng @d8d0d65b3f7cf42 strategy.