3

我有一个对象列表（实际上是一个 ObservableCollection）（在我创建的类中定义的类型对象），每个对象都有自己的对象列表。这是一个档案列表，每个档案都有一个文件列表。

设置存档的“启用”属性时，我需要检查是否还没有另一个启用的具有相同文件的存档。如果是这样，我需要做一些事情。

因此，如果我有（例如）1000 个档案并启用了档案，我必须搜索每个档案的文件列表（= 1000 个档案列表中的每个文件列表）以搜索匹配项。

  1. 这是一个糟糕的实施吗？制作一个包含启用的档案文件的额外列表会更好吗？或者也许是另一种更好的方法？

  2. 在归档类中定义列表并将其设为静态是一个好主意，还是我应该在使用列表的类中定义它（总是只有一个档案列表）

谢谢（新手在这里尝试通过实践来学习）

4

2 回答 2

1

这是一个糟糕的实施吗？

是的，因为O(N+M)搜索查询相当慢，时间复杂。

在存档类中定义列表是否是个好主意...

我有一个更好的建议来使用额外的索引。

步骤1

找出两个文件何时相同，例如：

  • 名称匹配
  • 名称和其他属性匹配
  • 数字签名匹配
  • （一些）内容匹配

第2步

给定第 1 步中的匹配指标，您可以构建在第 3 步中搜索的索引

步骤 2.1

制作快速索引是一件困难的事情。fastes 索引将在O(1)时间复杂度下工作，这意味着如果您查询它，它将以恒定时间返回您的结果，与档案和文件的数量无关。我会首先要求这种性能。如果无法做到这一点，我会按排序顺序存储指标，这样您就可以在binary search其上运行一个该死的快速O(logN)时间复杂度。

所以让我们尝试在 O(1) 中实现它。假设指标与文件名匹配（不重要，纯粹是为了简单）。字典数据结构将允许您：

  1. 检查是否有任何文件“已知”在任何档案中
  2. 检索存档名称列表，该文件在其中找到
----------------------------------
钥匙 | 价值
----------------------------------
Foo.txt | 档案 1、档案 43
吧.txt | 存档2

注意：您必须保持索引的一致性，因此在对存档内容进行更改时更新索引。这可能会变得棘手！

第 3 步

现在是时候查询您的索引了！鉴于您遵循了第 1 步和第 2 步，这很简单，只需向字典询问指标，即可获得结果。如果只有一个条目，那就是您的存档，如果有多个，那么您知道哪个存档存储了相同的文件。

于 2013-10-23T17:07:03.173 回答
1

除了你的ObservableCollection<Archive>，我可能还包括一个HashSet<File>s。（File需要正确实施GetHashCode和Equals）这将让您快速查看文件是否已存在于任何其他存档中。

IList<Archive> archives = new ObservableCollection<Archive>();
ISet<File> files = new HashSet<File>();

void OnArchiveEnabled(Archive archive)
{
    foreach (var file in archive.Files)
    {
        if (!files.Add(file))
        {
            //file already exists, do some stuff
        }
    }
}

我省略了如何OnArchiveEnabled触发（可能Archive.Files属性是 an ObservableCollection<File>），并且在此实现中无法禁用存档。要禁用存档，您可以重新创建files集合，或更改files为Dictionary<File, IList<Archive>>（从文件到它们所在的已启用存档的字典）并稍微调整逻辑。

于 2013-10-23T16:52:36.943 回答