Почему этот основной оператор списка занимает гораздо больше времени, чем этот в длинном списке в Elixir?

Question

Так в эликсире 1.3.2, я создаю 2 большие списки:

a = Enum.to_list(10..1_000_001) 
b = Enum.to_list(1..1_000_000) 

Я заметил, что a++b возвращает результат быстро, но a--b занимает много времени, чтобы вернуть результат. Почему это?

Answer 1

Я думаю, что для объединения массивов нужно только выделить память для нового массива, а затем поместить, но оба массива в выделенной памяти.

Для вычисления разности двух массивов каждый элемент второго массива выполняется в первом массиве (элемент удаляется из первого массива при его обнаружении).

Сложность добавления O (n) и сложность вычитания - O (n2).

Из документов - http://elixir-lang.org/docs/stable/elixir/Kernel.html

complexity of a ++ b пропорциональна длине (а), поэтому следует избегать многократно добавления к спискам произвольной длины, например, list ++ [item].

complexity of a -- b пропорционален длине (a) * length (b), что означает, что она будет очень медленной, если оба a и b являются длинными списками. В таких случаях рассмотрите преобразование каждого списка в MapSet и используя MapSet.difference/2.