多字段索引列表

• 下载源代码 - 12.37 KB

引言

当您编写类似游戏引擎的东西时，通常会有许多类，这些类必须组织为某些数据的容器。例如，您可能需要存储您的计时器、纹理、声音等等。

这些内容类可以具有必须在游戏循环中尽可能快地找到的附加信息。当您的数据量很小时，将数据存储在 List<T> 容器中不是什么大问题，但是如果一个容器中有超过 10000 个对象，那可能就是一个问题。在未排序列表上进行串行搜索太慢了。

在 C# 工具包中有非泛型 SortedList 或泛型 SortedDictionary 集合，但它们一次只能按一个字段排序，并且字典语法对于您的大多数类来说不是最佳选择。

我尝试使用一个泛型类来解决这个问题，该泛型类包含针对内容类的任何公共属性动态排序和同步的列表。

背景

这个想法来自于我思考它在数据库中是如何工作的。据我所知，您添加到数据库的任何索引都会成为该字段（多字段索引的字段）的排序列表。然后，您可以在这些字段上使用快速搜索算法。

所以，我尝试在 C# 世界中实现这个想法 ;)。

您可以根据需要添加任意数量的索引，以及您自己的别名、排序顺序和唯一标志。

更重要的是 - 如果您需要同时拥有升序和降序，则可以为同一属性添加两个具有不同别名的索引。

我使用的是快速二分查找算法，它有一个限制 - 仅在使用具有 unique 标志=true 的字段的 BinarySearch() 方法时才是正确的。 这是因为我的类在同时搜索多个字段时未被接受 :( (类似于 SQL 中的 "Select" 命令)。

所有索引器都按相应的属性、对内容类实例的引用列表进行排序，因此您可以将它们用于复杂的搜索（函数 GetIndexer(string alias)）。

唯一标志用于自动添加仅具有目标属性唯一值的实例（用于指定键字段）。

使用代码

按属性 ID 索引的类 T。这是 IndexedList<T> 类的一部分。 支持排序顺序和唯一键保护。

public class ListIndex<T>
{
    private string id;
    // Name of the indexer
    public string ID
    {
      get { return id; }
    }

    private bool unique;
    // True if all values of indexed field must be unique
    public bool Unique
    {
      get { return unique; }
    }
    
    private int direction;
    // Direction of indexing. 1 - ascending, -1 - descending
    public int Direction
    {
      get { return direction; }
    }

    private string alias;
    // Alias for indexer. Is equivalent to ID if not specified in constructor
    public string Alias
    {
      get { return alias; }
    }

    private List<T> list;
    // Container for sorted data
    public List<T> List
    {
      get { return list; }
    }

    // Default constructor for preorder sorting with not unique fields
    public ListIndex(string id)
      : this(id,id,false,false)
    {
    }

    // Constructor with possibility to select indexer alias, type of order
    // and unique flag
    public ListIndex(string id,string alias,bool backDirection,bool unique)
    {
    }

    // Disposing of indexer
    public void Dispose()
    {
    }

    ~ListIndex()
    {
      Dispose();
    }
}

用于类 T 的索引列表的主要类容器。

public class IndexedList<T> where T:class
{
    private List<T> list;
    // Unsorted list for situations when no one indexes present 
    // (or for geting elements in the add order)
    public List<T> List
    {
      get { return list; }
    }

    // default binding flag for supported type of fields wich can be indexed
    BindingFlags bindingAttr=BindingFlags.Public | BindingFlags.Instance;

    // default constructor for creating empty list with no indexes
    public IndexedList()
    {
    }

    // Get indexer by alias indexAlias.
    // Useful for series of searching or for direct access to sorted list
    public ListIndex<T> GetIndexer(string indexAlias)
    {
    }

    // Fast searching for object with value T.v
    // in the indexer with alias indexAlias
    public T BinarySearch(string indexAlias,object v)
    {
      return BinarySearch(GetIndexer(indexAlias),v);
    }

    // Fast searching for object with value T.v in the indexer index
    public T BinarySearch(ListIndex<T> index,object v)
    {
    }

    // Looking for the position of the value T.v in the indexer index
    // (base function for searching and inserting)
    public int Search4index(ListIndex<T> index,object v,bool inserting)
    {
    }

    // Add new object obj to collection
    public bool Add(T obj)
    {
    }

    // Delete object obj from collection.
    // Delete without fast search because it is safe for not unique fields
    public void Delete(T obj)
    {
    }

    // Delete object by indexer id indexID and value of indexed field fieldValue
    // It is possible to use only for unique indexers
    public void Delete(string indexID,object fieldValue)
    {
      Delete(GetIndexer(indexID),fieldValue);
    }

    // Delete object by indexer index and value of indexed field fieldValue
    // It is possible to use only for unique indexers
    public bool Delete(ListIndex<T> index,object fieldValue)
    {
    }

    // Add default (preorder, not unique) indexer by field T.id if present
    public bool AddIndex(string id)
    {
      return AddIndex(id,id,false,false);
    }

    // Add indexer by field T.id if present,
    // with specific order and unique or not flag
    // Fail if find same fields in unique indexer
    public bool AddIndex(string id,string alias,bool backDirection,bool unique)
    {
    }

    // Delete indexer with by alias name
    public void DelIndex(string alias)
    {
    }

    // Clear collection and free resourses
    public void Dispose()
    {
    }

    ~IndexedList()
    {
      Dispose();
    }
}

关注点

构建这样一个可以在许多不同情况下使用的通用类很有意思。

代码

附件中有一个示例，展示了如何

1. 添加/删除索引
2. 添加一些数据
3. 获取索引器
4. 使用二分查找

性能测试

由于使用了反射机制，这种实现并不是很快。 但无论如何，它比在 10000 个对象的列表上进行串行搜索快 3-4 倍，并且在 100,000 个对象的列表中进行搜索时快 20 多倍。