On Fri, 2007-03-16 at 10:58 -0400, Jacques Carette wrote: > First, one has to decide what is really being 'costed'. Worst-case or > average-case? Neither are fully satisfactory, for obvious reasons.
both :) We could write: worst_cost n * log n average_cost n * n and chose worst_case if the operation was required to be real time, average cost otherwise. Of course these things are only approximations and guesses, but we're not aiming for perfection in the first release: one example where it works would be cool! > How should costing be done? Well, there the answer is fairly > well-understood now: series. Or more precisely, and asymptotic series. Ok, so you suggest 'log n' is a bad idea? (Well, it can be considered sugar for a series). Anyhow, that's a good point. Series make sense. > But constants matter a lot. For example, consider two algorithms which > have cost n^3 and 10^12*n^2 respectively. The n^3 algorithm is to be > chosen over the O(n^2) algorithm essentially *always*, as the cross-over > is at n=10^12, which is likely bigger than what can realistically be > done. These are extreme cases, Not really. Computing is fully of bad O() performance algorithms which are used anyhow because the constants are more important for the reasons you describe. > I guess what I am saying is that whatever you implement, the above > considerations should be used in the *design* (ie design-for-change), as > if Felix is successful, whatever first approximation of costing will > need to evolve towards handling the above issues. Well I agree .. and that's why language implementors need theoreticians hanging around :) this kind of thing: worst_cost n * log n average_cost n * n is still weak: it addresses two case: batch processing and real time processing. Can this be generalised? And WFT do you do for chosing a data structure? That is, something where there are a SET of operations, not just one? A really interesting case is a hybrid which can convert representations, at a cost. When is it worth converting a list to an array? -- John Skaller <skaller at users dot sf dot net> Felix, successor to C++: http://felix.sf.net ------------------------------------------------------------------------- Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV _______________________________________________ Felix-language mailing list Felix-language@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/felix-language
