Ruby

Question

'daki bir dizideki diğer öğelerin tüm alt dizelerini silmek için etkin bir dizi eldeki yerinde düzenleme karmaşık bir sorunum var. Bazı öğelerin diğer öğelerin alt dizeleri olduğu bir dizi var. Tüm alt dizeleri silmek ve yalnızca üst dizeleri/dizeleri tutmak istiyorum. yani Dizi işleminden sonra =>['1', '1 1', '1 1 1', '1 1 1 2', '1 2 3 1', '1 2', '2 3'] bir dezenfekte dizi =>['1 1 1 2', '1 2 3 1']

aynı ulaşmak için etkili bir algoritma var olmalıdır?

Answer 1

Daha az bellek kullanır, daha az hesaplama yapar. Bu, her iki yolla alt dizeleri silecek, döngü daha az olacaktır. Yukarıdaki bağlamda getirdi

   user  system  total  real 
    First 0.000000 0.000000 0.000000 ( 0.000076) 
    Second 0.010000 0.000000 0.010000 ( 0.000037) 
    Third 0.000000 0.000000 0.000000 ( 0.000019) 

(Birinci ve İkinci) ve bu bir (Üçüncü) Yukarıda belirtilen 2 algos için test sonuçları olduğunu.

array = ['1 1 1', '1', '1 1', '1 1 1 2', '1 2 3 1', '1 2', '2 3', '1 2 3', '1 1 1'] 

i1 = 0 
arr_len = array.length 
last_index = arr_len - 1 

while i1 <= last_index 
    w1 = array[i1] 
    i2 = i1 + 1 
    while i2 <= last_index 
    w2 = array[i2] 
    # If w2 is a subset of w1 
    if w1.include? w2 
     # Delete from index i2 
     array.delete_at(i2) 
     # Decrement the array_length as one element is deleted 
     arr_len -= 1 
     # Decrement last index, as one element is deleted 
     last_index -= 1 
     next 
    end 
    # If w1 comes out to be a subset of w2 
    if w2.include? w1 
     # Delete the value from that index 
     array.delete_at(i1) 
     # Decrement the array_length as one element is deleted 
     arr_len -= 1 
     # Decrement last index, as one element is deleted 
     last_index -= 1 
     # Reset value of w1 as it is deleted in this operation 
     w1 = array[i1] 
     # Reset index of 2nd loop to start matching again 
     i2 = i1 + 1 
     # Move next from here only 
     next 
    end 
    i2 += 1 
    end 
    i1 += 1 
end 

Answer 2

Bu yaklaşım, diziden kendini kaldırmak için bazı dizi matematik kullanır ve sonra bir alt dizgi olarak görünüp görünmediğini denetler. Bunun ne kadar iyi olduğu hakkında hiçbir fikrim yok. Eğer bir alt dize biraz daha hızlı daha sonraki kontroller yaparak bulundu edilir senin dizi her zaman kısaltarak olarak, performansı artırmak olarak

a = ['1', '1 1', '1 1 1', '1 1 1 2', '1 2 3 1', '1 2', '2 3'] 
a.uniq.delete_if { |i| (a-[i]).any? {|j| j.include? i } } 

Bir delete_if kullanarak değiştirildi.

GÜNCELLEME: Cary Swoveland, dizi çoğaltmaları içerdiğinde bir sorun bulundu. Bir dizgeyi tekrarlamak için bir uniq ekledim, ancak bir öğe tekrarlanırsa ne olması gerektiği net değil, her ikisi de birbirinin alt dizeleri olduğundan kaldırılmalı mı? Bu sorunu, kopyaların çıktıda sadece bir öğe ile sonuçlandığı varsayımıyla çözdüm, ancak bu yanlış olabilir.

Answer 3

Burada olduğu gibi alt dizeleri kaldıran bir yol.

a = ['1', '1 1', '1 1 1', '1 1 1 2', '1 2 3 1', '1 2', '2 3'] 

b = a.dup 
b.size.times do 
    first, *rest = b 
    (rest.any? { |t| t.include? first }) ? b.shift : b.rotate! 
end 
b #=> ["1 1 1 2", "1 2 3 1"] 

, neler olduğunu görmek first,*rest = b sonra

puts "first=\"#{first}\n, rest=#{rest}" 

eklemek için. Bu, aşağıdakileri basar (yeniden biçimlendirmeden önce).

first="1",  rest=["1 1", "1 1 1", "1 1 1 2", "1 2 3 1", "1 2", "2 3"] 
first="1 1",  rest=["1 1 1", "1 1 1 2", "1 2 3 1", "1 2", "2 3"] 
first="1 1 1", rest=["1 1 1 2", "1 2 3 1", "1 2", "2 3"] 
first="1 1 1 2", rest=["1 2 3 1", "1 2", "2 3"] 
first="1 2 3 1", rest=["1 2", "2 3", "1 1 1 2"] 
first="1 2",  rest=["2 3", "1 1 1 2", "1 2 3 1"] 
first="2 3",  rest=["1 1 1 2", "1 2 3 1"]