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?
Is it possible to create an algorithm-aware optimizer?
cc.complexity theory;ds.algorithms;pl.programming languages;optimization;compilers