I've recently implemented a physics system where each object has to interact with eachother. It consisted of, pretty much, the following algorithm:
for obj_a in world for obj_b in world obj_a.collide(obj_b)
This is O(N^2) and obviously scales very badly. I know, though, that distant objects don't collide, so I partitioned the space. The algorithm became:
for obj_a in world for obj_b in space_partition_of(obj_a) obj_a.collide(obj_b)
Considering the second loop iterates only over objects close to A, it brings the complexity down to almost O(N) and is ridiculously faster.
That made me think: it does not matter which language I implemented the first algorithm, it would always be sluggish. There is not a single compiler in the world that would fix my mistake, as much as obvious it seems for a human programmer. My question is: what is there stopping us to create a compiler that replaces the algorithms and data-structures used for the optimal ones? Is it impossible in a turing complete language? Would it be possible in a non-turing-complete language such as Idris?