Как сортировка Array # в Ruby такая быстрая?

Question

C # имеет BitArray, C имеет битовые поля .. Я не смог найти эквивалент в ядре Ruby. Google показал мне BitField класс, который Питер Купер написал для того же.

Я читал «Программирование жемчуга» Джона Бентли и, пока пробовал один из первых примеров, который касается сортировки BitMap, - мне нужен был тип, представляющий собой массив битов. Я использовал класс Питера

class BitMapSort
  def self.sort(list, value_range_max)
    bitmap = BitField.new(value_range_max)

    list.each{|x| bitmap[x] = 1 }

    sorted_list = []
    0.upto(value_range_max-1){ |number|
      sorted_list << number if (bitmap[number] == 1)
    }
    sorted_list
  end
end

Выполнение этого для набора из 1М уникальных чисел в диапазоне [0, 10 000 000) дало некоторые интересные результаты,

                         user     system      total        real
bitmap               11.078000   0.015000  11.093000 ( 11.156250)
ruby-system-sort      0.531000   0.000000   0.531000 (  0.531250)
quick-sort           21.562000   0.000000  21.562000 ( 21.625000)

Benchmark.bm(20){|x|
    x.report("bitmap"){ ret = BitMapSort.sort(series, 10_000_000);}
    x.report("ruby-system-sort"){ ret = series.sort; }
    x.report("quick-sort"){ ret = QuickSort.sort( series, 0, series.length-1); }
    }

Как сортировка по умолчанию в ruby ​​в 22 раза быстрее, чем 1M BitField.set + 1 цикл по 10M битовому вектору? Есть ли в Ruby более эффективное битовое поле / массив? Как сортировка по умолчанию в Ruby позволяет достичь такого уровня производительности ... Неужели это происходит в C, чтобы это сделать?

Answer 1

Array # sort реализован на C, см. rb_ary_sort в array.c

Также имеется несколько проверок для сравнения Fixnums, поэтому сортировка массиваЦелые числа даже не нуждаются в поиске методов.

Answer 2

Как сортировка по умолчанию в Ruby позволяет достичь такого уровня производительности ... Он прыгает в C, чтобы это сделать?

Все базовые классы и методы в стандартной реализации ruby ​​реализованы на C.

Answer 3

Прыжок в C абсолютно правильный. Array и Hash имеют реализации C многих методов для повышения производительности. Целочисленные и плавающие литералы также имеют некоторые хитрые оптимизации кода. Когда вы конвертируете их в растровое изображение, вы также теряете эту оптимизацию.

Скомпилированный язык, такой как C или Java, действительно имеет смысл искать хитрые шаблоны оптимизации. с интерпретируемыми языками стоимость интерпретации каждой команды делает это контрпродуктивным.

Answer 4

Я думаю, что реальная проблема здесь в том, что вы выполняете 10M сравнений, 10M выборок массивов, 10M множества вещей, в то время как правильно оптимизированная процедура сортировки выполняет намного меньше операций, так как работает с фиксированным набором 1M элементов. .

Базовые операции, такие как сортировка, высоко оптимизированы в виртуальной машине Ruby, и их трудно превзойти с помощью альтернативы Ruby.

Answer 5

Причина, по которой он намного быстрее, возможно, в том, что он реализован в реализации ruby ​​в C.