Algoritmo utilizado en Ruby para "String # include?"

Question

¿Alguien puede identificar qué algoritmo se usa para incluir? método en Ruby? Por ejemplo

"helloworld".include?("hello") 

Answer 1

Como en relieve estados en su respuesta, String#include llamadas rb_str_index. Esta función a su vez llama al rb_memsearch, que implementa el Rabin-Karp string search algorithm, de acuerdo con this post en ruby-forum.com.

Answer 2

Ésta es la aplicación real de 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; 
} 

Así que el algoritmo real utilizado puede encontrarse en rb_str_index.

Answer 3

La especificación de lenguaje Ruby no prescribe ningún algoritmo en particular. Cada implementación puede usar cualquier algoritmo que deseen.

Por ejemplo, en Rubinius, String#include? llamadas 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 su vez se implementa mediante la primitiva string_index:

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

El string_index primitiva se implementa por la función de 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>(); 
    } 
}