Comments

6 responses to “String matching in Ruby”

1. 

   무책

   March 2, 2006

   구현상 select가 제일 빠를텐데 싶어 벤치마크를 돌려보니 역시 select가 제일 빠르게 나오더군요.

   Rehearsal ——————————————–
   find_all 1.211000 0.000000 1.211000 ( 1.207000)
   select 0.691000 0.000000 0.691000 ( 0.693000)
   scan 1.533000 0.000000 1.533000 ( 1.533000)
   & 1.301000 0.000000 1.301000 ( 1.311000)
   ———————————– total: 4.736000sec

   user system total real
   find_all 1.022000 0.000000 1.022000 ( 1.033000)
   select 0.711000 0.000000 0.711000 ( 0.707000)
   scan 1.562000 0.000000 1.562000 ( 1.562000)
   & 1.252000 0.000000 1.252000 ( 1.255000)

2. 

   공성식

   March 2, 2006

   무책님,

   select 와 find_all 은 같은 것 아닌가요?
   어떻게 해서 그렇게 많은 차이가 나는지 궁금하네요.

   또한 문자열의 길이와 배열의 크기에 따라 결과가 달리 나올 것 같습니다.
   개인적으로는 맨 마지막 방법이 가장 훌륭해 보입니다만…

3. 

   무책

   March 2, 2006

   Enumerable에서 find_all과 select는 그냥 alias일 뿐 같은 것입니다. 그러나 Array에서는 select를 따로 정의하고 있죠. 그래서 위의 예에서는 find_all을 쓸 때는 Enumerable의 implementation을, select를 쓸 때는 Array의 implementation을 사용하고 있습니다. 아래 실제 소스를 보시면 왜 셋 중에 Array#select가 속도 면에서는 제일 빠른지 아실겁니다.

   저도 표현 면에서는 세번 째 방법이 가장 훌륭해 보입니다.

   /* Array#select */
   static VALUE
   rb_ary_select(ary)
   VALUE ary;
   {
   VALUE result;
   long i;

   result = rb_ary_new2(RARRAY(ary)->len);
   for (i = 0; i len; i++) {
   if (RTEST(rb_yield(RARRAY(ary)->ptr[i]))) {
   rb_ary_push(result, rb_ary_elt(ary, i));
   }
   }
   return result;
   }

   /* Enumerable#find_all a.k.a. #select */
   static VALUE
   enum_find_all(VALUE obj)
   {
   VALUE ary;

   RETURN_ENUMERATOR(obj, 0, 0);

   ary = rb_ary_new();
   rb_block_call(obj, id_each, 0, 0, find_all_i, ary);

   return ary;
   }

   static VALUE
   find_all_i(VALUE i, VALUE ary)
   {
   if (RTEST(rb_yield(i))) {
   rb_ary_push(ary, i);
   }
   return Qnil;
   }

   /* Array#& */
   static VALUE
   rb_ary_and(ary1, ary2)
   VALUE ary1, ary2;
   {
   VALUE hash, ary3, v, vv;
   long i;

   ary2 = to_ary(ary2);
   ary3 = rb_ary_new2(RARRAY(ary1)->len len ?
   RARRAY(ary1)->len : RARRAY(ary2)->len);
   hash = ary_make_hash(ary2, 0);

   for (i=0; ilen; i++) {
   v = vv = rb_ary_elt(ary1, i);
   if (st_delete(RHASH(hash)->tbl, (st_data_t*)&vv, 0)) {
   rb_ary_push(ary3, v);
   }
   }

   return ary3;
   }

4. 

   MKSeo

   March 2, 2006

   헉! 저 없는 사이 두분이서 .. ㅋㅋㅋ

   무책님. 물론 뉴스그룹에도 BM 결과가 있긴 합니다만, 제가 생각하기에는 benchmark 를 할 때 str의 길이와 leagues 의 길이를 둘다 조정해가면서 비교해보아야 할 듯합니다. 있다가 밤에 follow up 할께요 ^^

5. 

   공성식

   March 2, 2006

   아, 그렇군요.
   여태껏 select와 find_all을 늘 같다고 여겼는데 앞으로는 골라서 사용해야겠네요.
   무책님은 루비의 코어 소스까지 뒤지시다니 진정한 해커시군요…:-)

6. 

   MKSeo

   March 2, 2006

   공성식님이 말씀하신것도 있고, 아무래도 두분의 커멘트를 제 사이트에만
   저장하기에는 죄송한 마음도 있어서 루비 메타블로그의 퍼마링크를 original website에서
   메타블로그쪽으로 바꿨습니다. 음.. 이후 메타 블로그에서 커멘트를 남기면 제 홈피가
   아니라 메타블로그 자체에 저장됩니다.