Алгоритм, используемый в Ruby для "String # include?"

Question

Кто-нибудь может определить, какой алгоритм используется для включения? метод в рубине? Например

"helloworld".include?("hello")

Answer 1

Поскольку выбивает состояния в своем ответе, String#include вызывает rb_str_index. Эта функция в свою очередь вызывает rb_memsearch, который реализует алгоритм поиска строки Рабина-Карпа , согласно этой записи на ruby-forum.com.

Answer 2

Спецификация языка Ruby не предписывает какой-либо конкретный алгоритм.Каждая реализация может использовать любой алгоритм, который они хотят.

Например, в Рубиниус , String#include? звонки String#find_string:

def include?(needle)
  if needle.kind_of? Fixnum
    needle = needle % 256
    str_needle = needle.chr
  else
    str_needle = StringValue(needle)
  end

  !!find_string(str_needle, 0)
end

String#find_string, в свою очередь, реализуется через примитив string_index:

def find_string(pattern, start)
  Rubinius.primitive :string_index
  raise PrimitiveFailure, "String#find_string failed"
end

Примитив string_index реализуется с помощью функции rubinius::String::index:

// Rubinius.primitive :string_index
Fixnum* index(STATE, String* pattern, Fixnum* start);

rubinius::String::index:

Fixnum* String::index(STATE, String* pattern, Fixnum* start) {
  native_int total = size();
  native_int match_size = pattern->size();

  if(start->to_native() < 0) {
    Exception::argument_error(state, "negative start given");
  }

  switch(match_size) {
  case 0:
    return start;
  case 1:
    {
      uint8_t* buf = byte_address();
      uint8_t matcher = pattern->byte_address()[0];

      for(native_int pos = start->to_native(); pos < total; pos++) {
        if(buf[pos] == matcher) return Fixnum::from(pos);
      }
    }
    return nil<Fixnum>();
  default:
    {
      uint8_t* buf = byte_address();
      uint8_t* matcher = pattern->byte_address();

      uint8_t* last = buf + (total - match_size);
      uint8_t* pos = buf + start->to_native();

      while(pos <= last) {
        // Checking *pos directly then also checking memcmp is an
        // optimization. It's about 10x faster than just calling memcmp
        // everytime.
        if(*pos == *matcher &&
            memcmp(pos, matcher, match_size) == 0) {
          return Fixnum::from(pos - buf);
        }
        pos++;
      }
    }
    return nil<Fixnum>();
  }
}

Answer 3

Это фактическая реализация String#include?:

static VALUE
rb_str_include(VALUE str, VALUE arg)
{
    long i;

    StringValue(arg);
    i = rb_str_index(str, arg, 0);

    if (i == -1) return Qfalse;
    return Qtrue;
}

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