7

我的目标是创建一个数据结构实现接口，该接口将通过牺牲内存IList<T>来实现元素查找时间。O(1)

背景 如您所知，所有基于数组的IList<T>实现List<T>都具有O(n)元素查找时间。这意味着操作喜欢int IndexOf(T element)或bool Contains(T element)遍历底层数组，直到找到匹配项。

众所周知的想法是使用列表和哈希表的组合作为底层数据结构。值保存在列表中。哈希表将索引作为值和列表的值作为键。因此可以使用哈希表进行查找。

这正是KeyedCollection<TKey, TItem> see MSDN的实现方式。

到目前为止我尝试过的

internal class MyList<T> : KeyedCollection<T, T>
{
    protected override T GetKeyForItem(T item)
    {
        return item;
    }
}

到目前为止，除了一个问题外，这一直有效。这种数据结构并没有完全模仿背后预期的行为List<T>。关键是List<T>允许重复，MyList不允许。

问题

是否有任何现成的数据结构，或者您可以推荐一种优雅的实现方式，IList<T>以便：

  1. 查找操作有O(1)时间。
  2. 所有其他操作具有相同O()的性能List<T>
  3. 内存可能会受到哈希表开销（constantA + constantB * n字节）的影响。
  4. 必须允许重复
  5. 允许空值是可选的（可以将它们装箱到空对象中）
4

4 回答 4

4

我能看到这一点的唯一方法是使用列表字典。点击该键将为您提供创建该特定键的所有重复项的列表。总是拿第一个。

于 2012-11-29T18:22:41.973 回答
2

在Ryan Bennett提出的建议的基础上，我认为最好的办法（因为您声明顺序很重要）是创建一个实现 IList 的类，然后在内部有这样的东西：

class MyList<T> : IList<T>
{
    Dictionary<T, List<int>> _indexMap;
    List<T> _items;


    public int IndexOf(T item)
    {
        List<int> indices;
        if(_indexMap.TryGetValue(item, out indices))
        {
            return indices[0];
        }
        return -1;
    }

    public void Add(T item)
    {
        List<int> indices;
        if(!_indexMap.TryGetValue(item, out indices))
        {
            indices = new List<int>();
            _indexMap[item] = indices;
        }

        indices.Add(_items.Count);
        _items.Add(item);
    }

    // Attempt at a Remove implementation, this could probably be improved
    // but here is my first crack at it
    public bool Remove(T item)
    {
        List<int> indices;
        if(!_indexMap.TryGetValue(item, out indices))
        {
            // Not found so can just return false
            return false;
        }

        int index = indices[0];
        indices.RemoveAt(0);
        if (indices.Count == 0)
        {
            _indexMap.Remove(item);
        }

        for(int i=index+1; i < _items.Count; ++i)
        {
            List<int> otherIndexList = _indexMap[_items[i]];
            for(int j=0; j < otherIndexList.Count; ++j)
            {
                int temp = otherIndexList[j];
                if (temp > index)
                {
                    otherIndexList[j] = --temp;
                }
            }
        }

        return _items.RemoveAt(index);
    }

    // ... Other similar type functions here
}

编辑：

刚刚意识到，当您执行Remove. 您将不得不遍历索引集合并使用值 > 您删除的项目的索引来更新任何索引。您现在已经增加了“删除”时间。你也让正确变得很棘手。如果你要尝试实现这样的东西，我会围绕这个集合进行大量的单元测试。

我知道你说顺序很重要，所以我假设这就是为什么你不使用允许重复并给你 O(log n) 操作时间的排序列表方法。

编辑2：另一种簿记类型方法
我只是在脑海中弹跳这个，所以我只会给出一些粗略的伪代码，但您可能会采取一种方法，您只需将项目字典映射到索引列表和第二个字典，将索引映射到项目。如果您添加 T 是一个类的限制，那么您只需支付两次存储参考的开销。然后，您需要维护当前的“最后一个”，以便您可以轻松地将新项目添加到集合中。这应该使删除操作更干净一些。它仍然是 O(n)，因为您必须使用索引 > 已删除项目来更新任何内容。在最初的想象中，这似乎是一个潜在的解决方案，可以让您接近您想要实现的目标（如果我正确理解目标）。

于 2012-11-29T18:38:19.487 回答
1

哈希表应该包含每个键的索引列表。我认为这就是你所需要的，不是吗？

于 2012-11-29T18:25:15.153 回答
0

如果您可以开发一个搜索时间为 O(1) 的结构，您会发现自己变得非常富有：p

基本上这种类型的结构是不存在的，最接近这个的是哈希表

C# 有一个内置的哈希表类型 - C~ Hash Table

于 2012-11-29T18:23:43.443 回答