Thuật toán được sử dụng trong Ruby cho "String # include?"

Question

Có ai có thể xác định thuật toán nào được sử dụng cho phần bao gồm không? phương pháp trong Ruby? Ví dụ

"helloworld".include?("hello") 

Answer 1

Là emboss nêu rõ câu trả lời của mình, String#include gọi rb_str_index. Chức năng này lần lượt gọi rb_memsearch, thực hiện Rabin-Karp string search algorithm, theo số this post trên ruby-forum.com.

Answer 2

này là việc thực hiện thực tế của 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; 
} 

Vì vậy, các thuật toán thực tế sử dụng có thể được tìm thấy trong rb_str_index.

Answer 3

Đặc tả ngôn ngữ Ruby không quy định bất kỳ thuật toán cụ thể nào. Mỗi lần triển khai có thể sử dụng bất kỳ thuật toán nào họ muốn.

Ví dụ, trong Rubinius, String#include? cuộc gọi 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 lần lượt được thực hiện thông qua các string_index nguyên thủy:

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

Các string_index nguyên thủy được thực hiện bởi các rubinius::String::index chức năng:

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