hi all, i've uploaded a new snapshot of boost.heap. it includes some of the proposed changes and i have also added a benchmark sections. during the final time for the gsoc, i'd like to get the library ready for a review ... therefore, i uploaded a new snapshot [1] and an updated documentation [2]. feedback welcome ... cheers, tim [1] http://tim.klingt.org/code/attachments/download/31/boost_heap_280710.tar.gz [2] http://tim.klingt.org/boost_heap -- tim@klingt.org http://tim.klingt.org Cheat your landlord if you can and must, but do not try to shortchange the Muse. It cannot be done. You can't fake quality any more than you can fake a good meal. William S. Burroughs
Tim Blechmann wrote:
hi all,
i've uploaded a new snapshot of boost.heap. it includes some of the proposed changes and i have also added a benchmark sections. during the final time for the gsoc, i'd like to get the library ready for a review ...
therefore, i uploaded a new snapshot [1] and an updated documentation [2].
feedback welcome ...
Hi, some feedback on the documentation: * Motivation: Many boost libraries offer a "Motivation" section to say what real world issues are addressed by the library. Currently, I am using std::priority_queue and it suits my needs. When would they be insufficient? * Navigation: Some pages are missing navigation elements, e.g. http://tim.klingt.org/boost_heap/heap/concepts.html should have a "top"-link. * Warnings: For instance: Mutability: "Incorrect use of increase or decrease may corrupt the priority queue data structure!" It would be good to have short examples of correct and incorrect usage. * Data structure comparisons: The information seems rather incomplete. For instance, "In contrast to d-ary heaps, binomial heaps can also be merged in O(log n)." OK, now I know, that binomial heaps can be merged in O(log n), and d-ary can't. But I don't know the complexity for merging d-ary nor any other heap. Maybe it would be easier to use one or more tables to compare the features/complexities? Regards, Roland
hi, thanks for looking into it ...
* Motivation: Many boost libraries offer a "Motivation" section to say what real world issues are addressed by the library. Currently, I am using std::priority_queue and it suits my needs. When would they be insufficient?
true ... as for std::priority_queue. it not mutable, not stable, different instances cannot be merged or compared, elements cannot be iterated.
* Navigation: Some pages are missing navigation elements, e.g. http://tim.klingt.org/boost_heap/heap/concepts.html should have a "top"-link.
hm, i just saw it too ... i guess, this is a quickbook/boostbook issue, that will be resolved automatically, if it becomes an official part of boost ...
* Warnings: For instance: Mutability: "Incorrect use of increase or decrease may corrupt the priority queue data structure!" It would be good to have short examples of correct and incorrect usage.
i am a bit afraid to show a piece of incorrect code. in the documentation. but is is probably clearer than just describing it with words ...
* Data structure comparisons: The information seems rather incomplete. For instance, "In contrast to d-ary heaps, binomial heaps can also be merged in O(log n)." OK, now I know, that binomial heaps can be merged in O(log n), and d-ary can't. But I don't know the complexity for merging d-ary nor any other heap. Maybe it would be easier to use one or more tables to compare the features/complexities?
well, i have been thinking about it ... however i am not sure, what to compare (amortized or worst-case complexity). also the analysis of pairing heaps is not solved, yet ... otoh, there is also the `benchmarks' section. will try to incorporate your changes! tim -- tim@klingt.org http://tim.klingt.org Which is more musical, a truck passing by a factory or a truck passing by a music school? John Cage
Tim Blechmann wrote:
hi,
thanks for looking into it ...
:-)
* Warnings: For instance: Mutability: "Incorrect use of increase or decrease may corrupt the priority queue data structure!" It would be good to have short examples of correct and incorrect usage.
i am a bit afraid to show a piece of incorrect code. in the documentation. but is is probably clearer than just describing it with words ...
If you have some comment like // DON'T DO THIS AT HOME no harm would come from showing incorrect code, I guess. BTW: Wouldn't it be possible to check whether or not increase/decrease are used correctly (and throw an exception otherwise)?
* Data structure comparisons: The information seems rather incomplete. For instance, "In contrast to d-ary heaps, binomial heaps can also be merged in O(log n)." OK, now I know, that binomial heaps can be merged in O(log n), and d-ary can't. But I don't know the complexity for merging d-ary nor any other heap. Maybe it would be easier to use one or more tables to compare the features/complexities?
well, i have been thinking about it ... however i am not sure, what to compare (amortized or worst-case complexity). also the analysis of pairing heaps is not solved, yet ...
One idea would be to have a table for complexities for each pair of type and action (i.e. push, top, pop, merge, ...). If you have different values (e.g. optimal, average, worst-case), name them all. Maybe also describe what optimal/worst-case look like. Another might be size, number of memory allocations per element, stuff like that.
otoh, there is also the `benchmarks' section.
That's nice, btw One more thing: Even if boost heaps are probably quite easy to use, I'd add a small tutorial/examples section that shows some working code using heaps and their features. Regards, Roland
i am a bit afraid to show a piece of incorrect code. in the documentation. but is is probably clearer than just describing it with words ...
If you have some comment like // DON'T DO THIS AT HOME no harm would come from showing incorrect code, I guess.
well, people may think, that you may use it, if you are supersmart ;)
BTW: Wouldn't it be possible to check whether or not increase/decrease are used correctly (and throw an exception otherwise)?
no. there is no way to detect, whether some data has been modified. stl containers like map/set don't allow you to modify the key elements in general, boost.intrusive lets you modify the nodes, but assumes that you are careful enough not to modify the key ...
* Data structure comparisons: The information seems rather incomplete. For instance, "In contrast to d-ary heaps, binomial heaps can also be merged in O(log n)." OK, now I know, that binomial heaps can be merged in O(log n), and d-ary can't. But I don't know the complexity for merging d-ary nor any other heap. Maybe it would be easier to use one or more tables to compare the features/complexities?
well, i have been thinking about it ... however i am not sure, what to compare (amortized or worst-case complexity). also the analysis of pairing heaps is not solved, yet ...
One idea would be to have a table for complexities for each pair of type and action (i.e. push, top, pop, merge, ...). If you have different values (e.g. optimal, average, worst-case), name them all. Maybe also describe what optimal/worst-case look like.
i will see, what i can do.
One more thing: Even if boost heaps are probably quite easy to use, I'd add a small tutorial/examples section that shows some working code using heaps and their features.
well, in the concepts section, i am trying to explain the concepts and give some example code. not sure, if it is better to separate concepts and examples or to combine them ... tim -- tim@klingt.org http://tim.klingt.org All we composers really have to work with is time and sound - and sometimes I'm not even sure about sound. Morton Feldman
Tim Blechmann wrote:
i am a bit afraid to show a piece of incorrect code. in the documentation. but is is probably clearer than just describing it with words ...
If you have some comment like // DON'T DO THIS AT HOME no harm would come from showing incorrect code, I guess.
well, people may think, that you may use it, if you are supersmart ;)
If you include such a counterexample, put it on a separate page with large, red warnings, linked from the point where you describe the incorrect usage in prose. That way, it won't be interpreted as yet another example of proper usage by appearing or being listed near normal examples. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Tim Blechmann wrote:
One more thing: Even if boost heaps are probably quite easy to use, I'd add a small tutorial/examples section that shows some working code using heaps and their features.
well, in the concepts section, i am trying to explain the concepts and give some example code. not sure, if it is better to separate concepts and examples or to combine them ...
The sample code in the concepts section is nice to illustrate the concepts, but these are just code snippets. It would be nice to have some examples which just compile and do something. Regards, Roland
One more thing: Even if boost heaps are probably quite easy to use, I'd add a small tutorial/examples section that shows some working code using heaps and their features.
well, in the concepts section, i am trying to explain the concepts and give some example code. not sure, if it is better to separate concepts and examples or to combine them ...
The sample code in the concepts section is nice to illustrate the concepts, but these are just code snippets. It would be nice to have some examples which just compile and do something.
well, there is some actual code, that should compile and do something ;) http://tim.klingt.org/git?p=boost_heap.git;a=blob;f=libs/heap/examples/inter... -- tim@klingt.org http://tim.klingt.org ... to make life worth living ... Keith Rowe on making music
Tim Blechmann wrote:
One more thing: Even if boost heaps are probably quite easy to use, I'd add a small tutorial/examples section that shows some working code using heaps and their features. well, in the concepts section, i am trying to explain the concepts and give some example code. not sure, if it is better to separate concepts and examples or to combine them ... The sample code in the concepts section is nice to illustrate the concepts, but these are just code snippets. It would be nice to have some examples which just compile and do something.
well, there is some actual code, that should compile and do something ;)
http://tim.klingt.org/git?p=boost_heap.git;a=blob;f=libs/heap/examples/inter...
I trust it compiles, but since there is no main function, it doesn't actually do anything, right? I get no executable. Nothing to start playing with. I am not looking for something elaborate, but two or three small applications that just do something and allow me to experiment with a new library without writing anything from scratch. IMHO, Boost.Asio has a particularly nice example section with use cases and working example programs: http://www.boost.org/doc/libs/1_43_0/doc/html/boost_asio/examples.html Regards, Roland
participants (3)
-
Roland Bock -
Stewart, Robert -
Tim Blechmann