Algoritmo utilizzato in Ruby per "String # include?"

Question

Qualcuno è in grado di individuare quale algoritmo è utilizzato per l'inclusione? metodo in Ruby? Per esempio

"helloworld".include?("hello") 

Answer 1

Come in rilievo stati nella sua risposta, String#include chiamate rb_str_index. Questa funzione a sua volta chiama rb_memsearch, che implementa lo Rabin-Karp string search algorithm, in base a this post su ruby-forum.com.

Answer 2

Questo è l'effettiva attuazione del 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; 
} 

Quindi l'algoritmo effettivamente utilizzato può essere trovato in rb_str_index.

Answer 3

La specifica del linguaggio Ruby non prescrive alcun algoritmo particolare. Ogni implementazione può utilizzare qualunque algoritmo vogliano.

Ad esempio, in Rubinius, String#include? chiamate 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 a sua volta è implementato mediante string_index primitivo:

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

Il string_index primitivo è implementata dalla funzione 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>(); 
    } 
}