Как вернуть совпадения и не совпадения при сравнении двух диапазонов / массивов

Question

Я пытаюсь вернуть счетчик общего количества совпадающих и не совпадающих записей в наборе из двух диапазонов.

Я пытаюсь избежать зацикливания массива дважды так:

#expected output:
#inside: 421 | outside: 55

constant_range = 240..960
sample_range   = 540..1015
sample_range_a = sample_range.to_a

def generate_range
  inside = sample_range_a.select { |val| constant_range.include?(val) }.count
  outside = sample_range_a.select { |val| !constant_range.include?(val) }.count
end

# I was thinking of a counter, but thought that would be even more ineffective
def generate_range
  a = 0
  b = 0
  sample_range_a.select { |val| constant_range.include?(val) ? a++ : b++ }
end

Answer 1

Я не знаю, полностью ли это ваш случай, но если они всегда являются диапазонами чисел с интервалом 1, а не произвольным массивом, решение может быть оптимизировано до O (1), в отличие от других методов, использующих to_a по крайней мере O (n). Другими словами, если у вас есть БОЛЬШОЙ диапазон, эти решения с массивами будут сильно подавляться.

Предполагая, что вы всегда будете использовать возрастающий диапазон чисел с интервалом 1, это означает, что вы можете считать их, просто используя size (count будет нашим врагом в этой ситуации).

С учетом сказанного, используя простую математику, вы можете сначала проверить, могут ли диапазоны пересекаться, если нет, просто вернуть 0. В противном случае вы можете наконец, вычислите новый интервал диапазона и получите его размер.

def range_intersection_count(x, y)
  return 0 if x.last < y.first || y.last < x.first
  ([x.begin, y.begin].max..[x.max, y.max].min).size
end

Это будет считать количество элементов, которые пересекаются в двух диапазонах в O (1). Вы можете протестировать этот код с помощью чего-то вроде

range_intersection_count(5000000..10000000000, 3000..1000000000000)

, а затем попробовать тот же ввод с другими методами и наблюдать зависание вашей программы.

Окончательное решение будет выглядеть примерно так:

constant_range = (240..960)
sample_range   = (540..1015)

inside_count   = range_intersection_count(constant_range, sample_range) # = 421
outside_count  = sample_range.size - inside_count                       # = 55

Answer 2

constant_range = (240..960).to_a

sample_range   = (540..1015).to_a

inside_count = (sample_range & constant_range).count #inside: 421

outside_count = sample_range.count - inside_count #outside: 55

Answer 3

Вы можете использовать - (разница) в Ruby:

constant_range = (240..960).to_a
sample_range   = (540..1015).to_a

puts (sample_range - constant_range).count # 55