List.myers_difference is very slow and memory hungry

[Serge Smetana]

Hello,

Is this algorithm inherently slow and memory inefficient or is there something wrong with the implementation? Running it on two 5000 elements takes 20 seconds and 1.7 Gigabytes (!) of memory

iex(1)> a = String.duplicate("a", 5000) |> String.graphemes()

iex(2)> b = String.duplicate("b", 5000) |> String.graphemes()

iex(3)> :erlang.memory()

[total: 22780608, processes: 5842616, processes_used: 5841624, system: 16937992,

 atom: 264529, atom_used: 260532, binary: 40448, code: 7295199, ets: 375008]

iex(4)> List.myers_difference(a, b)  # takes 20 seconds

iex(5)> :erlang.memory()           

[total: 1816622088, processes: 1799695120, processes_used: 1799694128,

 system: 16926968, atom: 264529, atom_used: 260622, binary: 23688,

 code: 7298655, ets: 376544]         # And 1.7Gb of memory

Thanks,

Serge

[José Valim]

IIRC, myers is supposed to use m+n memory. But maybe that is the complexity for a mutable algorithm.

I believe processing time depends on the edit script and you have very large one here.

In any case, there is probably a lot of room for improvement here. :)

José Valim

www.plataformatec.com.br

Founder and 

Director of R&D

--
You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-core+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/a5f26b64-b3e3-43a3-804c-72cf151f9fd0%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.