在排序列表中快速查找项目索引

本文关键字：查找 项目 索引 排序 列表 | 更新日期: 2023-09-27 18:10:22

我有一个对象:

public class MyObject
{
int id;
string value;
}

我也有一个列表:

List<MyObject> list = new List<MyObject>;
for(int i=0;i;i<100000;i++)
{
list.Add(new MyObject(i, string.Format("Item {0}", i));
}

And list将是:

1, "Item 1"
2, "Item 2"
....
99999, "Item 99999"

这个列表是一个按ID字段排序的排序列表。注意这是一个描述排序列表的例子，它不像上面的例子那么简单。

我想根据ID字段查找有序列表中的一个项。我不知道。net框架是否支持在有序列表中快速搜索而不使用枚举。

我对性能很感兴趣，因为有一个大列表。谢谢。

问好。

在排序列表中快速查找项目索引

您可以使用二进制搜索。

您可以使用内置实现，提供一个自定义的IComparer<T>来比较您的类型的id属性:

var objToFind = new MyObject { id = 42 };
int foundIndex = yourList.BinarySearch(objToFind, new MyObjectIdComparer());
// ...
public class MyObjectIdComparer : Comparer<MyObject>
{
    public override int Compare(MyObject x, MyObject y)
    {
        // argument checking etc removed for brevity
        return x.id.CompareTo(y.id);
    }
}

四个选项:

  • 如果你的列表总是包含ID为1的项目…N，那么你可以直接输入:

    MyObject foo = list[id - 1];

  • 您可以填充Dictionary<int, MyObject>

  • 您可以让MyObject实现IComparable<T>或IComparable(按ID排序)并使用List<T>.BinarySearch，提供一个具有所需ID的虚拟MyObject
  • 你可以自己实现二进制搜索——这样做并不太难

请注意，如果您采用最后一种方法，您可能希望以一种通用的方式作为扩展方法，以便以后可以重用它:

// Optionally another overload with an IComparer<TKey>
public static TItem ProjectedBinarySearch<TItem, TKey>(
    this IList<TItem> list,
    Func<TItem, TKey> projection)
{
    // Do the binary search here.
    // TODO: Decide what to do if you can't find the right value... throw
    // an exception? Change the return type to return the *index* instead of the
    // value?
}

我假设它实际上不会是1:1与数组索引和ID字段(如在您的示例中)，或者您可以使用[]-方法找到它。

选项1是将其添加到Dictionary中，并使用ID字段作为键。

选项2是编写一个临时的二进制搜索，从数组的中间开始，检查当前id是否更大、更小或正确。然后对新的子数组重复此操作，直到找到ID。

您可以实现某种二进制除法，而不是蛮力，开始-结束搜索，这应该会大大加快速度。还是使用Dictionary类型?

您可以简单地使用.Find()来查找列表中的项，而无需显式枚举:

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

编辑:实际上，看更多的细节，它看起来像是一个线性搜索，可能不是你想要的。

关于您ID的索引是ID - 1。但是，如果您已经删除了项目，那么这种方法将不起作用。然后您可以使用Binary search，前提是您的列表已排序。所以你必须始终保持它的排序，否则你会使用低效的Linear search。

看看Linq

using System.Linq;

从列表中获取一个可查询对象(通常通过.AsQueryable()调用)

对得到的Queryable应用。select ()

var c = queryable.Select (x => x.field == 999)

对于那些根据标题遇到这个问题的人(在排序列表中快速查找项目索引)，您可能有兴趣知道SortedList<TKey,>有以下两个方法:—

    public int IndexOfKey(TKey key);
    public int IndexOfValue(TValue value);

和SortedList有:-

    public virtual int IndexOfKey(object key);
    public virtual int IndexOfValue(object value);
相关文章：