determine common members in list of lists

[John A Grandy]

InstrumentPropertyEntity
string Name

InstrumentEntity
string Name
List<InstrumentPropertyEntity> InstrumentProperties


For a List<InstrumentEntity> , I want to determine the
List<InstrumentPropertyEntity> held in common by all members.


What is the most performant algorithm ?

 

[Pavel Minaev]

InstrumentPropertyEntity
    string Name

InstrumentEntity
    string Name
    List<InstrumentPropertyEntity> InstrumentProperties

For a List<InstrumentEntity> , I want to determine the
List<InstrumentPropertyEntity> held in common by all members.

What is the most performant algorithm ?

If you need it to be fast, you shouldn't use List<T>. If
InstrumentProperties would have been of type HashSet<T>, then you
could use its IntersectWith method in a foreach loop to efficiently
find the intersection of InstrumentProperties for all your elements -
and that would be what you want. For plain List<T>, you can use
Enumerable.Intersect, but it's not any more efficient than a plain
nested foreach.

 

[John A Grandy]

How about transferring the contents of the first List to a HashSet and then
successively call HashSet.IntersectWith( List ) for each remaining List ?

InstrumentPropertyEntity
string Name

InstrumentEntity
string Name
List<InstrumentPropertyEntity> InstrumentProperties

For a List<InstrumentEntity> , I want to determine the
List<InstrumentPropertyEntity> held in common by all members.

What is the most performant algorithm ?

If you need it to be fast, you shouldn't use List<T>. If
InstrumentProperties would have been of type HashSet<T>, then you
could use its IntersectWith method in a foreach loop to efficiently
find the intersection of InstrumentProperties for all your elements -
and that would be what you want. For plain List<T>, you can use
Enumerable.Intersect, but it's not any more efficient than a plain
nested foreach.

 

[John A Grandy]

Just noticed that HashSet was introduced in 3.5. I am on 2.0.

 

[Pavel Minaev]

How about transferring the contents of the first List to a HashSet and then
successively call HashSet.IntersectWith( List ) for each remaining List ?

InteesectWith requires the argument to be a HashSet as well, so you'll
need to convert both.

 

[John A Grandy]

How is IntersectWith determining equality ? Is it instance equality ? Or
does it compare the values of all members of each instance ?

My instance equality is based on the Name property only.

InstrumentProperty1.Name == InstrumentProperty2.Name

How about transferring the contents of the first List to a HashSet and
then
successively call HashSet.IntersectWith( List ) for each remaining List ?

InteesectWith requires the argument to be a HashSet as well, so you'll
need to convert both.

 

[Pavel Minaev]

Just noticed that HashSet was introduced in 3.5. I am on 2.0.

You can always use Dictionary with dummy values - performance-wise,
it's the same as HashSet - but you'd still have to code Intersect
youself. Perhaps this would do the trick:

IEnumerable<T> Intersect<T>(IEnumerable<T> xs, IEnumerable<T> ys)
{
Dictionary<T, bool> zs = new Dictionary<T, bool>();
foreach (T x in xs)
{
zs.Add(x, false);
}
foreach (T y in ys)
{
bool dummy;
if (zs.TryGetValue(y, out dummy))
{
zs[y] = true;
}
}
foreach (KeyValuePair<T, bool> z in zs)
{
if (z.Value)
{
yield return z.Key;
}
}
}