Как дублируется максимальный порядок функций Ruby?

Ваш пример можно упростить, используя max_by, чтобы получить аналогичный результат:

10.times{|y| p x.max_by(y) {|t| t%2}}

Я провел некоторое время с источником, но не могу найти ни одной дыры.

После того, как я увидел публикацию под названием Switch: A Deep Embedding of Queries into Ruby (диссертация Мануэля Майра) Я нашел ответ.

Где на странице 104 можно найти ответ для max_by:

... Здесь возвращается значение в списке ввода, которое принимает максимальное значение при оценке функцией. Если более чем одно значение дает максимум, выбор результата среди этих значений является произвольным. ...

Аналогично для:
sort и sort_by из комментариев @ emu. с

Стабильность результата не гарантируется. Когда два ключа равны, порядок соответствующих элементов непредсказуем.

Первое, второе редактирование — «нам нужно углубиться» => Надеюсь, вам понравится «поездка».

Короткий ответ:
Причина того, что сортировка выглядит так, - это комбинация блока max_by (заставляет начать сортировку с max значений из %2, которая равна 1, затем она продолжается с 0) и qsort_r (быстрая сортировка BSD) реализован @ruby.

Длинный ответ: Все основано на исходном коде ruby ​​2.4.2 или текущей версии 2.5.0 (которая сейчас находится в разработке).

Алгоритм быстрой сортировки может различаться в зависимости от используемого компилятора. Вы можете использовать qsort_r: версия GNU, версия BSD (вы можете проверить конфигурацию ). ac) для получения дополнительной информации. Visual Studio использует версию BSD 2012 года или более позднюю.

+Tue Sep 15 12:44:32 2015  Nobuyoshi Nakada  <[email protected]>
+
+   * util.c (ruby_qsort): use BSD-style qsort_r if available.

Thu May 12 00:18:19 2016  NAKAMURA Usaku  <[email protected]>

    * win32/Makefile.sub (HAVE_QSORT_S): use qsort_s only for Visual Studio
      2012 or later, because VS2010 seems to causes a SEGV in
test/ruby/test_enum.rb.

1. Если у вас есть GNU qsort_r, но не BSD: используется только внутренняя реализация ruby_qsort. Проверьте util.c для внутренней реализации быстрой сортировки (ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d) ) функция Томоюки Кавамуры. @util.h

   Если HAVE_GNU_QSORT_R=1, то #define ruby_qsort qsort_r:

   #ifdef HAVE_GNU_QSORT_R
   #define ruby_qsort qsort_r
   #else    void ruby_qsort(void *, const size_t, const size_t,
       int (*)(const void *, const void *, void *), void *);
   #endif
   

2. Если обнаружен стиль BSD: используется приведенный ниже код (можно найти по адресу util.c). Обратите внимание, как cmp_bsd_qsort вызывается перед ruby_qsort. Причина? Вероятно, стандартизация, место в стеке и, возможно, скорость (сам не проверял - нужно было создать бенчмарк, а это довольно трудоемко).

Экономия места в стеке указана в исходном коде BSD qsort.c:

    /*
    * To save stack space we sort the smaller side of the partition first
    * using recursion and eliminate tail recursion for the larger side.
    */

Ветка BSD в исходном коде ruby:

     #if defined HAVE_BSD_QSORT_R
    typedef int (cmpfunc_t)(const void*, const void*, void*);

    struct bsd_qsort_r_args {
        cmpfunc_t *cmp;
        void *arg;
    };

    static int
    cmp_bsd_qsort(void *d, const void *a, const void *b)
    {
        const struct bsd_qsort_r_args *args = d;
        return (*args->cmp)(a, b, args->arg);
    }

    void
    ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d)
    {
        struct bsd_qsort_r_args args;
        args.cmp = cmp;
        args.arg = d;
        qsort_r(base, nel, size, &args, cmp_bsd_qsort);
    }

Если вы используете MSYS2 для компиляции вашего ruby ​​в Windows (больше не DevKit, а MSYS2 для установщика Windows, который я использую большую часть времени), NetBSD-версия qsort_r (которая существует с 02-07-2012). Последняя версия NetBSD qsort.c (редакция: 1.23).

Теперь примеры из жизни: "нам нужно пойти еще глубже"

Тесты будут проводиться на двух (Windows) рубинах:

• Первый рубин: будет основан на DevKit версии 2.2.2p95 (выпущенной 13 апреля 2015 г.) и не содержит реализации BSD qsort.

• Второй ruby: будет основан на MSYS2 tool-chain версии ruby ​​2.4.2-p198 (которая была выпущена 15 сентября 2017 года) и содержит патч (см. выше) для реализации BSD qsort.

Код:

x=[1,2,3,4,5,6,7,8,9]
10.times{|y| p x.max_by(y) {|t| t%2}}

Руби 2.2.2p95:

The result:
[]
[5]
[7, 1]
[3, 1, 5]
[7, 3, 1, 5]
[9, 7, 3, 1, 5]
[5, 9, 1, 3, 7, 6]
[5, 1, 9, 3, 7, 6, 4]
[5, 1, 3, 7, 9, 6, 4, 2]
[9, 1, 7, 3, 5, 4, 6, 8, 2]

Руби 2.4.2-p198:

The result:
[]
[1]
[7, 1]
[5, 3, 1]
[5, 7, 3, 1]
[5, 9, 7, 3, 1]
[5, 1, 9, 7, 3, 6]
[5, 1, 3, 9, 7, 4, 6]
[5, 1, 3, 7, 9, 2, 6, 4]
[9, 1, 3, 7, 5, 8, 4, 6, 2]

Теперь для разных x: x=[7,9,3,4,2,6,1,8,5]

Руби 2.2.2p95:

The result:
[]
[1]
[9, 7]
[1, 7, 3]
[5, 1, 7, 3]
[5, 1, 3, 9, 7]
[7, 5, 9, 3, 1, 2]
[7, 9, 5, 3, 1, 2, 4]
[7, 9, 3, 1, 5, 2, 4, 8]
[5, 9, 1, 3, 7, 4, 6, 8, 2]

Руби 2.4.2-p198:

The result:
[]
[9]
[9, 7]
[3, 1, 7]
[3, 5, 1, 7]
[7, 5, 1, 3, 9]
[7, 9, 5, 1, 3, 2]
[7, 9, 3, 5, 1, 4, 2]
[7, 9, 3, 1, 5, 8, 2, 4]
[5, 9, 3, 1, 7, 2, 4, 6, 8]

Теперь для тех же элементов в исходном массиве (qsort нестабилен, см. ниже): x=[1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Обработайте его следующим кодом: 12.times{|y| p x.max_by(y) {|t| t%2}}

Руби 2.2.2p95:

The result:
[]
[3]
[1, 1]
[9, 1, 7]
[3, 9, 1, 7]
[5, 3, 9, 1, 7]
[1, 5, 3, 9, 1, 7]
[5, 9, 3, 7, 1, 1, 1]
[1, 5, 9, 1, 7, 1, 3, 4]
[1, 1, 5, 9, 1, 7, 3, 4, 2]
[1, 1, 1, 5, 7, 3, 9, 4, 2, 8]
[9, 1, 7, 1, 5, 3, 1, 2, 6, 8, 4]

Руби 2.4.2-p198:

The Result:
[]
[1]
[1, 1]
[7, 9, 1]
[7, 3, 9, 1]
[7, 5, 3, 9, 1]
[7, 1, 5, 3, 9, 1]
[1, 5, 9, 3, 7, 1, 1]
[1, 1, 5, 9, 3, 7, 1, 4]
[1, 1, 1, 5, 9, 3, 7, 2, 4]
[1, 7, 3, 1, 5, 9, 1, 2, 4, 8]
[9, 3, 1, 7, 1, 5, 1, 2, 8, 6, 4]

Теперь главный вопрос --> Почему результаты отличаются?

Первый очевидный ответ будет заключаться в том, что при использовании реализаций GNU или BSD результат будет другим? Верно? Что ж, реализации разные, но дают (подробности смотрите в связанных реализациях) одинаковые результаты. Суть проблемы в другом.

Настоящая проблема здесь в самом алгоритме. Когда используется быстрая сортировка, вы получаете нестабильную сортировку (когда вы сравниваете два одинаковых значения, их порядок не остается прежним). Когда у вас есть [1,2,3,4,5,6,7,8,9], которые вы затем преобразуете в блоке в [1,0,1,0,1,0,1,0,1] с max(_by) вы сортируете массив в [1,1,1,1,1,0,0,0,0]. Вы начинаете с 1, но с какого? Ну тогда вы получите непредсказуемый результат. (max(_by) - это причина, по которой сначала получаются нечетные числа, а затем четные).

См. комментарий GNU qsort:

Предупреждение: если два объекта сравниваются как равные, их порядок после сортировки непредсказуем. То есть сортировка нестабильна. Это может иметь значение, когда при сравнении учитывается только часть элементов. Два элемента с одним и тем же ключом сортировки могут отличаться в других отношениях.

Теперь, чтобы отсортировать его, как это делает движок:

[1,2,3,4,5,6,7,8,9] -> Первыми учитываются нечетные числа [1,3,5,7,9], а те, которые считаются равными max_by{|t| t%2}, дают [1,1,1,1,1].

Вывод:

Теперь какой брать? Ну, это непредсказуемо, в вашем случае это были те, которые вы получили. Я получу разные даже для той же версии ruby, что и базовый алгоритм quick-sort неустойчив по своей природе.