Hi. I’m trying to improve the solution to this problem;
Every instance class B has an instance of class A.
I have a collection of Class B.
What ways can I search Class A’s properties at better than O(n)?
Real world example
An item class:
using UnityEngine;
public class Item
{
public string Id { get; set; }
}
Every ItemSlot contains an Item or null.
using UnityEngine;
public class ItemSlot
{
public Item Item { get; set; }
}
ItemStore has a collection of many ItemSlot.
using UnityEngine;
public class ItemStore : MonoBehaviour
{
//This collection can be anything, I don't mind
public List<ItemSlot> ItemSlots { get; set; }
}
The problem
I need to query these often, and they may contain many items as I’m keeping track of lots of these ItemStores. Here’s the O(n) way, just a bunch of foreach.
using UnityEngine;
public class ItemStore : MonoBehaviour
{
public List<ItemSlot> ItemSlots { get; set; }
}
public Item FindItem(string itemId)
{
Item foundItem = null;
foreach (var slot in ItemSlots)
{
if (slot.Item.Id == itemId)
{
foundItem = slot.Item;
break;
}
}
return foundItem;
}
public Item FindItem(Item item)
{
Item foundItem = null;
foreach (var slot in ItemSlots)
{
if (slot.Item == item)
{
foundItem = slot.Item;
break;
}
}
return foundItem;
}
The ideal solution
I was hoping for some way to make this entire nested structure searchable at O(1) like Hashset.Contains(), but I don’t know if it’s possible. A custom data structure of some kind? I think that’s beyond me, but if it can be done, I will learn to do it if I can know what sort of terminology I should be reading about and if it’s possble.
The not quite solutions
-
My first solution, the obvious is just foreach through. O(n) and fine for a few ItemStore. Starts to add up quickly. Want to go faster if possible.
-
My current solution is that every time an Item is updated, I take the item that was updated and add to a separate ItemMetrics class that stores the itemId and count in a Dictionary<string, int>. Now I can just query the dictionary in the metrics class instead of the ItemStore directly.
Drawback 1, if I miss an item being updated and don’t add it to the ItemMetrics dictionary to keep a perfect count, the ItemMetrics and ItemStore become out of sync. Keeping the Metrics and actual ItemStore synchronized seems unreliable and very easy to accidentally make bugs. ItemStore shifts the items around in to different ItemSlots a in almost all of its functions (there are a lot of places to miss something).
Drawback 2, the dictionary with itemId as key is great for fast search, until I want to search by a different Item property or even the Item reference itself. Now I’m back to the start and if I carry on down this route, I’d need a different copy of the data for every different query. I don’t think this is the right approach.
- Almost the same as option 2, but change the List in ItemStore to a dictionary<string, int> with the key being the Id of the item in the slot, thus reducing the search to O(1). Has the same drawbacks as number 2 above though.
I seem to be running in to this nested objects need to be searchable problem often. I would guess there are some solutions that I don’t know to solve it. It seems quite common. That or I’m doing something wrong to keep backing myself in to the same corner 
A pointer in the right direction or any suggestions for something I can try, or look up, or learn would be great.
Jasper