Replace Go implementation by a more naive one

[silkeh]

I came across these benchmarks, and found the current Go implementation relatively hard to read. This (completely new) implementation aims to be better to read and maintain, with the following major differences:

• Rename Node's X,Y to Value and Weight
• Make methods of functions that operate on *Node
• Concentrate complexity in the *Node methods

The implementation seems to be a bit faster as well.

PS: I've opted to replace the current main.go because this is also a 'naive' implementation using raw pointers. This makes the diff is a bit useless, sorry about that.

[frol]

The implementation seems to be a bit faster as well.

It is faster because you changed the algorithm of the Contains implementation. I will only be able to merge your solution once it implements the same algorithm as all the other languages (using split + merge).

[frol]

I like your API design. I think most of the naive implementations (in other languages) would also benefit in readability if apply this design. Currently, most of the naive implementations (inlcuding Go) have the same API design, and I am not sure how to proceed with this PR. I consider having a second edition of the benchmark in the future (e.g. in a year, when the compilers will evolve even futher), so I think, I will need to organize the repository the way to indicate that the results are "fixed" while the solutions can be improved.

Thank you for your interest!

[silkeh]

It is faster because you changed the algorithm of the Contains implementation. I will only be able to merge your solution once it implements the same algorithm as all the other languages (using split + merge).

Right, I completely missed that. Updated.

I like your API design. I think most of the naive implementations (in other languages) would also benefit in readability if apply this design. Currently, most of the naive implementations (inlcuding Go) have the same API design, and I am not sure how to proceed with this PR. I consider having a second edition of the benchmark in the future (e.g. in a year, when the compilers will evolve even futher), so I think, I will need to organize the repository the way to indicate that the results are "fixed" while the solutions can be improved.

The API design here is mostly for aiding readability, but it shouldn't influence the actual performance. I guess the solution would be to not restrict solutions to an API with the actual object and method names, but to allow readable solutions with implementations in the spirit of the benchmark (Treap with split and merge). This may also allow languages to (better) show what they have to offer in terms of readability.

[frol]

I guess the solution would be to not restrict solutions to an API with the actual object and method names.

Well, this is a double-edged sword. Having all solutions sharing the API makes it easier to compare the syntax of different languages.

Having Contains / Insert / Delete on a Node might also be questionable. In the scope of the current benchmark, it looks good, but I have just realized that some_node.Delete(other_node) looks odd.

[silkeh]

Well, this is a double-edged sword. Having all solutions sharing the API makes it easier to compare the syntax of different languages.

Good point. I have updated the names to match the API for this PR, Go isn't a language with standardised naming for these things anyway. (Gist of original implementation here)

I think this discussion should probably take place in an issue when it's time for the second edition of benchmarks.

Having Contains / Insert / Delete on a Node might also be questionable. In the scope of the current benchmark, it looks good, but I have just realized that some_node.Delete(other_node) looks odd.

I guess in more general applications a node would be an unexported implementation detail and only Tree should be used for interaction.

[frol]

@silkeh Thank you for your contribution! I have no estimated time when I will get back to this benchmark, but once that happens, I will surely take this PR into account.