0

我有一个包含很多（数百万）对象的容器，并且必须为每个项目维护一个经过验证的状态，例如：

class MyContainer<T>
{
    bool IsValidated(T t);
}

一个项目是否被验证完全是一个容器的概念。物品没有这样的概念。那么这种情况下如何实现item的Validated状态呢？我将用我想到的两种解决方案来解释这个问题：

解决方案 1）通过强制添加到集合中的项目从基类继承来为项目本身添加一个 Validated 属性：

class MyContainer<T> where T : BaseItem
{
    bool IsValidated(T t)
    {
        return t.IsValidated;
    }
}

class BaseItem
{
    bool IsValidated;
}

但这似乎是错误的。一个项目是否被验证是容器的关注点。该项目不应该对“已验证”的含义有任何概念。但另一方面，这是我能想到的唯一解决方案，给定一个项目，允许在 O(1) 中查找其验证状态。

解决方案 2）在容器中维护一个字典以将 Items 与验证状态相关联：

class MyContainer<T>
{
    Dictionary<T, bool> isValidated;

    bool IsValidated(T t)
    {
        return isValidated[t];
    }
}

这解决了第一个解决方案的“错误”。它从 Item 中删除了所有关于验证的知识，并且也不需要 item 继承基类。但不利的一面是，确定项目验证状态的查找现在是 O(log n)。

我无法克服的是设计方面最差的解决方案（＃1）如何在查找性能方面更好。除了解决方案#1 的糟糕设计会产生 O(1) 查找之外，我什么都想不到。

是否有设计良好的 O(1) 解决方案，或者我应该只解决 O(log n) 查找？

4

1 回答 1

1

正如 Dave 所写，字典的复杂性接近 O(1)

使用其键检索值非常快，接近 O(1)，因为 Dictionary 类是作为哈希表实现的。

http://msdn.microsoft.com/en-us/library/xfhwa508.aspx

于 2013-05-17T14:06:14.663 回答