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-05 09:18:07 +0100
commitd98da38562ec79360b58eed87eced3a506f1ff6d (patch)
tree4946a629854e4a65ae751bebc177390bc36450f8 /lib/stdlib/doc
parent53e7743216647d810d529e397bd3ea7278c6047c (diff)
downloadotp-d98da38562ec79360b58eed87eced3a506f1ff6d.tar.gz
otp-d98da38562ec79360b58eed87eced3a506f1ff6d.tar.bz2
otp-d98da38562ec79360b58eed87eced3a506f1ff6d.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.xml6
1 files changed, 0 insertions, 6 deletions
diff --git a/lib/stdlib/doc/src/lists.xml b/lib/stdlib/doc/src/lists.xml
index 89ba5238b5..4a4c170bba 100644
--- a/lib/stdlib/doc/src/lists.xml
+++ b/lib/stdlib/doc/src/lists.xml
@@ -708,12 +708,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 will be very slow if
- both <c>A</c> and <c>B</c> are long lists.
- (Using ordered lists and
- <seealso marker="ordsets#subtract/2">ordsets:subtract/2</seealso>
- is a much better choice if both lists are long.)</p></warning>
</desc>
</func>
<func>