To perform the search-in-map with only a balance scale, we’d either need to compare all pairs of weights ahead of time (which would mean O(n2) effort), or we’d need to run out and compare physical weights in the middle of the search (at which point we’re effectively back to search-in-territory).
nit: (I think you maybe meant this but glitched while writing) in this particular example we could do better by indexing (in map) the rocks by weight order (O(nlogn) map-building comparisons). Then once we have the reference rock we can effectively blend our map with in-territory search for only O(logn) in-territory comparisons. It’s more costly overall (by a log factor) to build this map, but if we have map-building budget in advance it yields much faster solving (log instead of linear). Or if the reference rock was one of the original rocks (we just didn’t know which one), as long as our index has constant-time access we can do O(1) search in-map once the appropriate reference rock is pointed out.
I think this just corroborates your claim
The map-making process can use information before the search process “knows what to do with it”.
I think this raises an interesting further question, especially when we don’t know what the task will be ahead of time: how many (and what? and at what resolution?) indices should we ideally spend ‘prep’ time (and memory) on? (This was a professional concern of mine for several years as a software engineer haha)
nit: (I think you maybe meant this but glitched while writing) in this particular example we could do better by indexing (in map) the rocks by weight order (O(nlogn) map-building comparisons). Then once we have the reference rock we can effectively blend our map with in-territory search for only O(logn) in-territory comparisons. It’s more costly overall (by a log factor) to build this map, but if we have map-building budget in advance it yields much faster solving (log instead of linear). Or if the reference rock was one of the original rocks (we just didn’t know which one), as long as our index has constant-time access we can do O(1) search in-map once the appropriate reference rock is pointed out.
I think this just corroborates your claim
I think this raises an interesting further question, especially when we don’t know what the task will be ahead of time: how many (and what? and at what resolution?) indices should we ideally spend ‘prep’ time (and memory) on? (This was a professional concern of mine for several years as a software engineer haha)
Echoes of your gooder regulator theorem