We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
list.unique
Hello. According to the documentation list.unique returns in loglinear time.
But it's implementation
pub fn unique(list: List(a)) -> List(a) { case list { [] -> [] [x, ..rest] -> [x, ..unique(filter(rest, fn(y) { y != x }))] } }
is quadratic instead. It's especially slow if list is already unique or almost unique.
list
I believe that the following implementation is faster (if set.contains and set.insert are logarithmic):
set.contains
set.insert
pub fn unique(xs: List(a)) -> List(a) { let #(result_rev, _) = xs |> list.fold(#([], set.new()), fn(acc, x) { let #(result_rev, seen) = acc case set.contains(seen, x) { False -> #([x, ..result_rev], set.insert(seen, x)) True -> #(result_rev, seen) } }) result_rev |> list.reverse }
The text was updated successfully, but these errors were encountered:
Oh dear! That's certainly not what we want, especially with the incorrect documentation. Would you mind making a pull request? Thank you
Sorry, something went wrong.
Successfully merging a pull request may close this issue.
Hello. According to the documentation
list.unique
returns in loglinear time.But it's implementation
is quadratic instead. It's especially slow if
list
is already unique or almost unique.I believe that the following implementation is faster (if
set.contains
andset.insert
are logarithmic):The text was updated successfully, but these errors were encountered: