Skip to content

list.unique needs quadratic time #667

@radekm

Description

@radekm

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.

I believe that the following implementation is faster (if set.contains and set.insert are logarithmic):

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
}

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions