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é Valimwww.plataformatec.com.br <http://www.plataformatec.com.br/>Founder and Director of R&D* On Tue, Apr 17, 2018 at 10:41 AM, Serge Smetana <[email protected]> wrote: > 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 > > -- > 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 [email protected]. > To view this discussion on the web visit https://groups.google.com/d/ > msgid/elixir-lang-core/a5f26b64-b3e3-43a3-804c- > 72cf151f9fd0%40googlegroups.com > <https://groups.google.com/d/msgid/elixir-lang-core/a5f26b64-b3e3-43a3-804c-72cf151f9fd0%40googlegroups.com?utm_medium=email&utm_source=footer> > . > For more options, visit https://groups.google.com/d/optout. > -- 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/CAGnRm4J1K%2BcaNUmrWeurLdKopt7RucD7Xqy68JE9-XkPOms1HQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
