按照 int[] 定义的顺序迭代 List<T> 的最快方法

Question

什么是迭代列表元素的最快方式，在这个列表中，每个项目都有一个关联的“分数”，并且具有最高分数的项目排在第一位。

例子：

List<X> items = new List<X>(new X[]{a,b,c,d});
int[] score = new int[]{20,301,-34,7};
foreach(X x in IterateByScore(items,score)) { // <-- Fastest way to do this?
    // order should be b - a - d - c
}

编辑：第一个例子使用了一个可以用作索引的有序列表，但我有一个“分数”列表。请原谅我的错误。

- Danvil

---

你不能在“X”的定义中包含排序值的原因是什么？ - ChrisF

@ChrisF：项目和顺序来自代码的不同部分，应该保持分开。 - Danvil

Answer 1

注意：此答案是在问题更新前发布的，在第二个数组中的值是第一个数组的索引时。

List<T> 在内部使用一个数组，因此索引访问是最合理的选择：

foreach (int index in order)
{
    X x = items[index];
    ...
}

如果需要的话，您可以将这种间接索引逻辑封装到一个IEnumerator<T>实现中，在其构造函数中接受List<T>和int[]。这种方法在期望IEnumerable<T>的情况下非常有用。

（个人认为除非这是您程序的性能瓶颈（我认为不是），否则不要过于关注性能。）

- Ondrej Tucny

---

简单、易懂、可能非常快。+1 - Maarten

@ Danvil 这对你有用，因为你使用索引来指定顺序，所以你的例子很简单。如果你有其他方式来定义顺序（不基于索引），那么这个解决方案当然就不适用了。 - King King

@OndrejTucny：不是真的...但你的答案完全没问题。我要发布一个新问题。 - Danvil

@KingKing：这正是问题所在。我正在发布第二个问题。 - Danvil

亲爱的@downvoter，你应该注意一下我回答开头的注释。在OP修改问题而不是发布新问题之前，你很快就会发现这个答案不仅相关，而且正确。 - Ondrej Tucny

Answer 2

简单的解决方案是创建一个新类：

```html

简单的解决方案是创建一个新类：

```

public class OrderedX
{
    public X Element { get; set; }
    public int Order { get; set; }
}

然后下单。

X[] element = new X[]{a,b,c,d});
int[] score = new int[]{20,301,-34,7};
List<OrderedX> items = new List<OrderedX>();
for (int i = 0; i < count; i++)
{
    items.Add(new OrderedX
    {
        X = element[i],
        Order = score[i]
    });
}
foreach(OrderedX x in items.OrderBy(a => a.Score)
{
    Process(x.X);
}

- ChrisF

---

应该为交叉编辑和交叉投票彼此的答案添加一个徽章 :-) - Ondrej Tucny

Answer 3

针对更新后的问题，我认为最有效的方法应该是使用Array.Sort方法:

List<X> items = new List<X>(new X[] { a, b, c, d });
int[] score = new int[] { 20, 301, -34, 7 };
List<X> sorted = items.ToArray();
Array.Sort(score, sorted);

foreach (X x in sorted)
{ 
    // process x here
}

- Douglas

Answer 4

我可能会使用Zip和匿名类型：

foreach (X x in items.Zip(scores, (item, score) => new { item, score })
                          .OrderByDescending(x => x.score).Select(x => x.item))
{
    // order is b - a - d - c
}

如果将X和它的分数配对是一个常见的事情，那么你应该创建一个命名类来代替匿名类型。

- Tim S.

Answer 5

虽然Ondrej的答案是正确的，但它仅适用于您将仅迭代一次列表（或少量次数）的情况。

如果您需要按给定顺序多次迭代列表，则最好先按所需顺序复制列表，因为这将促进缓存命中并显着提高内存访问性能。

List<X> items = new List<X>(new X[]{a,b,c,d});
int[] order = new int[] { 2, 3, 1, 0 };
List<X> sorted = order.Select(i => items[i]).ToList();

for (int i = 0; i < 10000000; ++i)
    foreach (X x in sorted)
    {
        // process x here
    }

- Douglas