liên tục và cấu trúc dữ liệu không thay đổi

Question

Có bất kỳ sự khác biệt nào trong cấu trúc dữ liệu liên tục và không thay đổi được không? Wikipedia đề cập đến cấu trúc dữ liệu bất biến khi thảo luận về sự bền bỉ nhưng tôi có cảm giác có thể có sự khác biệt tinh tế giữa hai yếu tố này.

Answer 1

Tính không thay đổi là kỹ thuật triển khai. Trong số những thứ khác, nó cung cấp kiên trì, là một giao diện. API kiên trì là một cái gì đó như:

• version update(operation o, version v) Thực hiện hoạt động trên phiên bản ov, trả lại một phiên bản mới. Nếu cấu trúc dữ liệu là không thay đổi, phiên bản mới là cấu trúc mới (có thể chia sẻ các phần không thể thay đổi của cấu trúc cũ). Nếu cấu trúc dữ liệu không thay đổi, phiên bản trả lại có thể chỉ là một số phiên bản. Phiên bản v vẫn là phiên bản hợp lệ và phiên bản này không được thay đổi theo bất kỳ cách nào observe do cập nhật này - bản cập nhật chỉ hiển thị trong phiên bản trả về chứ không phải trong v.
• data observe(query q, version v) quan sát cấu trúc dữ liệu ở phiên bản v mà không thay đổi hoặc tạo phiên bản mới.

Để biết thêm về những khác biệt này, xem:

• The chapter "Persistent data structures" by Haim Kaplan in Handbook on Data Structures and Applications
• "Making Data Structures Persistent" by Driscoll et al.
• The first lecture of the Spring 2012 incarnation of MIT's 6.851: Advanced Data Structures

Answer 2

Có, có sự khác biệt. Một cấu trúc dữ liệu bất biến không thể được sửa đổi trong bất kỳ cách nào sau khi tạo ra nó. Cách duy nhất để sửa đổi hiệu quả nó sẽ là tạo một bản sao có thể thay đổi hoặc một cái gì đó tương tự (ví dụ: sửa đổi một chút các tham số mà bạn truyền cho hàm tạo của cái mới). Một cấu trúc dữ liệu liên tục, mặt khác, có thể thay đổi theo nghĩa là API tiếp xúc xuất hiện để cho phép thay đổi cấu trúc dữ liệu. Tuy nhiên, trong thực tế, mọi thay đổi sẽ giữ lại một con trỏ tới cấu trúc dữ liệu hiện có (và do đó mọi cấu trúc trước đó); chúng dường như chỉ làm thay đổi cấu trúc dữ liệu vì API được trả về trả về một con trỏ mới có thể bao gồm con trỏ tới một tập hợp con của cấu trúc dữ liệu trước đó (trong cây, ví dụ, chúng ta sẽ trỏ vào nút có subtree không thay đổi do hoạt động).