search

evenfurther / pathfinding

Pathfinding library for rust
837 stars 69 forks source link

Further work for benchmarks #134

Closed felix91gr closed 6 years ago

felix91gr commented 6 years ago

I think there are two changes/upgrades to the benchmarks that could make them more precise:

  1. Shuffling the neighbours function's output, such that any algorithm that could benefit from preordering of the nodes is on the same playing field as the other algorithms. I'm mainly thinking here about DFS, which always picks the first option it can use, and therefore it benefits (or falls behind) by a huge amount depending on the ordering of its options. I was more keen on this idea a while ago, but now I'm thinking that it could be detrimental if some algorithm depends on a "consistent" ordering of the neighbors. By this I don't mean that it benefits or falls behind, but that it actually affects its correctness. This may not be a good idea, or it could actually be used to test for robustness. I want to think more about it :thinking:

  2. Adding more kinds of problems to the benchmarks. Currently the benchmarks use only a search on a grid. But the structure of a grid isn't representative of all the kinds of problems for Search. I think we could use a couple more kinds of problems, with a different state-space structure :slightly_smiling_face:

samueltardieu commented 6 years ago

I like (2). (1) not so much because I just want to be able to compare base cases and see how they evolve. The goal is not to benchmark one algorithm against the other, but to ensure that we do not make performances worse when making a change.

felix91gr commented 6 years ago

The goal is not to benchmark one algorithm against the other, but to ensure that we do not make performances worse when making a change.

Ohh, I see. Hmm, what do you think about reducing the size of the current benchmark problem? I've tried to run IDDFS on it, but it's way too slow for that size and layout (I forgot how slow it can be when there's a lot of back-pointing connections in the graph). Reducing it from 64x64 to 8x8 could help.

On the other hand, if we can make sure it's stated in the documentation that we aren't comparing them, I could reduce the size of the problem only for IDDFS, such that it's not a pain to benchmark it on a grid ^^

samueltardieu commented 6 years ago

Yes, benchmarking IDDFS on a smaller problem can be done.

felix91gr commented 6 years ago

Awesome. I can then remove the "skip" tags I put there :)

felix91gr commented 6 years ago

For (2), I'm thinking of starting with the Pancake Problem: http://www2.informatik.uni-freiburg.de/~ki/papers/helmert-socs2010.pdf

samueltardieu commented 6 years ago

That would be great. However, note that this particular issue (#134) will be closed automatically when your IDDFS PR is merged since it concerns benchmarking it. Maybe another issue would be better.

felix91gr commented 6 years ago

Oh, of course. Closing this after the IDDFS PR is merged would keep things cleaner. I'll make another one, and there we can have a brainstorm about new types of problems if you want :)

samueltardieu commented 6 years ago

Closed via #133.