Open hissssst opened 1 month ago
Hi @hissssst!
Thank you for the feedback. I've pushed a feat/memoization branch. Maybe you can try whether this approach speeds things up for you? I tried with the Hamiltonian Path and a relatively large graph, but it just made things slower:
$ iex -S mix
Generated backfish app
Erlang/OTP 26 [erts-14.2.5] [source] [64-bit] [smp:20:20] [ds:20:20:10] [async-threads:1] [jit:ns]
Interactive Elixir (1.16.2) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> graph = Backfish.LargeGraph.generate_graph(25)
%{
1 => [3, 4, 0],
2 => [4, 5, 1],
3 => [5, 6, 2],
4 => [6, 7, 3],
5 => [7, 8, 4],
6 => [8, 9, 5],
7 => [9, 10, 6],
8 => ~c"\n\v\a",
9 => ~c"\v\f\b",
10 => ~c"\f\r\t",
11 => [13, 14, 10],
12 => [14, 15, 11],
13 => [15, 16, 12],
14 => [16, 17, 13],
15 => [17, 18, 14],
16 => [18, 19, 15],
17 => [19, 20, 16],
18 => [20, 21, 17],
19 => [21, 22, 18],
20 => [22, 23, 19],
21 => [23, 24, 20],
22 => [24, 25, 21],
23 => [25, 1, 22],
24 => [1, 2, 23],
25 => [2, 3, 24]
}
iex(2)> {time, _} = :timer.tc(fn -> Backfish.find_all_solutions(Backfish.Examples.HamiltonianPath, [args: [graph: graph, start_node: 1], memoize: false]) end); IO.puts("Time: #{time / 1_000_000} seconds"); :ok
Time: 5.016542 seconds
:ok
iex(3)> {time, _} = :timer.tc(fn -> Backfish.find_all_solutions(Backfish.Examples.HamiltonianPath, [args: [graph: graph, start_node: 1], memoize: true]) end); IO.puts("Time: #{time / 1_000_000} seconds"); :ok
Time: 10.311358 seconds
:ok
Hi, great library, clean approach! However, I have a couple of suggestions
Introduce memoization for
find_all_solutions
. While thinking about other problems, I've found that ifnext_state
function can return the same result for two different inputs (that is ifnext_state
is not bijection), a lot of solutions will be recomputed. It would be nice if this solver could store the%{state => next_state(state)}
kind of map to avoid recomputationsfind_all_solutions
function is craving for parallelization.Minor, it would be nice if you could remove examples from
lib
, so that they won't be loaded into runtime of the program which uses this dependency