(Rubin) Wenn der Array Kreuzungsoperator (&) ineffizient ist, warum ist es verfügbar?

Question

Ich fragte eine

War es hilfreich?

einreichen

Lösung

& ist keine besonders ineffiziente Methode. Ich denke, dass Sie die Kritik an der akzeptierten Antwort falsch verstanden.

Ihre bevorzugte Lösung ist ineffizient, da es um die Bereiche zu Arrays umwandelt.

Eine Reihe wie 1..10000 hat einen relativ geringen Speicherbedarf - es speichert nur die Start- und Endpunkte. Aber wenn man es in ein Array umwandeln, weisen Sie Speicher für alle 10.000 Einträge.

Answer 1

& ist keine besonders ineffiziente Methode. Ich denke, dass Sie die Kritik an der akzeptierten Antwort falsch verstanden.

Ihre bevorzugte Lösung ist ineffizient, da es um die Bereiche zu Arrays umwandelt.

Eine Reihe wie 1..10000 hat einen relativ geringen Speicherbedarf - es speichert nur die Start- und Endpunkte. Aber wenn man es in ein Array umwandeln, weisen Sie Speicher für alle 10.000 Einträge.

Answer 2

Der gestrige Frage des Wortlauts machte es klingen wie Sie einen binären Zustand der Berechnung wurden: Sie überlappen diese Bereiche? Die Antworten, die gegeben wurden, kann in konstanter Zeit berechnet werden, so dass, wenn sie für Sie arbeiten, ist es sinnvoll, mit ihnen zu halten macht.

Der Operator & angemessen wäre, wenn Sie wissen müssen, um die Ausdehnung der Überlappung, aber das war nicht das, was Sie fragen.

Was, warum es überhaupt existiert, kann ich nur spekulieren: Es ist nicht nur Bequemlichkeit hinzufügt, aber es ist nicht schwer, Wege, sich vorzustellen, in dem ein Array Konjunktionsoperation durch die Sprachumgebung optimiert werden kann - auch wenn seine Berechnung könnte noch benötigen lineare oder n * log (n) Zeit in den schlimmsten Fällen. (Wenn jeder Betrieb ein konstantes Zeitergebnis haben hat, würden wir ganz von einem paar Methoden loswerden müssen!)

Answer 3

Arrays in Ruby sind nicht typisiert: sie eine Mischung von Typen einschließlich Hashes, andere Arrays enthalten können, Symbole, was auch immer. In einer typisierten Array Sortierung und Vergleich ist viel einfacher. Vergleicht man untypisierten Sammlungen (insbesondere Sammlungen Sammlungen enthalten) ist teurer durch die Natur.

Answer 4

Es scheint nicht so schlecht in Bezug auf einen Test. Maschine war i7 (2,0 GHz 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)