如何从数组中删除另一个数组中指定索引位置的元素

Question

我有两个数组，一个是数据，一个是索引。我想知道是否有一些好的方法可以在给定 indexes 的位置上删除 data 中的元素。我可以进行简单的迭代，但我想知道最短的方法是什么：

data = ['a','b','c','a','b','c','a','b','c']
indexes = [2,5,8]

//some code here

当数组索引中的数字与 data 中的索引数字重合时，会导致 data 中的元素丢失。正确的表达应该是这样的：

['a','b','a','b','a','b']

- Muhammad Umer

---

我们在这里删除所有的 c 只是巧合吗？ - Anthony

是的，这就是演示。 - Muhammad Umer

投票：是否应该将Array＃delete_at从delete_at（i）更改为delete_at（* i）？ - Cary Swoveland

Answer 1

data.values_at(*data.each_index.to_a - indexes)
# => ["a", "b", "a", "b", "a", "b"]

- sawa

---

没有人能找到比这更好的解决方案。非常棒的答案。 - Arup Rakshit

这实际上是完美的。 - ndnenkov

Answer 2

我将按照以下步骤进行：

data = ['a','b','c','a','b','c','a','b','c']
indexes = [2,5,8]
data.values_at(*(0...data.size).to_a - indexes)
# => ["a", "b", "a", "b", "a", "b"]

- Arup Rakshit

---

@sawa 我很高兴我们有相同的想法... :) 但你更快。 - Arup Rakshit

这是一个非常好的答案，但需要注意的是，在幕后，数组减法使用迭代。 - Devon Parsons

Answer 3

不进行迭代似乎是一个很好的目标，但是正确地执行迭代将会非常快。

基准测试很重要：

require 'benchmark'

DATA = ['a','b','c','a','b','c','a','b','c']
INDEXES = [2,5,8]

def ttm(data)
  d2 = data.dup
  INDEXES.sort.reverse.each{ |i| d2.delete_at(i) }
  d2
end

def devon_parsons(data)
  new_data = data.each_with_index.reject do |value,index|
    INDEXES.include? index
  end.map(&:first)
  new_data
end

def arup_rakshit(data)
  data.values_at(*(0...data.size).to_a - INDEXES)
end

def sawa(data)
  data.values_at(*data.each_index.to_a - INDEXES)
end

确保进行比较的是同等条件下的测试：

ttm(DATA)           # => ["a", "b", "a", "b", "a", "b"]
devon_parsons(DATA) # => ["a", "b", "a", "b", "a", "b"]
arup_rakshit(DATA)  # => ["a", "b", "a", "b", "a", "b"]
sawa(DATA)          # => ["a", "b", "a", "b", "a", "b"]

运行基准测试：

n = 100_000 
Benchmark.bm(13) do |b|
  b.report('ttm:')          { n.times { ttm(DATA)           } }
  b.report('devon_parsons') { n.times { devon_parsons(DATA) } }
  b.report('arup_rakshit')  { n.times { arup_rakshit(DATA)  } }
  b.report('sawa')          { n.times { sawa(DATA)          } }
end

这导致：

# >>                     user     system      total        real
# >> ttm:            0.130000   0.000000   0.130000 (  0.127559)
# >> devon_parsons   0.530000   0.000000   0.530000 (  0.535929)
# >> arup_rakshit    0.250000   0.000000   0.250000 (  0.255295)
# >> sawa            0.300000   0.010000   0.310000 (  0.305376)

如果数据量增加:

DATA2 = DATA * 100
Benchmark.bm(13) do |b|
  b.report('ttm:')          { n.times { ttm(DATA2)           } }
  b.report('devon_parsons') { n.times { devon_parsons(DATA2) } }
  b.report('arup_rakshit')  { n.times { arup_rakshit(DATA2)  } }
  b.report('sawa')          { n.times { sawa(DATA2)          } }
end

结果真的变了：

# >>                     user     system      total        real
# >> ttm:            0.320000   0.090000   0.410000 (  0.420074)
# >> devon_parsons  39.170000   0.080000  39.250000 ( 39.265062)
# >> arup_rakshit    9.950000   0.010000   9.960000 (  9.975699)
# >> sawa            9.940000   0.020000   9.960000 (  9.959036)

当数组大小发生变化时，测试其运行情况非常重要。在小数组上运行良好的代码可能会随着数组增长而变得明显缓慢。而且，往往看起来很酷的做法实际上因为存在隐藏成本而非常慢。基准测试可以帮助我们找出这些问题。

注意：使用 sort.reverse 非常重要。如果没有这些内容，数组将被破坏。

---

可以进一步改进 sort 方法，使用 sort_by(&:itself)

require 'benchmark'

array = (0..99).to_a.shuffle
n = 100_000 

Benchmark.bm(7) do |b|
  b.report('sort:')    { n.times { array.sort              } }
  b.report('sort_by:') { n.times { array.sort_by(&:itself) } }
end

导致：

              user     system      total        real
sort:     0.460000   0.010000   0.470000 (  0.480236)
sort_by:  3.600000   0.030000   3.630000 (  3.627871)

增加数组大小：

array = (0..999).to_a.shuffle
Benchmark.bm(13) do |b|
  b.report('sort:')    { n.times { array.sort              } }
  b.report('sort_by:') { n.times { array.sort_by(&:itself) } }
end

导致：

                    user     system      total        real
sort:           9.520000   0.120000   9.640000 (  9.659246)
sort_by:       53.530000   0.720000  54.250000 ( 54.321285)

- the Tin Man

---

启发性的。谢谢！ - Wand Maker

我有一个解决方案，它似乎表现更好 - 它真的更好还是偶然的？ - Wand Maker

告诉你我的时间复杂度是N的平方:P - Devon Parsons

如果你只关心性能，sort 可以进一步改进为 sort_by(&:itself)。 - sawa

当比较基本对象（如数字）时，“sort”比“sort_by”运行速度更快。请参见添加的基准测试。 - the Tin Man

Answer 4

new_data = data.each_with_index.reject do |value,index|
  indexes.include? index
end.map(&:first)

新的回答这次确实有效 - 它运行在O(n^2)时间复杂度，我没有找到不迭代索引的方法。

- Devon Parsons

Answer 5

这是我的解决方案：

data = ['a','b','c','a','b','c','a','b','c']
indexes = [2,5,8]

updated_data = data.dup
indexes.each { |i| updated_data[i] = nil}
updated_data.compact!
p updated_data # Prints ["a", "b", "a", "b", "a", "b"]

就基准测试而言，使用 Tin Man 的代码似乎表现最佳。不确定是否与 indexes 数组的小尺寸有关。

                    user     system      total        real
ttm:            0.125000   0.000000   0.125000 (  0.113075)
devon_parsons   0.484000   0.000000   0.484000 (  0.491327)
arup_rakshit    0.219000   0.000000   0.219000 (  0.221149)
sawa            0.250000   0.000000   0.250000 (  0.253168)
wandmaker       0.094000   0.016000   0.110000 (  0.095063)

# Run 2 with larger data
                    user     system      total        real
ttm:            0.422000   0.188000   0.610000 (  0.596413)
devon_parsons  39.328000   0.000000  39.328000 ( 39.489394)
arup_rakshit   10.078000   0.562000  10.640000 ( 10.644099)
sawa           10.219000   0.110000  10.329000 ( 10.328250)
wandmaker       0.359000   0.062000   0.421000 (  0.423282)

- Wand Maker

---

如果OPs数组包含了重要的nil值，那该怎么办？你会删除掉indexes未指定的数据。你需要编写代码来防范这种情况。 - the Tin Man

@theTinMan 是的，那很有道理。 - Wand Maker