在排序列表

快速查找项目的索引我有一个目标：在排序列表

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)); 
}

和列表将是：

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

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

我想根据ID字段找到一个有序列表项。我不知道.NET Framework支持快速搜索有序列表而不枚举。

我对表现感兴趣，因为一个大名单。谢谢。

此致敬礼。

来源

2011-10-03 Leo Vo

不，你的名单将开始与'0 “项目0”' –

是，名单会以0开头，“项目0 “但你的意思是？这个列表只是一个例子来描述一个有序列表。 –

您可以使用binary search。

可以使用built-in implementation，提供自定义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); 
    } 
}

来源

2011-10-03 10:56:23 LukeH

而不是蛮力，开始，结束搜索，你可以实现某种二进制分割，并应该加速它很好。或者使用字典类型来代替？

来源

2011-10-03 10:55:36

我认为它实际上不会1：1的数组索引和ID字段（就像在你例如），或者你可以使用[] - 方法来找到它。

选项1是将其添加到字典中，并将ID字段用作关键字。

选项2是编写一个临时二进制搜索，从数组中间开始，检查当前的id是否更大，更小或正确。然后再次使用新的子阵列，直到找到您的ID。

来源

2011-10-03 10:57:11

您可以简单地使用.Find（）来查找列表中的一个项目，没有明确地列举：

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

编辑：其实，寻找更详细看起来这是一个线性搜索和可能不是你想要的。

来源

2011-10-03 10:57:21 dougajmcdonald

虽然这仍然是O（N）。它仍在列举，只是不明确。 –

是的，我注意到，我发布后，doh！ – dougajmcdonald

四个选项：

如果您的列表将总是包含ID为1个项目...n，那么你可以这样做：
```
MyObject foo = list[id - 1]; 
```
你可以填充Dictionary<int, MyObject>
你可以做MyObject实现IComparable<T>或IComparable（由ID排序），并使用List<T>.BinarySearch，提供了一个虚拟MyObject与所需的ID
您可以实现二进制搜索自己 - 它不是太难做这样

请注意，如果你把最后一种方法，你可以希望在一个通用的方法来做到这一点作为一个扩展方法，以便以后可以重用它：

// 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? 
}

来源

2011-10-03 10:58:11

关于你ID该指数是ID - 1。但是，如果您已删除项目，那么这种方式将无法正常工作。然后您可以使用Binary search，提供您列表已排序。所以你必须保持它总是排序，否则你会用不熟的Linear search。

来源

2011-10-03 11:02:27

看看LINQ的

using System.Linq;

从列表中（通常是通过.AsQueryable（）调用）

套用。选择（）上获得可查询

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

来源

2011-10-03 11:02:27 BigMike

获取可查询

对于那些基于它的标题（查找排序列表中的项目快速索引）的人，您可能有兴趣知道SortedList < TKey，TValue> has the以下两种方法： -

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

和SortedList的有： -

public virtual int IndexOfKey(object key); 
    public virtual int IndexOfValue(object value);

来源

2013-10-02 10:40:14

回答

相关问题