Mit Cache ist leider nicht, da ein nicht vorhersehbarer Zugriff auf die einzelnen Zellen stattfindet.
Das ist ja gerade der Sinn eines Caches, das selbst zu optimieren.
Ich würde mal einen MRU (Most Recently Used) Cache ausprobieren. Der wächst bis zur maximalen Größe X und schmeisst dann die Elemente raus, die am längsten *nicht* benutzt werden, d.h. Du wirst schon einen Benefit haben, wenn einige Daten mehrfach angefordert werden.
Von der Implementierung her ist es sehr sehr einfach: Man nehme eine Dictionary und eine linked List. Die Dictionary enthält die Listenelemente zum schnellen Suchen
Wenn Du ein Element suchst, dann suchst Du in der Dictionary nach dem Listenelement und bringst das in der LL nach vorne.
Wenn Du das Element nicht findest, lädst Du es und packst es in der LL nach vorne.
Wenn die LL die Maximalgröße überschreitet, räumst Du von hinten her auf.
Wäre denkbar, das das was bringt.