I have an algorithm which has an asymptotic runtime of O(log^2 n). It involves a binary search nested within another binary search. These binary searches are upon a storage array. It is likely that the nested binary search will end up re-reading storage array values which have already been read by a previous iteration of the parent binary search.
I would like to somehow cache values which have been read from the array. However, the traditional caching implementation approach (a map from an input such as the value's index to that index's value) does not seem possible in Solidity. This is because the
mapping type can only be created within storage, not memory. Clearly, this would defeat the purpose of my cache.
Current Best Approach
The best approach I have so far come up with is to create a fixed-size in-memory array for which values are a pairs of (index, value). In order to interrogate the cache for a hit or miss, a linear scan on this this array would be done to check if the target index has been stored.
This is obviously not ideal, as the overhead of re-reading a value from storage is "only" 500 gas. It is likely that the gas overhead of this linear scan will, statistically speaking, result in a higher gas cost overall than eschewing a cache entirely.
Essence of the Question
Is the described approach the best approach available given the tools Solidity offers?
I would like to hopefully achieve log-time or constant-time cache interrogation. This does not seem possible without an in-memory mapping, or an in-memory array of the same length as the storage array. This is not an option as I must keep the gas cost of searching the array sub-linear in terms of array length.
Perhaps one might use a constant-size in-memory array which stores the (index, value) tuples in sorted order by the index? This would make it possible to perform a binary search on the array given the index in question but results in log-time for both setting and getting from the cache.