Функциональное программирование: список содержит только уникальные элементы? - PullRequest
Новая
       15

Функциональное программирование: список содержит только уникальные элементы?

10 голосов
/ 06 октября 2010

У меня есть несортированный список, и я хочу знать, являются ли все элементы в нем уникальными.
Мой наивный подход будет 

<code>val l = List(1,2,3,4,3)
def isUniqueList(l: List[Int]) = (new HashSet()++l).size == l.size

По сути, я проверяю,Набор, содержащий все элементы списка, имеет одинаковый размер (поскольку элемент, появляющийся дважды в исходном списке, появится только один раз в наборе), но я не уверен, является ли это идеальным решением для этой проблемы.

Редактировать: Я протестировал 3 самых популярных решения, l==l.distinct, l.size==l.distinct.size и решение Алексея на основе HashSet.Каждая функция была запущена 1000 раз с уникальным списком из 10 элементов, уникальным списком из 10000 элементов и теми же списками с одним элементом, появляющимся в третьем квартале, скопированным в середину списка.Перед каждым запуском каждую функцию вызывали 1000 раз для разогрева JIT, весь тест выполнялся 5 раз, прежде чем время было взято с System.currentTimeMillis.Машина представляла собой C2D P8400 (2,26 ГГц) с 3 ГБ ОЗУ, java-версией была 64-битная виртуальная машина OpenJDK (1.6.0.20).Аргументы java были -Xmx1536M -Xms512M

Результаты: 

l.size==l.distinct.size (3, 5471, 2, 6492)
l==l.distinct           (3, 5601, 2, 6054)
Alexey's HashSet        (2, 1590, 3, 781)

Результаты с более крупными объектами (строки от 1 КБ до 5 КБ): 

l.size==l.distinct.size MutableList(4, 5566, 7, 6506)
l==l.distinct           MutableList(4, 5926, 3, 6075)
Alexey's HashSet        MutableList(2, 2341, 3, 784)

Решениеиспользование HashSets, безусловно, является самым быстрым, и, как он уже отметил, использование .size не имеет большого значения.

Ответы [ 3 ]

15 голосов
/ 06 октября 2010

Вот самое быстрое чисто функциональное решение, которое я могу придумать: 

def isUniqueList(l: List[T]) = isUniqueList1(l, new HashSet[T])

@tailrec
def isUniqueList1(l: List[T], s: Set[T]) = l match {
  case Nil => true
  case (h :: t) => if (s(h)) false else isUniqueList1(t, s + h)
}

Это должно быть быстрее, но с использованием изменяемой структуры данных (на основе реализации distinct, предоставленной Василом Ременюком): 

def isUniqueList(l: List[T]): Boolean = {
  val seen = mutable.HashSet[A]()
  for (x <- this) {
    if (seen(x)) {
      return false
    }
    else {
      seen += x
    }
  }
  true
}

А вот самое простое (эквивалентно вашему): 

def isUniqueList(l: List[T]) = l.toSet.size == l.size
6 голосов
/ 06 октября 2010

Я бы просто использовал distinct метод: 

scala> val l = List(1,2,3,4,3)
l: List[Int] = List(1, 2, 3, 4, 3)

scala> l.distinct.size == l.size
res2: Boolean = false


ADD : Стандарт distinct Реализация (из scala.collection.SeqLike) использует изменяемый HashSet для поиска дублирующихся элементов: 

  def distinct: Repr = {
    val b = newBuilder
    val seen = mutable.HashSet[A]()
    for (x <- this) {
      if (!seen(x)) {
        b += x
        seen += x
      }
    }
    b.result
  }
2 голосов
/ 06 октября 2010

Более эффективным методом было бы попытаться найти обман; это вернулось бы быстрее, если бы был найден: 

var dupes : Set[A] = Set.empty

def isDupe(a : A) = if (dupes(a)) true else { dupes += a; false }

//then
l exists isDupe
...