28

上是否有下界函数SortedList<K ,V>？该函数应返回等于或大于指定键的第一个元素。有没有其他类支持这个？

伙计们 - 请再读一遍这个问题。我不需要返回密钥（如果存在）的函数。我对没有精确键匹配的场景感兴趣。

我对 O(log n) time 感兴趣。这意味着我对 foreach 循环没有问题，而是希望有一种有效的方法来做到这一点。

我对此做了一些测试。

编译器和运行时机器都没有优化 Linq 语句，因此它们遍历所有集合元素并且速度慢 O(n)。基于 Mehrdad Afshari 的回答，这里是在 Keys 集合上以 O(log n) 工作的二进制搜索：

public static int FindFirstIndexGreaterThanOrEqualTo<T>(
            this IList<T> sortedCollection, T key
        ) where T : IComparable<T> {
    int begin = 0;
    int end = sortedCollection.Count;
    while (end > begin) {
        int index = (begin + end) / 2;
        T el = sortedCollection[index];
        if (el.CompareTo(key) >= 0)
            end = index;
        else
            begin = index + 1;
    }
    return end;
}
4

6 回答 6

26

SortedList.Keys对集合进行二进制搜索。

开始了。这是 O(log n )：

private static int BinarySearch<T>(IList<T> list, T value)
{
    if (list == null)
        throw new ArgumentNullException("list");
    var comp = Comparer<T>.Default;
    int lo = 0, hi = list.Count - 1;
    while (lo < hi) {
            int m = (hi + lo) / 2;  // this might overflow; be careful.
            if (comp.Compare(list[m], value) < 0) lo = m + 1;
            else hi = m - 1;
    }
    if (comp.Compare(list[lo], value) < 0) lo++;
    return lo;
}

public static int FindFirstIndexGreaterThanOrEqualTo<T,U>
                          (this SortedList<T,U> sortedList, T key)
{
    return BinarySearch(sortedList.Keys, key);
}
于 2009-02-27T12:20:01.390 回答
5

我会使用 LINQ（假设您使用的是 C#3），但是使用带有谓词的 FirstOrDefault 的重载：

first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);

（许多其他 Enumerable 方法也可以采用谓词，这是一个不错的捷径）

于 2009-02-27T12:36:23.237 回答
3

不知道，但这是一个简单的 LINQ 语句：

first = sortedList.Where(x => x >= theObjectForComparison).FirstOrDefault();

first要么是第一个通过比较的对象，要么是default(T)（通常是null）。

编辑

DaveW 的版本：

first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);

做同样的工作，但可能会更快，但你必须测试它。

于 2009-02-27T12:20:06.273 回答
0

或者您可以编写自己的扩展方法来执行此操作。请注意，不保证所有这些功能都按顺序执行。

于 2009-02-27T12:39:09.533 回答
0

SortedList<K ,V> 上是否有下界函数？该函数应返回等于或大于指定键的第一个元素。

此示例作为对 SortedList 的扩展实现，它返回大于或等于提供的键的最小元素的值。如果所有键都小于提供的键或提供了空列表，则返回 default(TValue)

public static TValue LowerBound<TKey, TValue>(this SortedList<TKey, TValue> list, TKey key) {
  if (list.Count == 0)
    return default;

  var comparer = list.Comparer;
  if (comparer.Compare(list.Keys[list.Keys.Count - 1], key) < 0)
    return default; // if all elements are smaller, then no lower bound

  int first = 0, last = list.Count - 1;
  while (first < last) {
    var middle = first + (last - first) / 2;
    if (comparer.Compare(list.Keys[middle], key) >= 0)
      last = middle;
    else
      first = middle + 1;
  }
  return list[list.Keys[last]];
}

使用示例：

SortedList<string, Object> myList = new SortedList<string, Object>();
...
var value = myList.LowerBound<string, Object>("theKey");
于 2021-03-16T07:55:21.767 回答
-2

希望这应该更快，具体取决于 SortedList 的实现。

public static int FindFirstIndexGreaterThanOrEqualTo<K, V>(
        this SortedList<K, V> sortedCollection, K key
    ) where V : new()
{
    if (sortedCollection.ContainsKey(key))
    {
        return sortedCollection.IndexOfKey(key);
    }
    sortedCollection[key] = new V();
    int retval = sortedCollection.IndexOfKey(key);
    sortedCollection.Remove(key);
    return retval;
}
于 2013-05-16T21:51:28.800 回答