Самый длинный общий префикс и суффикс массивов
Каков наилучший способ получить самый длинный общий префикс (подмассив, который начинается с индекса 0 оригинала) и суффикс (подмассив, который заканчивается индексом -1 оригинала) из двух массивов? Например, даны два массива:
[:foo, 1, :foo, 0, nil, :bar, "baz", false]
[:foo, 1, :foo, 0, true, :bar, false]
самый длинный общий префикс этих массивов:
[:foo, 1, :foo, 0]
и самый длинный общий суффикс этих массивов:
[false]
Когда элементы с индексом 0/-1 отличаются в исходных массивах, тогда общий префикс / суффикс должен быть пустым массивом.
5 ответов
Одно из возможных решений:
a1 = [:foo, 1, 0, nil, :bar, "baz", false]
a2 = [:foo, 1, 0, true, :bar, false]
a1.zip(a2).take_while { |x, y| x == y }.map(&:first)
#=> [:foo, 1, 0]
Обращение входных массивов и выходного массива находит общий суффикс:
a1.reverse.zip(a2.reverse).take_while { |x, y| x == y }.map(&:first).reverse
#=> [false]
Край случае: zip заполняет массивы аргументов nil ценности:
a1 = [true, nil, nil]
a2 = [true]
a1.zip(a2).take_while { |x, y| x == y }.map(&:first)
#=> [true, nil, nil]
Этого можно избежать путем усечения исходного массива до длины второго массива:
a1[0...a2.size].zip(a2).take_while { |x, y| x == y }.map(&:first)
Другое решение без крайнего случая:
a1 = [:foo, 1, 0, nil, :bar, "baz", false]
a2 = [:foo, 1, 0, true, :bar, false]
a1.take_while.with_index {|v,i| a2.size > i && v == a2[i] }
РЕДАКТИРОВАТЬ: Улучшенная производительность
class Array
def common_prefix_with(other)
other_size = other.size
take_while.with_index {|v,i| other_size > i && v == other[i] }
end
end
a1.common_prefix_with a2
Господа, запускайте свои двигатели!
Методы проверены
Я протестировал второй метод, данный @stefan, оба метода, предложенные @BroiSatse, и три метода, которые я предложил.
class Array #for broiSatse2
def common_prefix_with(other)
other_size = other.size
take_while.with_index {|v,i| other_size > i && v == other[i] }
end
end
class Cars
def self.stefan(a1,a2)
a1[0...a2.size].zip(a2).take_while { |x, y| x == y }.map(&:first)
end
def self.broiSatse1(a1,a2)
a1.take_while.with_index {|v,i| a2.size > i && v == a2[i] }
end
def self.broiSatse2(a1,a2)
a1.common_prefix_with(a2)
end
def self.cary1(a,b)
a[0,b.size].take_while.with_index { |e,i| e == b[i] }
end
def self.cary2(a,b)
any, arr = a.zip(b).chunk { |e,f| e==f }.first
any ? arr.map(&:first) : []
end
def self.cary3(a,b)
a[0,(0..[a.size, b.size].min).max_by { |n| (a[0,n]==b[0,n]) ? n : -1 }]
end
end
Я не включил решение, данное @6ftDan (не путать с 5' Dan или 7' Dan), потому что оно не прошло все тесты.
Построение тестовых массивов
random_arrays(n) создает одну пару массивов. n это размер меньшего из двух. Чем больше размер n+1,
def random_arrays(n)
m = rand(n)
# make arrays the same for the first m elements
a = Array.new(m,0)
b = Array.new(m,0)
if m < n
# make the m+1 elements different
a << 0
b << 1
# randomly assign 0s and 1a to the remaining elements
(n-m-1).times { a << rand(2); b << rand(2) } if m < n - 1
end
# make arrays unequal in length
(rand(2) == 0) ? a << 0 : b << 0
[a,b]
end
Подтвердите, что протестированные методы дают идентичные результаты
N = 10000 #size of smaller of two input arrays
methods = Cars.methods(false)
# ensure are methods produce the same results and that
# all deal with edge cases properly
20.times do |i|
test = case i
when 0 then [[0,1],[1,1]]
when 1 then [[0],[]]
when 1 then [[0,0,0],[0,0]]
else
random_arrays(N)
end
soln = Cars.send(methods.first, *test)
methods[1..-1].each do |m|
unless soln == Cars.send(m, *test)
puts "#{m} has incorrect solution for #{test}"
exit
end
end
end
puts "All methods yield the same answers\n"
Бенчмаркинг
require 'benchmark'
I = 1000 #number of array pairs to test
@arr = I.times.with_object([]) { |_,a| a << random_arrays(N) } #test arrays
#test method m
def testit(m)
I.times { |i| Cars.send(m, *@arr[i]) }
end
Benchmark.bm(12) { |bm| methods.each { |m| bm.report(m) { testit(m) } } end
Результаты
All methods yield the same answers
user system total real
stefan 11.260000 0.050000 11.310000 ( 11.351626)
broiSatse1 0.860000 0.000000 0.860000 ( 0.872256)
broiSatse2 0.720000 0.010000 0.730000 ( 0.717797)
cary1 0.680000 0.000000 0.680000 ( 0.684847)
cary2 13.130000 0.040000 13.170000 ( 13.215581)
cary3 51.840000 0.120000 51.960000 ( 52.188477)
Это работает на уникальных массивах.
Префикс
x = [:foo, 1, 0, nil, :bar, "baz", false]
y = [:foo, 1, 0, true, :bar, false]
(x & y).select.with_index {|item,index| x.index(item) == index}
ВЫХОДЫ: => [:foo, 1, 0]
Запустите реверс на массивах для Affix
(x.reverse & y.reverse).select.with_index {|item,index| x.reverse.index(item) == index}
ВЫХОДЫ: => [false]
Три решения: грубое (№ 3, первоначальный ответ), лучшее (№ 2, первое редактирование) и лучшее (№ 1, вариант ответа @Stefan, второе редактирование).
a = [:foo, 1, :foo, 0, nil, :bar, "baz", false]
b = [:foo, 1, :foo, 0, true, "baz", false]
c = [:foo,1,:goo]
d = [:goo,1,:new]
Заметка b немного изменен по сравнению с примером ОП.
Если не указано иное, общий суффикс будет рассчитываться путем обращения массивов, применяя common_prefix и затем полностью изменяет результат.
# 1
Вариант ответа Стефана, который избавляет его от zip а также map (и сохраняет свою технику усечения одного массива до не более длины другого):
def common_prefix(a,b)
a[0,b.size].take_while.with_index { |e,i| e == b[i] }
end
common_prefix(a,b)
#=> [:foo, 1, :foo, 0]
common_prefix(c,d)
#=> []
# 2
def common_prefix(a,b)
any, arr = a.zip(b).chunk { |e,f| e==f }.first
any ? arr.map(&:first) : []
end
def common_suffix(a,b)
any, arr = a[a.size-b.size..-1].zip(b).chunk { |e,f| e==f }.to_a.last
any ? arr.map(&:first) : []
end
common_prefix(a,b)
#=> [:foo, 1, :foo, 0]
# Nore: any, arr = a.zip(b).chunk { |e,f| e==f }.to_a
# => [[true, [[:foo, :foo], [1, 1], [:foo, :foo], [0, 0]]],
# [false, [[nil, true], [:bar, :baz], ["baz", false], [false, nil]]]]
common_suffix(a,b)
#=> ["baz", false]
# Note: any, arr = a[a.size-b.size..-1].zip(b).chunk { |e,f| e==f }.to_a
# => [[false, [[1, :foo], [:foo, 1], [0, :foo], [nil, 0], [:bar, true]]],
# [true, [["baz", "baz"], [false, false]]]]
когда :first отправляется в перечислитель Enumerable#chunk возвращается первый элемент перечислителя. Следовательно, по эффективности он должен быть сопоставим с использованием Enumerable # take_ while.
common_prefix(c,d)
#=> []
common_suffix(c,d)
#=> []
# 3
def common_prefix(a,b)
a[0,(0..[a.size, b.size].min).max_by { |n| (a[0,n]==b[0,n]) ? n : -1 }]
end
common_prefix(a,b)
#=> [:foo, 1, :foo, 0]
common_prefix(c,d)
#=> []