(Ruby) Если оператор пересечения массива (&) неэффективен, почему он доступен?

Question

Вчера я задал вопрос о сравнении диапазонов перекрытия и с тех пор он застрял у меня в горле.

Похоже, консенсус заключается в том, что мой предпочтительный ответ, который предполагает использование оператора пересечения массивов (&), неэффективен, поскольку сравнение массивов является дорогостоящим.

Интересно, почему эта функция на языке? Может быть, создатели языка считают, что иногда вам нужен элегантный способ найти решение, даже если это дорого? Является ли сравнение массивов настолько дорогостоящим, что вам следует избегать его, когда это возможно? Вся привлекательность Ruby для меня - это сосредоточенность на синтаксической элегантности над преждевременной оптимизацией.

Answer 1

& не является особенно неэффективным методом. Я думаю, вы неправильно поняли критику принятого ответа.

Ваше предпочтительное решение неэффективно, поскольку оно преобразует диапазоны в массивы.

Диапазон, такой как 1..10000, имеет относительно небольшой объем памяти - он хранит только начальную и конечную точки. Но если вы преобразуете его в массив, вы выделяете память для всех 10 000 записей.

Answer 2

Вчерашняя формулировка вопроса выглядела так, как будто вы вычисляли двоичное условие: перекрываются ли эти диапазоны? Ответы, которые были даны, могут быть вычислены в постоянное время, поэтому, если они работают на вас, имеет смысл придерживаться их.

Оператор & подойдет, если вам нужно знать экстент перекрытия, но это не то, о чем вы спрашивали.

Что касается того, почему он вообще существует, я могу только предположить: он не только добавляет удобства, но и не представляет сложностей представить способы, с помощью которых операция соединения с массивом может быть оптимизирована языковой средой - даже если ее вычисления могут по-прежнему требуется линейное или n * log (n) время в худших случаях. (Если каждая операция должна иметь результат с постоянным временем, нам нужно избавиться от множества методов!)

Answer 3

Это не так уж плохо с точки зрения теста. Машина была i7 (2,0 ГГц двухъядерный)

#!/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)

Answer 4

Массивы в Ruby не типизированы: они могут содержать смесь типов, включая хэши, другие массивы, символы, что угодно. В типизированном массиве сортировка и сравнение намного проще. Сравнение нетипизированных коллекций (особенно коллекций, содержащих коллекции) по своей природе более затратно.