Efficient way of retrieving an item from a collection with a mutable key

Question

I have a collection of items Foos that have a property FooPosition, and I need to quickly access Foos by their positions.

For example : retrieve a Foo which is located at X=0 and Y=1.

My first thought was to use a dictionary for that purpose nd to use the FooPosition as dictionary key. I know that every FooPosition in my collection is unique, I don't mind throwing an Exception if it is not the case.

This works well as long as Foos do not move all over the place.

But, as I figured out the hard way, and understood thanks to this and this posts, this does not work anymore if the FooPosition is updated. I shouldn't use mutable keys in a dictionary : the dictionary keeps the FooPosition HashCode in memory but does not update it when the underlying FooPosition is modified. Therefore, calling dic[Position(0,1)] gives me the Foo which was at this position when the dictionary was built.

So, I am now wondering what should I use to retrieve Foos by their positions efficiently.

By efficiently I mean not going all across the whole collection every time I query for a Foo by its position. Is there a suitable structure which would accomodate mutable keys?

Thanks for your help

EDIT

As mentioned rightfully in comments, there is a missing part in my question : I have no control over Foo Moves. The software is actually connected to another software (Excel via VSTO) via a COM Protocol which changes the FooPosition (Excel Ranges) without notifying the change.

Therefore, I cannot take take any action in case a move happens because I don't know that a change did happen.

public class FooManager
{
    public void DoSomething(IList<Foo> foos) {
        Dictionary<FooPosition, Foo> fooPositionDictionary = foos.ToDictionary(x => x.Position, x => x); //I know that position is unique

        //Move Foos all around the place by changing their positions. 

        FooPosition queryPosition = new FooPosition(0, 1);

        fooPositionDictionary.TryGetValue(queryPosition, out var foo1); //DOES NOT WORK
        var foo2 = foos.FirstOrDefault(x => x.Position == queryPosition); //NOT EFFICIENT

        //Any better idea?
    }
}

public class Foo
{
    public string Name { get; set; }
    public FooPosition Position { get; set; }
}

public class FooPosition : IEquatable<FooPosition>
{
    public int X { get; set; }
    public int Y { get; set; }

    public FooPosition(int x, int y)
    {
        X = x;
        Y = y;
    }

    public void MoveBy(int i)
    {
        X = X + i;
        Y = Y + i;
    }

    public bool Equals(FooPosition other)
    {
        if (ReferenceEquals(null, other)) return false;
        if (ReferenceEquals(this, other)) return true;
        return X == other.X && Y == other.Y;
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != this.GetType()) return false;
        return Equals((FooPosition) obj);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            return (X * 397) ^ Y;
        }
    }

    public static bool operator ==(FooPosition left, FooPosition right)
    {
        return Equals(left, right);
    }

    public static bool operator !=(FooPosition left, FooPosition right)
    {
        return !Equals(left, right);
    }
}

How about updating the dictionary, whenever an item is moved? `if (fooPositionDictionary.Remove(oldPosition, out var theMovedFoo)) { fooPositionDictionary.Add(newPosition, theMovedFoo); }` — Corak, Jun 23 '20 at 10:58
Instead of **modifying** an existing item, why not just create a copy for it with the updated position and replace the existing item with the copy? — MakePeaceGreatAgain, Jun 23 '20 at 11:03
@Corak yes I thought about it but unfortunately items are moved by an external code (this is a COM Protocol interface) and I have no control on how /when item are moved. I cannot neither create an event which will fire anytime the position changes. — XavierAM, Jun 23 '20 at 11:07
Could have a reference to the dictionary in your `FooPostition` class? When you call the settter methods for `X` and `Y`you could remove the old position reference in the dictionary and add the new position. — mortb, Jun 23 '20 at 11:09
@HimBromBeere unfortunaly, as I told Corak, items are moved outside of my control. So, items are modified by the program I am connected to and I cannot change anything about it. To be more specific, this is connected to Excel VSTO, and FooPosition is actually an Excel Range. if a user changes the Range, Excel doesn't notify my plug in of the move that occurs. — XavierAM, Jun 23 '20 at 11:10
_"(this is a COM Protocol interface)"_ This is a crucial part you should really have mentioned in your question. — Fildor, Jun 23 '20 at 11:11
well, if you have no control on when the positions are updated, how do you expect any data-storage to update its content if it is not even aware that any change occured? There is no way to keep your storage in sync. Thus the only way is to have a constant identifier in your map and iterate the items in that map - even if this seems uneficient. — MakePeaceGreatAgain, Jun 23 '20 at 11:15
How many entries (roughly) are we talking about? How many items do you query, before the next position change happens? Did you profile it? Do you have a performance problem with the "not efficient" way?` — Corak, Jun 23 '20 at 11:16
Well... If you know the bounderies of X and Y... You can use a multidimensional array. — Legacy Code, Jun 23 '20 at 11:16
@Corak hundred of thousands. An the search operation can be triggered thousand times as well. — XavierAM, Jun 23 '20 at 11:19
@HimBromBeere ok clear, that does answer the question, it is not feasible. I dind't expect anything, I am not 100% proficient with cross-process communications and I just asked, in case. — XavierAM, Jun 23 '20 at 11:20
I can't tell if this is applicable to your situation but the usual approach to this kind of Excel problem is to use Named Ranges and refer to the Named Ranges in your code rather than the worksheet and cell coordinates - Excel updates the RefersTo formula property of a named range when the named range is moved. Alternatively you may be able to use an excel event to tell your code when a move has occurred. — Charles Williams, Jun 23 '20 at 11:36
@CharlesWilliams actually you may be right, the solution could be by naming ranges afterwards to keep track of them. Are you aware of any limitation in the number of NamedRange we can create? Can I create one per cell in the worksheet without any troubles (I am exagerating but not that much :-) ) — XavierAM, Jun 23 '20 at 14:25
IMHO It gets a bit sticky perf-wise somewhere around 60000 to 100000 Names. But usually you don't name individual cells, you name contiguous areas or even build names that hold multiple areas. (Note that Excel will crash if you try to actually fill ALL the cells in a worksheet anyway, let alone Name them individually - it uses a sparse matrix storage scheme) — Charles Williams, Jun 23 '20 at 15:10

score 2 · Accepted Answer · edited Jun 23 '20 at 11:24

2

In some sense a dictionary - as any other hash-based data-storage - uses some kind of caching. In this case the hashes are cached. However as for every cache you need some constant data that does not change during the lifetime of that data-storage. If there is no such constant data, there´s no way to efficiently cache that data.

So you end up to store all items in some linear collection - e.g. a List<T>- and iterate that list again and again.

edited Jun 23 '20 at 11:24

Fildor

14,510
4
35
67

answered Jun 23 '20 at 11:22

MakePeaceGreatAgain

35,491
6
60
111

1

thanks @Fildor for the edit, although I like my typo ;) – MakePeaceGreatAgain Jun 23 '20 at 11:25
Yes, that would be awesome, if we could cash some data ... :D – Fildor Jun 23 '20 at 11:26

Efficient way of retrieving an item from a collection with a mutable key

1 Answers1