Hacker News Reader

I have a feeling the second question will stay open. :)

I believe so too. To choose an efficient algorithm, you have to know things about the input data. Even with the sorting example, this is so; e.g. if you place a certain set of constraints on the input, its possible to sort in linear time. But the compiler has no way of knowing such things, unless, of course, the language has some means of expressing constraints on the input in a manner that is digestible by the compiler...

I don't think this is that hard of a problem. The compiler could have a set of algorithms, each controlled by a set of constraints. Basically the job of the compiler would be to "normalize" a set of constraints such that they can be matched to an equivalent set of constraints from its algorithm toolbox.

From the sorting example, the compiler could recognize that the constraints given match the problem of sorting. If the input data also had the constraint of "integer between 0 and 10,000", it would recognize this as a subset of sorting that could be handled through a linear time algorithm.

The compiler could also be an interpretor. ;) What could be a better way to chose the algorithm than to try them all on the actual data runtime (or in "training mode")?

Reply on news.ycombinator.com