aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib/doc
diff options
context:
space:
mode:
authorJohn Högberg <[email protected]>2018-10-15 18:17:12 +0200
committerLukas Larsson <[email protected]>2018-11-02 17:15:32 +0100
commitbf5886b790f8f386ed425f543506a4bebb48448c (patch)
treeb2ef444c7bc5fc21b9e1e4cf905041ca70832c78 /lib/stdlib/doc
parentdb6059a9217767a6e42e93cec05089c0ec977d20 (diff)
downloadotp-bf5886b790f8f386ed425f543506a4bebb48448c.tar.gz
otp-bf5886b790f8f386ed425f543506a4bebb48448c.tar.bz2
otp-bf5886b790f8f386ed425f543506a4bebb48448c.zip
Optimize operator '--' and yield on large inputs
The removal set now uses a red-black tree instead of an array on large inputs, decreasing runtime complexity from `n*n` to `n*log(n)`. It will also exit early when there are no more items left in the removal set, drastically improving performance and memory use when the items to be removed are present near the head of the list. This got a lot more complicated than before as the overhead of always using a red-black tree was unacceptable when either of the inputs were small, but this compromise has okay-to-decent performance regardless of input size. Co-authored-by: Dmytro Lytovchenko <[email protected]>
Diffstat (limited to 'lib/stdlib/doc')
-rw-r--r--lib/stdlib/doc/src/lists.xml8
1 files changed, 0 insertions, 8 deletions
diff --git a/lib/stdlib/doc/src/lists.xml b/lib/stdlib/doc/src/lists.xml
index 7efafedc82..55227aaee5 100644
--- a/lib/stdlib/doc/src/lists.xml
+++ b/lib/stdlib/doc/src/lists.xml
@@ -838,14 +838,6 @@ splitwith(Pred, List) ->
> <input>lists:subtract("123212", "212").</input>
"312".</pre>
<p><c>lists:subtract(A, B)</c> is equivalent to <c>A -- B</c>.</p>
- <warning>
- <p>The complexity of <c>lists:subtract(A, B)</c> is proportional to
- <c>length(A)*length(B)</c>, meaning that it is very slow if both
- <c>A</c> and <c>B</c> are long lists. (If both lists are long, it
- is a much better choice to use ordered lists and
- <seealso marker="ordsets#subtract/2">
- <c>ordsets:subtract/2</c></seealso>.</p>
- </warning>
</desc>
</func>