9

每当我想插入 aSortedList时，我都会检查该项目是否存在，然后插入。这是两次执行相同的搜索吗？一次查看项目是否存在，然后再次查找插入项目的位置？有没有办法优化它以加快速度，或者这只是这样做的方法，不需要更改？

if( sortedList.ContainsKey( foo ) == false ){
    sortedList.Add( foo, 0 );
}
4

5 回答 5

6

您可以将项目添加到 HashSet 和列表中，在哈希集中搜索是查看是否必须将值添加到列表的最快方法。

if( hashSet.Contains( foo ) == false ){
    sortedList.Add( foo, 0 );  
    hashSet.Add(foo);
}
于 2012-11-08T16:13:43.787 回答
1

您可以使用索引器。索引器在内部以最佳方式执行此操作，首先使用二进制搜索查找与键对应的索引，然后使用此索引替换现有项目。否则，通过考虑已计算的索引来添加新项目。

list["foo"] = value;

无论密钥是否已经存在，都不会引发异常。

更新：

如果新值与旧值相同，则替换旧值与什么都不做具有相同的效果。

请记住，已完成二进制搜索。这意味着在 1000 个项目中找到一个项目大约需要 10 个步骤！log2(1000) ~= 10. 因此，进行额外的搜索不会对速度产生重大影响。在 1,000,000 个项目中搜索只会将该值加倍（约 20 步）。

但是通过索引器设置值在任何情况下都只会进行一次搜索。我使用 Reflector 查看了代码并可以确认这一点。

于 2012-11-08T16:22:16.887 回答
1

如果这不能回答您的问题，我很抱歉，但我不得不说，有时 .NET 中的默认集合结构在功能上受到不合理的限制。Add如果方法返回一个指示成功/失败的布尔值，这可能已经被处理了HashSet<T>.Add。所以一切都在一步完成。事实上，整个 ofICollection<T>.Add应该是一个布尔值，因此在实现方面它是强制的，就像Collection<T>在 Java 中一样。

您可以使用ServySortedDictionary<K, V>指出的结构，也可以使用和在同行的答案中的组合以获得更好的性能，但他们都没有真正坚持只做一次哲学。我尝试了几个开源项目，看看在这方面是否有更好的实现，但找不到。HashSet<K>SortedList<K, V>

您的选择：

  1. 在绝大多数情况下，进行两次查找是可以的，不会造成太大的伤害。坚持一个。没有内置解决方案。

  2. 编写自己的SortedList<K, V>类。这一点都不难。

  3. 如果你很绝望，你可以使用反射。该Insert方法是 SortedList 类中的私有成员。一个例子。. 请不要这样做。这是一个非常非常糟糕的选择。为了完整起见，在此提及。

于 2014-06-12T19:40:14.730 回答
0

ContainsKey进行二进制搜索，即 O(log n)，因此除非您列出大量，否则我不会太担心。而且，据推测，在插入时，它会进行另一次二进制搜索以找到要插入的位置。

避免这种情况的一种选择（搜索两次）是使用 List 的BinarySearch方法。如果未找到该项目，这将返回一个负值，并且该负值是应插入该项目的位置的按位补充。所以你可以寻找一个项目，如果它不在列表中，你就知道它应该插入到哪里来保持列表的排序。

于 2012-11-08T16:19:07.143 回答
0

SortedList<Key,Value>是一种您可能根本不应该使用的慢速数据结构。您可能已经考虑过使用SortedDictionary<Key,Value>，但发现它不方便，因为这些项目没有索引（您不能编写sortedDictionary[0]），并且您可以为但不编写查找最近的键操作。SortedListSortedDictionary

但是如果你愿意切换到第三方库，你可以通过改变不同的数据结构来获得更好的性能。

SortedList<Key,Value>Loyc Core 库包含一种数据类型，它的工作方式与列表大时相同，但速度显着加快。它被称为BDictionary<Key,Value>。

现在，回答您最初的问题：是的，您编写代码的方式是执行两次搜索和一次插入（插入是最慢的部分）。如果切换到BDictionary，则有一种方法bdictionary.AddIfNotPresent(key, value)可以将这两个操作组合成一个操作。如果添加了指定的项目，则返回 true，如果已存在，则返回 false。

于 2016-02-26T05:40:33.323 回答