Cách xóa các phần tử khỏi mảng có chỉ mục trong một mảng khác

Question

Tôi có hai mảng, một mảng có dữ liệu và một với chỉ mục. Tôi muốn biết nếu có một số cách hay để xóa các phần tử trong data tại vị trí được đưa ra trong indexes. Tôi có thể làm lặp đi lặp lại đơn giản nhưng tôi tự hỏi những gì con đường ngắn nhất là:

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

//some code here 

yếu tố trong data đã mất hết khi các chỉ số đã xảy ra trùng với số trong chỉ số mảng. Nó sẽ giống như thế này:

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

Answer 1

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

Answer 2

tôi sẽ làm như sau:

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"] 

Answer 3

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

câu trả lời mới mà thực sự hoạt động thời gian này - nó chạy trong thời gian O (n^2) và Tôi không thấy cách làm nó mà không lặp lại các chỉ mục.

Answer 4

Thực hiện nó mà không cần lặp lại có vẻ giống như một mục tiêu tốt, nhưng việc lặp lại được thực hiện ngay sẽ cực kỳ nhanh.

Điểm chuẩn rất quan trọng:

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 

Hãy chắc chắn rằng nó là một quả táo để thử nghiệm táo:

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"] 

Chạy các tiêu chuẩn:

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 

mà kết quả trong:

# >>      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) 

Nếu kích thước dữ liệu phát triển:

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 

Kết quả thực sự thay đổi:

# >>      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) 

Đó là thực sự quan trọng để kiểm tra những gì xảy ra khi thay đổi kích thước mảng. Những gì có thể chạy nhanh trên một mảng nhỏ có thể làm chậm đáng kể khi mảng phát triển. Và, thường xuyên, những gì có vẻ như một cách mát mẻ để làm một cái gì đó hóa ra là rất chậm vì có chi phí ẩn. Điểm chuẩn giúp chúng tôi tìm ra những điều này.

Lưu ý: Sử dụng sort.reverse là rất quan trọng. Nếu không có những mảng đó sẽ bị xáo trộn.

---

loại có thể tiếp tục được cải thiện để sort_by (&: bản thân)

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 

Hệ quả là:

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

Tăng kích thước mảng:

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 

Hệ quả là:

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

Answer 5

Đây là giải pháp của tôi:

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"] 

Theo như chuẩn đi, sử dụng mã Tin Man, có vẻ như để thực hiện tốt nhất. Bạn không chắc chắn liệu nó có liên quan đến kích thước nhỏ của mảng indexes hay không.

    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)