On Thu, Jan 03, 2013 at 11:33:53AM -0700, Marcus G. Daniels wrote: > 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. Profiling will reveal that you spend 5% time in insert and 3% time in remove. You spend two weeks optimizing your tree and memory allocator for it. > > 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).
And thats exactly a problem I am talking about. Person that writes structures will not notice that what he writes is not needed and introduce much more problems by adding patricia trees etc. A person who uses that structure will not notice that he can do it more effectively without these structures because performance details were abstracted away. Note that in my examples each uses some special property that is not worth abstracting because its quite narrow use case. > > 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 _______________________________________________ fonc mailing list [email protected] http://vpri.org/mailman/listinfo/fonc
