On 1/2/13 1:49 AM, Ondřej Bílka wrote:
A better example is that you have c code where at several places is code for inserting element into sorted array and using that array. What should you do. CS course taugth us to use red-black tree there. Right? Well not exactly. When one looks how is this code used it discovers that first occurence is shortest path problem so radix heap is appropriate. Second does not use ordering so hash table is more appropriate. Third periodicaly generates webpage from sorted data so keeping new data in separate buffer and calling sort from generating routine looks best. Finally fourth, original contains a comment: /* Used to find closest value to given value. Profiling shown this accounted to 13% of time. As updates are rare (not changed in previous year) using more sophisticated structures than binary search is counterproductive.*/
I imagine a process like this:
First create a generic container type, say a Map, for the array and a lookup and traversal routine.
If performance matters, profiling will reveal that certain uses are more conspicuous than others.
Inspection of those uses will suggest refinement of the Map to drop the traversal and/or lookup routines, and thus diversification of the types to an ordered or unordered sets. Distinguishing between integer and more expensive comparisons might motivate introduction of Patricia trees (for integer sets).
Maybe I'm losing sight of the question at hand. I'm just saying that going maximally generic at first will motivate appropriate specialization of the abstractions. The opposite approach of specialized inline implementations, built from scratch in different apps or even different modules of the same app has a higher risk of creating frozen accidents.
Marcus _______________________________________________ fonc mailing list [email protected] http://vpri.org/mailman/listinfo/fonc
