FAQ
Mmmm. I didn't run tests on it, just a modification of my benchmarks to
take this implementation.

That is sad. Though on the brighter side, it means I don't need to think
about improving biogo.llrb.
On Fri, 2013-06-07 at 11:41 +0100, roger peppe wrote:
it's a nice idea but i'm sad to say the implementation is
broken. if there was a test that a) added more than
one element to the list and b) actually ran (tests must begin
with a "Test" prefix) then it would become evident that the
set never grows larger than one element and hence insertion
and lookup times are really remarkably fast :-)

here's a slightly different approach that doesn't require
implementing quite as many methods each time
and is somewhat more efficient to boot.

http://play.golang.org/p/NqEplsTLcv

the code still broken (i only fixed the most obvious
problem in the most obvious way) but i think the API
is perhaps worth considering.

here's the test file i used: http://play.golang.org/p/uYYwbT0Fkk

note that the Get benchmark hangs up - i think that insert
might be O(n) or something. i have no time to investigate.

cheers,
rog.

PS i am suspicious of all LLRB implementations without seriously
comprehensive test suites - i made an implementation years ago
which followed all the rules but was still broken in rare circumstances.
you can't depend on everything in Sedgewick's slides.
That's why my test suite is significantly longer than the actual
implementation... and includes graphical output for failing cases :)

Dan

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Search Discussions

Discussion Posts

Previous

Related Discussions

Discussion Navigation
viewthread | post
posts ‹ prev | 5 of 5 | next ›
Discussion Overview
groupgolang-nuts @
categoriesgo
postedJun 6, '13 at 5:09p
activeJun 7, '13 at 11:18a
posts5
users3
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase