如何选择唯一的元素

Question

我想要扩展Array类，并添加一个名为uniq_elements的方法，该方法会返回那些出现次数为一的元素。同时，我也想像uniq方法一样，在新的方法中使用闭包。示例代码如下：

t=[1,2,2,3,4,4,5,6,7,7,8,9,9,9]
t.uniq_elements # => [1,3,5,6,8]

使用闭包的示例：

t=[1.0, 1.1, 2.0, 3.0, 3.4, 4.0, 4.2, 5.1, 5.7, 6.1, 6.2]
t.uniq_elements{|z| z.round} # => [2.0, 5.1]

t-t.uniq 和 t.to_set-t.uniq.to_set 都不起作用。我不关心速度，因为我在程序中只调用一次，所以它可以很慢。

- Konstantin

---

不清楚，为什么第二个例子的结果中包含了 5.7？ - sawa

因为我错过了，所以现在被排除了。 - Konstantin

Answer 1

辅助方法

此方法使用辅助器：

class Array
  def difference(other)
    h = other.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 }
    reject { |e| h[e] > 0 && h[e] -= 1 }
  end
end

这种方法类似于Array#-，不同之处可通过以下示例进行说明：

a = [3,1,2,3,4,3,2,2,4]
b = [2,3,4,4,3,4]

a - b              #=> [1]
c = a.difference b #=> [1, 3, 2, 2] 

如您所见，a 包含三个 3，而 b 包含两个 3，因此在构建 c 时将删除 a 中的前两个 3（a 不会发生变化）。当 b 中包含的某个元素至少与 a 中的实例数相同时，c 将不包含该元素的任何实例。要从 a 的末尾开始删除元素：

a.reverse.difference(b).reverse #=> [3, 1, 2, 2]

Array#difference! 可以按照显而易见的方式进行定义。

我已经发现了许多使用这种方法的例子：这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里, 这里和这里。

我建议将这种方法添加到Ruby核心。

当与Array#-一起使用时，该方法使得从数组a中提取唯一元素变得容易：

a = [1,3,2,4,3,4]
u = a.uniq          #=> [1, 2, 3, 4]
u - a.difference(u) #=> [1, 2]

这个有效是因为：

a.difference(u)     #=> [3,4]    

包含 a 中所有非唯一元素（每个可能出现多次）。

问题在于

代码

class Array
  def uniq_elements(&prc)
    prc ||= ->(e) { e }
    a = map { |e| prc[e] }
    u = a.uniq
    uniques = u - a.difference(u)
    select { |e| uniques.include?(prc[e]) ? (uniques.delete(e); true) : false }
  end
end

例子

t = [1,2,2,3,4,4,5,6,7,7,8,9,9,9]
t.uniq_elements
  #=> [1,3,5,6,8]

t = [1.0, 1.1, 2.0, 3.0, 3.4, 4.0, 4.2, 5.1, 5.7, 6.1, 6.2]
t.uniq_elements { |z| z.round }
  # => [2.0, 5.1]

- Cary Swoveland

Answer 2

这里还有另外一种方法。

代码：

require 'set'

class Array
  def uniq_elements(&prc)
    prc ||= ->(e) { e }
    uniques, dups = {}, Set.new
    each do |e|
      k = prc[e]
      ((uniques.key?(k)) ? (dups << k; uniques.delete(k)) :
          uniques[k] = e) unless dups.include?(k)
    end
    uniques.values
  end
end

示例

t = [1,2,2,3,4,4,5,6,7,7,8,9,9,9]
t.uniq_elements #=> [1,3,5,6,8]

t = [1.0, 1.1, 2.0, 3.0, 3.4, 4.0, 4.2, 5.1, 5.7, 6.1, 6.2]
t.uniq_elements { |z| z.round } # => [2.0, 5.1]

解释

• 如果使用块调用uniq_elements，则块作为Proc prc 接收。
• 如果未使用块调用uniq_elements，则prc为nil，因此该方法的第一条语句将prc设置为默认的Proc（lambda）。
• 一个最初为空的哈希表uniques包含唯一值的表示。这些值是数组self的唯一值，键是当传递数组值并调用Proc prc时返回的内容：k = prc[e]。
• 集合dups包含找到的不唯一数组元素。 它是一组（而不是一个数组），以加速查找。或者，它可以是一个具有非唯一值作为键和任意值的哈希表。
• 对于数组self的每个元素e执行以下步骤：
• 计算k = prc[e]。
• 如果dups包含k，则e是重复项，因此不需要进行其他操作；否则
• 如果uniques有一个键k，则e是重复项，因此将k添加到集合dups中，并从uniques中删除带有键k的元素；否则
• 将元素k => e作为候选唯一元素添加到uniques中。
• 返回unique的值。

- Cary Swoveland

---

谢谢，我一直使用这种方法，但它无法接收一个块：def uelements(a) t=a.sort u=[] u.push t1[0] if t1[0] != t1[1] for i in 1..t.size-2 do u.push t[i] if t[i] != t[i+1] && t[i] != t[i-1] end u.push t[-1] if t[-2] != t[-1] return u end - Konstantin

Answer 3

class Array
  def uniq_elements
    counts = Hash.new(0)

    arr = map do |orig_val|
      converted_val =  block_given? ? (yield orig_val) : orig_val
      counts[converted_val] += 1
      [converted_val, orig_val]
    end

    uniques = []

    arr.each do |(converted_val, orig_val)|
      uniques << orig_val if counts[converted_val] == 1
    end

    uniques
  end
end

t=[1,2,2,3,4,4,5,6,7,7,8,9,9,9]
p t.uniq_elements

t=[1.0, 1.1, 2.0, 3.0, 3.4, 4.0, 4.2, 5.1, 5.7, 6.1, 6.2]
p  t.uniq_elements { |elmt| elmt.round }

--output:--
[1, 3, 5, 6, 8]
[2.0, 5.1]

Array#uniq并不是用来查找非重复元素的，而是用来删除重复元素的。

- 7stud

---

在map块之后，考虑使用arr.each_with_object([]) do |(converted_val, orig_val),uniques|...end。 - Cary Swoveland

Answer 4

使用 Enumerable#tally：

class Array
  def uniq_elements
    tally.select { |_obj, nb| nb == 1 }.keys
  end
end

t=[1,2,2,3,4,4,5,6,7,7,8,9,9,9]
t.uniq_elements # => [1,3,5,6,8]

如果你使用的是 Ruby < 2.7，你可以通过 backports gem 获取 tally。

require 'backports/2.7.0/enumerable/tally'

- Marc-André Lafortune

Answer 5

1. 创建和调用默认的proc是浪费时间的。
2. 使用复杂的结构将所有内容挤在一行中并不会使代码更高效，反而会使代码更难理解。
3. 在require语句中，Ruby程序员不会将文件名大写。

....

require 'set'

class Array
  def uniq_elements
    uniques = {}
    dups = Set.new

    each do |orig_val|
      converted_val =  block_given? ? (yield orig_val) : orig_val
      next if dups.include? converted_val 

      if uniques.include?(converted_val)  
        uniques.delete(converted_val)
        dups << converted_val
      else
        uniques[converted_val] = orig_val
      end
    end

    uniques.values
  end
end


t=[1,2,2,3,4,4,5,6,7,7,8,9,9,9]
p t.uniq_elements

t=[1.0, 1.1, 2.0, 3.0, 3.4, 4.0, 4.2, 5.1, 5.7, 6.1, 6.2]

p  t.uniq_elements {|elmt|
  elmt.round
}

--output:--
[1, 3, 5, 6, 8]
[2.0, 5.1]

- 7stud

---

谢谢，7。一开始我使用的是 next if...，就像你建议的那样，但后来改成了 unless，因为代码很短，不过 next 或许更易读。我更喜欢使用 proc，部分原因是 unique_elements(&prc) 可以立刻告诉读者可能正在传递参数，第一行代码也有所说明；如果只用裸露的 unique_elements，可能会给读者误解，直到看到 yield 为止。我把 set 改成了小写。 - Cary Swoveland

我更喜欢使用proc，因为它可以立即告诉读者可能正在传递参数。但是，Ruby的语法允许您在不指定参数的情况下将一个方法传递到另一个方法中。此外，无谓的方法调用并不是免费的。 "switched to unless" 我遵循“Perl最佳实践”关于unless的建议-这是一种可憎的写法。无论如何，使用仅对数组进行单次遍历的好方法。 - 7stud

Answer 6

class Array
  def uniq_elements
    zip( block_given? ? map { |e| yield e } : self )
      .each_with_object Hash.new do |(e, v), h| h[v] = h[v].nil? ? [e] : false end
      .values.reject( &:! ).map &:first
  end
end

[1,2,2,3,4,4,5,6,7,7,8,9,9,9].uniq_elements #=> [1, 3, 5, 6, 8]
[1.0, 1.1, 2.0, 3.0, 3.4, 4.0, 4.2, 5.1, 5.7, 6.1, 6.2].uniq_elements &:round #=> [2.0, 5.1]

- Boris Stitnicky

---

不需要使用each_with_index()函数，你可以每次插入1。另外请注意：虽然你只需遍历数组两次（最小次数），但之后还需要调用keys()函数。 - 7stud

现在摆脱你的哈希表，改用Hash.new(0)；没有必要创建那么多数组。 - 7stud

我在你写评论之前就已经做过了，但还是感谢你的关注。 - Boris Stitnicky

是啊，但我第一次阅读您的帖子时就在考虑这个问题！我仍然认为我的更有效率...如果没有块给出，那你巧妙地规避了map()调用。但是，您的代码与舍入示例不兼容，因为您没有保留原始值和转换后值之间的映射关系。 - 7stud