CODEWITHSUNDEEP
c#listsearch
Randy Minder
Randy Minder

Reputation: 48402

What is the most efficient search mechanism for this situation?

I have a class that is defined as follows:

public class AlarmViolation
{
    public string ObjectId { get; set; }
    public int ChartType { get; set; }
    public string AlarmInternalId { get; set; }
    public short PositionInSequence { get; set; }
    public short SequenceCount { get; set; }
    public string TagValue { get; set; }
    public DateTime PurgeDate { get; set; }
}

Then I create a List of this class as follows:

List<AlarmViolation> alarmViolationList;

I currently execute a Linq query as follows:

return alarmViolationList
  .Where(row => row.ObjectId == objectId)
  .Where(row => row.ChartType == this.ChartType)
  .Where(row => row.AlarmInternalId == this.InternalId)
  .Where(row => row.PositionInSequence == positionInSequence)
  .Where(row => row.SequenceCount == sequenceCount)
  .Any();

I am getting pretty bad performance with my current implementation. The list will typically contain somewhere between 150K and 300K entries. This query is executed hundreds of times on a regular schedule (roughly every 3 minutes).

If I could somehow index this list, or if this were a database table, I would create an index on ObjectId + ChartType.

Could someone suggest a more efficient implementation. If you need more information, I would be glad to provide it.

Upvotes: 2

Views: 134

Answers (3)

Sarfaraz Nawaz
Sarfaraz Nawaz

Reputation: 361302

Why don't you write this:

return alarmViolationList
      .Any(row => row.ChartType == this.ChartType &&              //int
                  row.PositionInSequence == positionInSequence && //short
                  row.SequenceCount == sequenceCount &&           //short
                  row.AlarmInternalId == this.InternalId &&       //string
                  row.ObjectId == objectId);                      //string

This should improve the performance by some amount, in my opinion. Note that I'm doing string comparison after int and short comparisons, taking advantage of short-circuits.

Upvotes: 0

usr
usr

Reputation: 171178

As you only search for equality, I suggest you use a hashtable. Create a class that will hold all members which you equality-search on (in your case: ObjectId, ChartType, AlarmInternalId, ...). Implement Equals and GetHashCode.

Next, put all your objects into a lookup table using either Enumerable.ToDictionary or Enumerable.ToLookup. You can use that newly created "key" class to add the items and to search for items.

This will give you constant time lookup, even for multiple results.

Upvotes: 1

Jon Skeet
Jon Skeet

Reputation: 1499860

If I could somehow index this list, or if this were a database table, I would create an index on ObjectId + ChartType.

That suggests you should create a key type (AlarmViolationKey?) consisting of the ObjectId and ChartType, then use a Dictionary<AlarmViolationKey, AlarmViolation>. That will radically enhance the search time. If you have more than one violation per key, and you've created the list up-front in a way where it won't be changing, you could use a Lookup instead.

Whatever you do, basically you don't want to do the linear scan you're currently doing - you want a hash-based lookup.

(Depending on your exact situation, you may still need a list, or you may be able to use a dictionary instead of the list completely. It's hard to say without any more context.)

Upvotes: 3

Related Questions