BitArray 索引列表

• 下载源代码 - 12.2 KB

引言

在我所从事的应用中，我们需要将订单合并并装上卡车：这是一个典型的卡车调度问题。 为了我想要展示的这个专门的 List 类，此问题的特点如下：

• 项目数量有限（订单、卡车、仓库）
• 有很多小列表，你想检查它们是否包含相同的项目

几个列表操作的速度至关重要。 因此，该 List 具有超快的

• Contains
• Intersect
• Union
• 重叠检查

我搜索了维基和文章，以找到这种集合的良好描述。 它可能被称为 BitArray，或者带有 BitArray 索引的 List。 这个想法可能不是独一无二的，但据我所知，.NET 中的实现是独一无二的。

背景

在我们的例子中，我们有三个固定的列表：订单、卡车、仓库。 对于每个订单，我们创建其他可以与之合并的订单的列表，可以装载的卡车列表，以及拥有所需产品的仓库列表。

在所有调度过程中，我们必须不断比较列表。 例如，如果两个订单在它们的卡车列表中没有共享卡车，则它们不能合并。 如果我们合并两个订单，它们可以调度的卡车是两个订单的卡车列表的交集。

Using the Code

代码由列表中的项目必须实现的一个简单接口，以及 List 类本身组成。

要使用 List，您必须确保要放入其中的项目实现 IIndexable 接口。 此外，每个项目都必须为其 Index 拥有一个唯一值。

一个最小的例子，展示了先决条件和主要方法

Public Class Order
    Implements IIndexable
    Private _Index As Short

    Public Property Index() As Short Implements IIndexable.Index
        Get
            Return Me._Index
        End Get
        Set(ByVal value As Short)
            Me._Index = value
        End Set
    End Property
End Class

Public Class OrderManager
    Private Orders As New List(Of Order)
    Public Sub InitOrders()
        Dim NewOrder As Order
        For Index As Integer = 0 To 10
            NewOrder = New Order
            NewOrder.Index = Index
            Me.Orders.Add(NewOrder)
        Next
    End Sub
    Public Sub UseOrders()
        Dim OrderList1 As New IndexedList(Of Order)
        Dim OrderList2 As New IndexedList(Of Order)
        OrderList1.Add(Me.Orders(0))
        OrderList1.Add(Me.Orders(1))
        If OrderList1.Contains(Me.Orders(0)) Then
            OrderList2.Add(Me.Orders(0))
            OrderList2.Add(Me.Orders(2))
        End If
        OrderList1.UnionWith(OrderList2) 'Order 2 will be added to OrderList1
        OrderList1.IntersectWith(OrderList2) 'OrderList1 will contain order 0 and 2 now
    End Sub
End Class

我用 VB.NET 编写了所有内容，但可以使用在线工具将所有代码翻译成 C#。

关注点

我自己也学到了一些东西：要打开无符号整数中的特定位，可以使用按位移位和按位或。 这比我之前使用的“2 的 x 次方”快得多。 类中的测试是基于我在 CP 上学到的一个想法。 为了使其工作，您必须在 vbproj 中添加一个 ProjectTypeGuids 标签，使用文本编辑器。

历史

• 2012 年 2 月 29 日：初始版本。