对于 LINQ 性能专家 - 搜索非泛型 ICollection

Question

我需要搜索包含时间属性的“Item”对象的集合。我有一个快速的解决方案，但它非常混乱（如果没有更好的出现，我会发布）。以下是我尝试使用 LINQ 等自行执行搜索。

就我的具体情况而言，我 知道 这些物品根据时间从低到高排序。当我迭代它们时，结果是 9/12、9/13、9/14。我想找到一个快速的解决方案，即使没有订购，但现在并不重要。

//ICollection c = GetCollection(); //25,000+ items
DateTime TIME = DateTime.Now.AddDays(-1);

EventLog scan = new EventLog("Application", "Server", "N/A");
EventLogCollection c = scan.Entries;
Console.WriteLine(logs.Count); // All entries already in list here

// 64 sec - SLOW
List<Item> l1 = new List<Item>();
foreach (Item i in c) { 
  if (i.time > TIME) { 
    l1.Add(i); }
}

// 93 sec - SLOWER
var l2 = c.Cast<Item>().AsParallel().Select(n => n.time > TIME);
var i = l2.Count();

// 98 sec - EVEN SLOWER!
List<Item> l3 = new List<Item>();
Parallel.ForEach(c.Cast<Item>(), n => {
    if (n.time > TIME) {
        l3.add(n);
    }
});

我当前的解决方案是对开始时间和结束时间进行 BinarySearch，并根据这些索引循环遍历 ICollection。它非常快（1-2 秒）但非常混乱。我不 需要 一个不同的解决方案，但我想我会把这个扔给你们性能专家。

有没有一种更快、更优雅的方式来搜索 ICollection？ 顺便说一句，我无法控制所提供的集合，也无法更改它的结构。.NET 4.0

不，我无法使用 System.Diagnostics.Eventing.Reader，因为我一直使用 Windows XP

Answer 1

编辑

在断言上， dasblinkenlight的答案通常是对的，我写了一个快速通用的辅助功能。

public static int BinaryFirstIndexOf<T>(
    Func<int, T> indexer,
    Func<T, boo> predicate,
    int count)
{
    var low = 0;
    var high = count - 1;

    while (low < (high - 1))
    {
        var mid = low + ((high - low) / 2);

        if (predicate(indexer(mid))
        {
            high = mid;
        }
        else
        {
            low = mid;
        }
    }

    if (predicate(indexer(low)))
    {
        return low;
    }

    if (low != high && predicate(indexer(high)))
    {
        return high;
    }

    return -1;
}

.

我会用这样使用，

var time = DateTime.Now.AddDays(-1);
var c = scan.Entries;

var first = BinaryFirstIndexOf(
     i => c[i], 
     e => e.TimeGenerated > time,
     c.Count);

if (first >= 0)
{
    var result = new List<Item>(c.Count - first);
    Enumerable.Range(first, c.Count - first).AsParallel()
    .ForAll(i => 
        {
            var j = i - first;
            result[j] = (Item)c[i];
        });
}

.

---

你不想做这样的事情

var time = DateTime.Now.AddDays(-1);
var c = scan.Entries;

var cutOff = 0;
for (var i = c.Count - 1; i > - 1; i--)
{
    if (c[i].TimeGenerated < time)
    {
        cutOff = i;
        break;
    }
}

var result = new List<Item>(c.Count - cutOff - 1);
var j = 0;
for (var i = cutOff + 1; i < c.Count; i ++)
{
    result[j] = (Item)c[i];
    j++;
}

.

我假设你想要的数据到底，占用的一半集合。

或者可能使用LINQ并行进行铸造，

var time = DateTime.Now.AddDays(-1);
var c = scan.Entries;

var cutOff = 0;
for (var i = c.Count - 1; i > - 1; i--)
{
    if (c[i].TimeGenerated < time)
    {
        cutOff = i;
        break;
    }
}

var result = new List<Item>(c.Count - cutOff - 1);
Enumerable.Range(cutOff + 1, c.Count - cutOff - 1).AsParallel()
    .ForAll(i => 
        {
            var j = i - cutOff - 1;
            result[j] = (Item)c[i];
        });

.

Answer 2

您的“查询”不正确。您实际上是在选择一堆布尔值，但没有进行过滤。你要：

var l2 = c.Cast<EventLogEntry>().AsParallel().Where(n => n.time > TIME);

这 可能 不会更快，但值得一试。哎呀，我什至不会从一开始就并行地做这件事。

实际上， Count 有一个需要谓词的重载，所以你可以使用这个：

var count = c.Cast<EventLogEntry>().Count(n => n.time > TIME);

或者并行版本：

var count = c.Cast<EventLogEntry>().AsParallel().Count(n => n.time > TIME);

和克里斯一样，我很惊讶这会花费一分钟多的时间 任何 执行...

Answer 3

第一个语句：

List<Item> l1 = new List<Item>();
foreach (Item i in c) { 
  if (i.time > TIME) { 
    l1.Add(i); }
}

.

它是否改进了更改的性能（将在Foreach运行之前过滤列表）：

List<Item> l1 = new List<Item>();
foreach (Item i in c.Where(a => a.time > TIME)) { 
    l1.Add(i);
}

.