Что включает в себя алгоритм, который включает Array #? использует?

Для рубина, где x - это массив, как x.include?(y) проверить, y находится в x? Какой алгоритм?Что включает в себя алгоритм, который включает Array #? использует?

источник

2012-01-27 locoboy

вы можете найти источник функции http://ruby-doc.org/core-1.9.3/Array.html#method-i-include-3F – oldergod

Это 'O (n)'. Для 'O (1)' вместо этого используйте 'Set'. –

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

источник

2012-01-27 01:19:52

Gotcha, поэтому, если у вас есть отсортированный массив, используйте что-то еще ... – locoboy

@ cfarm54 С большим отсортированным массивом в большинстве случаев бинарный поиск будет быстрее. http://0xcc.net/ruby-bsearch/index.html.en –

yep, и я предполагаю, что для этого нет функций для ruby – locoboy

В дополнение к ответу Greg Hewgill, в исходный код Руби 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; 
}

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

источник

2012-01-27 01:24:03 blahman

+1 за использование источника, Люк. –

Что включает в себя алгоритм, который включает Array #? использует?

ответ

Смежные вопросы