pbies pbies - 11 days ago 5
C# Question

Fill ICollection<Class> with proper parent objects

I have a class:

public class MyObject {
int id;
int parentId;
MyObject parentObj;
}


and I need to fill parentObj with proper objects. I need to do this with look on performance and simplicity.

So I have code:

ICollection<MyObject> Method(ICollection<MyObject> coll)
{
foreach(var item in coll)
...

return coll;
}


that I would need to fill the parentObj with proper objects from this collection. As I can think the complex of this problem is N*log(N).

Answer

A classic approach is using dictionaries. The lookup operation (retrieve the value for a given key) can be implemented in O(1). This assumes a good hash function that maps the key to a position in a lookup array.

Using the default Dictionary implementation in .net, this will result in this code.

ICollection<MyObject> Method(ICollection<MyObject> coll)
{
    var lookup = new Dictionary<int, MyObject>();
    foreach (var item in coll)
    {
         lookup.Add(item.id, item);
    }
    foreach (var item in coll)
    {
         item.parentObj = lookup[item.parentId];
    }

    return coll;
}

There is a memory overhead with allocating lookup, but the runtime will be (theoretically) O(n + n) = O(n)

Comments