Sử dụng ngăn xếp không đổi

Question

Tôi đã nhìn thấy số post thông báo việc phát hành phiên bản ổn định của gói Microsoft.Bcl.Immutable NuGet ngay hôm nay.

Tôi tự hỏi: điều gì sẽ được sử dụng cho một ngăn xếp không thay đổi? Tôi không thể tìm thấy một ví dụ hoặc một kịch bản mà sẽ hữu ích. Có thể là sự hiểu biết của tôi về bất biến. Nếu bạn có thể làm sáng tỏ một số lý do tại sao điều này có thể hữu ích, tốt nhất là với một ví dụ cụ thể, điều này sẽ tốt đẹp.

Answer 1

Ý tưởng đằng sau thư viện bộ sưu tập này là cung cấp các bộ sưu tập, khi thay đổi tạo ra các phiên bản mới của cùng một bộ sưu tập, trong đó tất cả các phiên bản cũ của bộ sưu tập vẫn hợp lệ.

Điều này tương tự như cách hệ thống kiểm soát phiên bản hoạt động: Bạn có thể thay đổi mã và cam kết thay đổi đối với máy chủ, tạo phiên bản mới của cây nguồn. Trong thời gian chờ đợi, bạn vẫn có thể thanh toán bất kỳ bản sửa đổi trước đó nào.

Đối với bộ sưu tập không thay đổi, bạn giữ nguyên phiên bản cũ (về bản chất là ảnh chụp không thay đổi) bằng cách giữ con trỏ đến bộ sưu tập sẽ không thay đổi.

Bạn có thể cho rằng kịch bản này ít hữu ích hơn cho một ngăn xếp vì bạn có thể sử dụng ngăn xếp để thêm và truy xuất từng mục một cách chính xác, đồng thời duy trì thứ tự. Thông thường, việc sử dụng ngăn xếp được gắn rất nhiều với mã chạy trên một luồng thực thi duy nhất.

Nhưng giờ tôi đang nhập, tôi có thể nghĩ về trường hợp sử dụng cụ thể nếu bạn có trình phân tích cú pháp lười biếng cần theo dõi một số trạng thái trong ngăn xếp. Sau đó, bạn có thể lưu con trỏ vào ngăn xếp bất biến trong trạng thái trong quá trình phân tích ban đầu, mà không cần sao chép và truy xuất con trỏ khi bạn phân tích cú pháp công việc trì hoãn.

Answer 2

Hãy tưởng tượng kịch bản theo đó các yêu cầu đến trên một đường ống đơn và được lưu trữ trong ngăn xếp vì yêu cầu cuối cùng được coi là ưu tiên. Sau đó, tôi có một bộ người tiêu dùng yêu cầu luồng, mỗi người trong số đó đề cập đến một loại yêu cầu cụ thể. Mã marshalling chính xây dựng ngăn xếp, sau đó khi tất cả người tiêu dùng đã sẵn sàng, chuyển ngăn xếp đó đến người tiêu dùng và bắt đầu một ngăn xếp mới.

Nếu ngăn xếp có thể thay đổi, mỗi người tiêu dùng sẽ chạy song song và sẽ chia sẻ cùng một chồng có thể thay đổi ở bất kỳ giai đoạn nào do người tiêu dùng khác. Khóa sẽ được yêu cầu để kiểm soát các mục popping ra khỏi ngăn xếp để đảm bảo tất cả chúng đều được đồng bộ. Nếu người tiêu dùng mất một thời gian dài để hoàn thành một hành động mà ngăn xếp bị khóa, tất cả những người khác được tổ chức.

Bằng cách có ngăn xếp không thay đổi, mỗi người tiêu dùng được tự do thực hiện những gì nó muốn trong ngăn xếp mà không cần chăm sóc cho người tiêu dùng khác. Popping một mục ra khỏi ngăn xếp kết quả trong một cái mới và ban đầu là không thay đổi. Vì vậy, không có khóa là cần thiết và mỗi thread là miễn phí để chạy mà không cần chăm sóc cho những người khác.

Answer 3

Tôi yêu bộ sưu tập không thay đổi nhưng chúng thường cảm thấy như một giải pháp cần sự cố. Chúng có thể là unexpectedly slow do how they are implemented: chúng cố gắng hết sức để sử dụng bộ nhớ hiệu quả với chi phí làm cho các vòng lặp và lập chỉ mục phức tạp hơn về mặt thuật toán một cách phức tạp hơn. Với trí nhớ phong phú như thế nào, nó có thể khó để biện minh cho chi phí đó. Có rất nhiều thông tin được tìm thấy trên web về việc sử dụng thành công các bộ sưu tập không thể thay đổi (trừ ImmutableArray<T>). Trong một nỗ lực để khắc phục điều đó, tôi nghĩ rằng tôi muốn thêm một câu trả lời cho câu hỏi 3 năm tuổi này về một trường hợp mà tôi thấy ImmutableStack<T> là thực sự hữu ích.

xem xét cây giống như cấu trúc này rất cơ bản:

public class TreeNode 
{ 
    public TreeNode Parent { get; private set; } 
    public List<TreeNode> ChildNodes { get; set; } 

    public TreeNode(TreeNode parent) 
    { 
     Parent = parent; 
    } 
} 

tôi đã tạo ra các lớp học theo mô hình cơ bản này với nhiều người, nhiều lần, và trong thực tế, nó luôn luôn làm việc cho tôi. Gần đây, tôi đã bắt đầu làm điều gì đó như thế này:

public class TreeNode 
{ 
    public ImmutableStack<TreeNode> NodeStack { get; private set; } 
    public ImmutableStack<TreeNode> ParentStack { get { return NodeStack.IsEmpty ? ImmutableStack<TreeNode>.Empty : NodeStack.Pop(); } } 
    public TreeNode Parent { get { return ParentStack.IsEmpty ? null : ParentStack.Peek(); } } 

    public ImmutableArray<TreeNode> ChildNodes { get; set; } 

    public TreeNode(TreeNode parent) 
    { 
     if (parent == null) 
      NodeStack = ImmutableStack<TreeNode>.Empty; 
     else 
      NodeStack = parent.NodeStack.Push(this); 
    } 
} 

Đối với nhiều lý do, tôi đã đến để thích lưu trữ một ImmutableStack<T> của TreeNode trường hợp mà tôi có thể đi qua vào thư mục gốc chứ không phải chỉ đơn giản là một tài liệu tham khảo với phiên bản Parent.

• ImmutableStack<T> 'về triển khai cơ bản là danh sách được liên kết. Mỗi thể hiện của ImmutableStack<T> thực sự là một nút trên danh sách được liên kết. Đó là lý do tại sao tài sản ParentStack chỉ là Pop 's NodeStack. ParentStack sẽ trả về cùng một thể hiện của ImmutableStack<T> là Parent.NodeStack.
• Nếu bạn lưu trữ tham chiếu đến ParentTreeNode, sẽ dễ dàng tạo vòng lặp có thể gây ra các hoạt động như tìm nút gốc để không bao giờ chấm dứt và bạn sẽ bị tràn ngăn xếp hoặc vòng lặp vô hạn. An ImmutableStack<T>, mặt khác, có thể được tăng lên bởi Pop -ing, đảm bảo rằng nó sẽ chấm dứt.
  • Thực tế là bạn sử dụng một bộ sưu tập (ImmutableStack<T>) có nghĩa là bạn có thể ngăn chặn vòng tròn xảy ra ở nơi đầu tiên bằng cách đơn giản để đảm bảo các parentTreeNode không xảy ra hai lần khi xây dựng TreeNode.

Đó chỉ là bắt đầu. Tôi nghĩ rằng các ImmutableStack<T> làm cho hoạt động cây đơn giản và an toàn hơn. Bạn có thể (an toàn) sử dụng LINQ trên đó. Bạn có muốn biết liệu một người TreeNode có phải là hậu duệ của người khác không? Bạn chỉ có thể làm ParentStack.Any(node => node == otherNode)

Tổng quát hơn, lớp ImmutableStack<T> là dành cho bất kỳ trường hợp bạn muốn một Stack<T> mà bạn có thể đảm bảo sẽ không bao giờ được sửa đổi, hoặc bạn cần một cách dễ dàng để có được một "bản chụp" của một Stack<T> nhưng không muốn tạo ra một loạt các bản sao của ngăn xếp đó. Nếu bạn có một loạt các bước lồng nhau, bạn có thể sử dụng một số ImmutableStack<T> để theo dõi tiến trình và vì vậy khi bước hoàn tất, nó có thể chuyển công việc sang bước cha mẹ của nó. Tính chất bất biến của nó đặc biệt hữu ích khi bạn đang cố gắng làm việc song song.