"String＃include？"のRubyで使用されるアルゴリズム

Question

どのアルゴリズムがインクルードに使用されているのかを特定できますか？ Rubyのメソッド？例

"helloworld".include?("hello") 

Answer 1

エンボスの状態は、彼の答えでは、String#includeはrb_str_indexとなります。この関数はthis postのruby-forum.comに従ってRabin-Karp string search algorithmを実装するrb_memsearchを呼び出します。

Answer 2

のためにこれは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で見つけることができます。

Answer 3

Ruby言語仕様は、特定のアルゴリズムを規定していません。すべての実装で、必要なアルゴリズムを使用できます。 Rubinius、例えば

、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 

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>(); 
    } 
}