1
votes

Comment renvoyer des correspondances et des non-correspondances lors de la comparaison de deux plages / tableaux

J'essaie de renvoyer un décompte du nombre total d'entrées correspondantes et non correspondantes dans un ensemble de deux plages.

J'essaye d'éviter de boucler deux fois sur le tableau comme ceci:

#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

ruby

5 commentaires

Pas besoin de préfixer votre titre avec "Ruby -"; c'est à cela que servent les balises.

Utilisez les + et - intégrés? Ou un ensemble?

S'il ne s'agit que de deux plages, comparez leurs débuts et leurs fins. Vous n'avez pas du tout besoin de les itérer

J'évite d'utiliser + / - dans le cas où la plage d'échantillons est inférieure à la plage constante

Vous utilisez le post-incrémentation ++ , mais Ruby ne le prend pas en charge. Utilisez plutôt + = 1 .

3 Réponses :

1
votes

Vous pouvez utiliser - (différence) dans Ruby:

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

puts (sample_range - constant_range).count # 55

3 commentaires

Ces cas ne couvrent pas la possibilité lorsque la plage d'échantillons est sample_range = (1..180) .to_a

je veux dire utiliser une logique comme - & | i exemple pour un

Il est extrêmement inefficace de convertir les plages en tableaux.

1
votes

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

1 commentaires

Il est extrêmement inefficace de convertir les plages en tableaux.

4
votes

Je ne sais pas si c'est entièrement votre cas, mais si ce sont toujours des plages de nombres avec un intervalle de 1 et non un tableau arbitraire, la solution peut être optimisée à O (1), contrairement aux autres méthodes utilisant to_a qui sont au moins O (n). En d'autres termes, si vous avez une GRANDE plage, ces solutions de tableau s'étoufferaient mal.

En supposant que vous utiliserez toujours une plage croissante de nombres avec un intervalle de 1, cela signifie que vous pouvez les compter simplement en utilisant size ( count serait notre ennemi dans cette situation).

Cela dit, en utilisant des mathématiques simples, vous pouvez d'abord vérifier si les plages peuvent se croiser, sinon, renvoyez simplement 0. Sinon, vous pouvez enfin calculer le nouvel intervalle de plage et obtenir sa taille.

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

Cela comptera le nombre d'éléments qui se croisent dans deux plages dans O (1 ). Vous pouvez tester ce code avec quelque chose comme

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

, puis essayer la même entrée avec les autres méthodes et regarder votre programme se bloquer.

La solution finale serait ressemble à quelque chose comme ceci:

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

1 commentaires

Je simplifierais sample_range.last - sample_range.first + 1 en sample_range.size