Ruby中用於「String＃include？」的算法

Question

是否有人能夠確定哪些算法用於包含？ Ruby中的方法？例如

"helloworld".include?("hello") 

Answer 1

由於浮雕狀態，String#include調用rb_str_index。該功能依次調用rb_memsearch，該功能實現Rabin-Karp string search algorithm，根據this post的ruby-forum.com。

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