(Vermiglio) Se l'operatore matrice intersezione (e) è inefficiente, perché è disponibile?

Question

Ho chiesto a un > ieri sul confronto gamme per la sovrapposizione e il suo stato bloccato in gola da allora.

Il consenso sembra essere che la mia risposta preferita che prevede usando l'operatore matrice intersezione (e), è inefficiente perché confrontando array è costosa.

Mi chiedo allora, perché questa caratteristica è nel linguaggio? Potrebbe essere che i creatori della lingua credevano che a volte è necessario un modo elegante per raggiungere una soluzione, anche se è costoso da fare così? È confrontare le matrici così costosi che si dovrebbe evitare, quando possibile? L'intero attrazione di Ruby per me è l'attenzione per l'eleganza sintattico sopra ottimizzazione prematura.

Answer 1

& non è un metodo particolarmente inefficiente. Penso che tu frainteso la critica alla risposta accettata.

La soluzione preferita è inefficiente perché converte le gamme agli array.

Una gamma così come 1..10000 ha una relativamente piccola orma di memoria - si memorizza solo i punti di inizio e di fine. Ma se si converte a un array, si alloca la memoria per tutti i 10.000 voci.

Answer 2

formulazione della domanda di ieri ha reso il suono come se stessi calcolare una condizione binaria: fanno questi intervalli si sovrappongono? Le risposte che sono state date può essere calcolato in tempo costante, in modo da se lavorano per voi, ha senso restare con loro.

L'operatore & sarebbe appropriato se avete bisogno di sapere il misura della sovrapposizione, ma che non era quello che stavi chiedendo circa.

Per quanto riguarda il motivo per cui esiste, posso solo fare delle ipotesi: Non solo aggiungere la convenienza, ma non è difficile immaginare i modi in cui un'operazione di matrice congiunzione potrebbe essere ottimizzata con l'ambiente di lingua - anche se il suo calcolo potrebbe richiedono ancora lineare o n * log (n) nel peggiore dei casi. (Se ogni operazione deve avere un risultato costante di tempo, avremmo dovuto sbarazzarsi di alcuni metodi abbastanza!)

Answer 3

Gli array in Ruby sono senza tipo: possono contenere una combinazione di tipi tra cui hash, altri array, simboli, qualsiasi cosa. In un array tipizzato l'ordinamento e il confronto è molto più semplice. Confrontando collezioni tipizzati (specialmente raccolte contenenti raccolte) risulta più costosa per natura.

Answer 4

Non sembra troppo male in termini di un test. Macchina era i7 (2.0Ghz dual core)

#!/bin/ruby
require 'benchmark'
n = []
1.upto(10_000_000) do |i|
  n << i
end

m = Array.new(1000000){ rand(10_000_000)+1 }

Benchmark.bm(10) do |x|
  x.report('array_intersection'){ n & m }
end

---

                    user     system      total        real
array_intersection  2.870000   0.040000   2.910000 (  2.895202)