Pour les gourous de performance de Linq - Recherche par l'ICollection non générique

Question

J'ai besoin de rechercher à travers une collection d'objets "item" contenant une propriété temporelle. J'ai une solution rapide en place mais c'est très désordonné (postera si rien ne vaut mieux se lever). Vous trouverez ci-dessous mes tentatives d'exécution de la recherche moi-même à l'aide de Linq et de National.

Dans mon cas particulier, je sait les articles sont commandés à faible teneur élevée en fonction de l'heure. Quand je les itère à travers eux, c'est le 9/12, 9/13, 9/14. J'aimerais trouver une solution rapide même si cela n'est pas commandé, mais pas important en ce moment.

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

Ma solution actuelle est une recherche binaire pour les heures de début et de fin et boucle à travers l'Icollection basée sur ces index. C'est très rapide (1-2 secondes) mais très désordonné. Je n'ai pas besoin une solution différente mais je pensais que je vous lancerais des experts de performance.

Y a-t-il un moyen plus rapide et élégant de rechercher l'ICOLLECTION? BTW Je n'ai aucun contrôle sur la collection que je suis donnée et que je ne peux pas changer sa structure. .NET 4.0

et non, je ne peux pas utiliser system.diagnostics.venting.reader parce que je suis coincé avec Windows XP

Answer 1

Modifier

sur l'affirmation selon laquelle La réponse de Dasblinkenlight est généralement correcte, j'ai écrit une fonction d'assistance générique rapide.

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

que je voudrais utiliser comme ça,

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

---

Tu ne veux pas faire quelque chose comme ça

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

Je suppose que les données que vous voulez sont à la fin et prend moins de la moitié de la collection.

ou peut-être utiliser LINQ pour effectuer la coulée en parallèle,

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

Votre "requête" est incorrecte.Vous sélectionnez en fait un groupe de booléens, mais pas de filtrage.Vous voulez:

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

Ceci peut ne pas être plus rapide, mais cela mérite un chèque.Heck, je ne le ferais même pas en parallèle pour commencer.

En fait, Count a une surcharge qui prend un prédicat, vous pouvez donc utiliser ceci:

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

ou une version parallèle:

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

Comme Chris, je suis choqué que cela prendrait une minute pour tout implémentation ...

Answer 3

Cette première déclaration:

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

Améliore-t-il les performances qui changent-t-il (filtrera la liste avant la course de Foreach):

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