Какой алгоритм включает Array #?использует?

Question

Для ruby, где x - массив, как x.include?(y) проверяет, находится ли y в x? Какой алгоритм?

Answer 1

В дополнение к ответу Грега Хьюгилла, исходный код Ruby 1.9.3 для этого метода:

VALUE
rb_ary_includes(VALUE ary, VALUE item)
{
    long i;

    for (i=0; i<RARRAY_LEN(ary); i++) {
        if (rb_equal(RARRAY_PTR(ary)[i], item)) {
            return Qtrue;
        }
    }
    return Qfalse;
}

Таким образом, как сказал Грег, алгоритм представляет собой просто линейный поиск по массиву.

Answer 2

Поскольку массив не нужно сортировать, алгоритм не может быть лучше, чем «посмотреть на каждый элемент и посмотреть, соответствует ли он».