Удалить из массива повторяющиеся элементы

Question

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

a = [4, 3, 3, 1, 6, 6]

нужно получить

a = [4, 1]

Мой метод работает слишком медленно с большим количеством элементов.

arr = [4, 3, 3, 1, 6, 6]
puts arr.join(" ")
nouniq = []
l = arr.length
uniq = nil
for i in 0..(l-1)
  for j in 0..(l-1) 
    if (arr[j] == arr[i]) and ( i != j )
      nouniq << arr[j]
    end
  end
end
arr = (arr - nouniq).compact

puts arr.join(" ")

Answer 1

a = [4, 3, 3, 1, 6, 6]
a.select{|b| a.count(b) == 1}
#=> [4, 1]

Более сложное, но более быстрое решение (O(n) Я верю:))

a = [4, 3, 3, 1, 6, 6]
ar = []
add = proc{|to, form| to << from[1] if form.uniq.size == from.size }
a.sort!.each_cons(3){|b| add.call(ar, b)}
ar << a[0] if a[0] != a[1]; ar << a[-1] if a[-1] != a[-2]

Answer 2

arr = [4, 3, 3, 1, 6, 6]

arr.
  group_by {|e| e }.
  map {|e, es| [e, es.length] }.
  reject {|e, count| count > 1 }.
  map(&:first)
# [4, 1]

Answer 3

Без введения необходимости отдельной копии исходного массива и использования inject:

[4, 3, 3, 1, 6, 6].inject({}) {|s,v| s[v] ? s.merge({v=>s[v]+1}) : s.merge({v=>1})}.select {|k,v| k if v==1}.keys
 => [4, 1] 

Answer 4

Мне нужно было что-то подобное, поэтому протестировал несколько разных подходов. Все они возвращают массив элементов, которые дублируются в исходном массиве:

module Enumerable
def dups
  inject({}) {|h,v| h[v]=h[v].to_i+1; h}.reject{|k,v| v==1}.keys
end
def only_duplicates
  duplicates = []
  self.each {|each| duplicates << each if self.count(each) > 1}
  duplicates.uniq
end
def dups_ej
  inject(Hash.new(0)) {|h,v| h[v] += 1; h}.reject{|k,v| v==1}.keys
end
def dedup
  duplicates = self.dup
  self.uniq.each { |v| duplicates[self.index(v)] = nil }
  duplicates.compact.uniq
end
end

Результаты теста Benchark за 100 000 итераций, сначала с массивом целых чисел, затем с массивом строк. Производительность будет варьироваться в зависимости от количества найденных дубликатов, но эти тесты с фиксированным числом дубликатов (~ записи в половину массива являются дубликатами):

test_benchmark_integer
                                    user     system      total        real
Enumerable.dups                 2.560000   0.040000   2.600000 (  2.596083)
Enumerable.only_duplicates      6.840000   0.020000   6.860000 (  6.879830)
Enumerable.dups_ej              2.300000   0.030000   2.330000 (  2.329113)
Enumerable.dedup                1.700000   0.020000   1.720000 (  1.724220)
test_benchmark_strings
                                    user     system      total        real
Enumerable.dups                 4.650000   0.030000   4.680000 (  4.722301)
Enumerable.only_duplicates     47.060000   0.150000  47.210000 ( 47.478509)
Enumerable.dups_ej              4.060000   0.030000   4.090000 (  4.123402)
Enumerable.dedup                3.290000   0.040000   3.330000 (  3.334401)
..
Finished in 73.190988 seconds.

Так что из этих подходов кажется, что алгоритм Enumerable.dedup является лучшим:

• дублирует исходный массив, чтобы он был неизменным
• получает элементы массива uniq
• для каждого уникального элемента: ноль в первый раз в массиве dup
• компактный результат

Если бы только (array - array.uniq) работал правильно! (это не так - все удаляет)

Answer 5

Вот мой пример решения, используемого программистами Perl, использующими хеш для накопления счетчиков для каждого элемента в массиве:

ary = [4, 3, 3, 1, 6, 6]

ary.inject({}) { |h,a| 
  h[a] ||= 0
  h[a] += 1
  h 
}.select{ |k,v| v == 1 }.keys # => [4, 1]

Это может быть в одной строке, если это вообще важно, при разумном использовании точек с запятой между строками в map.

Немного по-другому:

ary.inject({}) { |h,a| h[a] ||= 0; h[a] += 1; h }.map{ |k,v| k if (v==1) }.compact # => [4, 1]

Он заменяет select{...}.keys на map{...}.compact, так что на самом деле это не улучшение, и мне немного сложнее понять.