Ruby의 인덱스/값에서 열거

Question

그래서 내가 이 엄청난 컬렉션을 갖고 있는 거 맞지?트리 기반(RBTree)이므로 조회가 빠르고 값이 정렬됩니다.

내가 X 값을 얻었다고 가정해 보세요.로그인 시간에 내 트리에서 X를 찾을 수 있습니다.하지만 그 중 하나가 테스트를 만족할 때까지 트리의 X 오른쪽에 있는 값도 원합니다.즉, >= X 및 < Y인 모든 요소를 ​​가져옵니다.

나 ~할 수 있었다 X, i의 인덱스를 얻은 다음 i+1, i+2에서 값을 얻습니다....val(i+z)가 > Y가 될 때까지.z * logn 비용을 제외하고.트리에 대해 열거하는 경우 트리 내부의 열거자는 다음 요소로 진행하는 데 logn 비용이 들지 않습니다. 트리의 포인터만 따라갑니다.

그렇다면 특정 인덱스에서 열거를 시작하는 방법이 있습니까?따라서 원하는 범위에 대해 열거를 시작하기 전에 i 요소를 건너뛸 필요가 없습니다.

내가 미쳤다고 생각하면 말해주세요.

Answer 1

글쎄요, 컬렉션의 요소를 여기에 직접 넣고 삽입하기 전에 정렬해도 괜찮다면 연결 목록 유형으로 래핑할 수 있습니다.각 요소의 링크 된 목록 항목 래퍼의 키가 요소의 키를 트리 정렬의 키로 사용하는지 확인하십시오.그런 다음 조회를 통해 연결 목록의 위치를 ​​얻을 수 있으며 거기에서 바로 이동할 수 있습니다.

그러나 그렇게 할 수 없는 경우 유일한 방법은 RBTree를 수정하는 것입니다. RBTree는 Ruby의 기본 확장이므로 C에서 약간의 작업이 필요합니다.필요한 대부분의 부품이 이미 존재합니다. dict_lookup() 필요한 트리의 노드를 제공하고 rbtree_for_each() 시작 노드가 주어지면 반복자를 작성하는 방법을 보여줍니다.

RBTree gem의 rbtree.c에 다음 코드를 추가해야 합니다.

*** rbtree.c.orig 2009-03-27 14:14:55.000000000 -0400
--- rbtree.c  2009-03-27 14:20:21.000000000 -0400
***************
*** 528,533 ****
--- 528,574 ----
      return EACH_NEXT;
  }

+ static VALUE
+ rbtree_each_starting_with_body(rbtree_each_arg_t* arg)
+ {
+     VALUE self = arg->self;
+     dict_t* dict = DICT(self);
+     dnode_t* node;
+     
+     ITER_LEV(self)++;
+     for (node = (dnode_t*) arg->arg;
+          node != NULL;
+          node = dict_next(dict, node)) {
+         
+         if (arg->func(node, NULL) == EACH_STOP)
+             break;
+     }
+     return self;
+ }
+ 
+ /*
+  * call-seq:
+  *   rbtree.each_starting_with(key) {|key, value| block} => rbtree
+  *
+  * Calls block once for each key in order, starting with the given key,
+  * passing the key and value as a two-element array parameters.
+  */
+ VALUE
+ rbtree_each_starting_with(VALUE self, VALUE key)
+ {
+     dnode_t* node = dict_lookup(DICT(self), TO_KEY(key));
+     rbtree_each_arg_t each_arg;
+     if (node == NULL) { return self; };
+     
+     RETURN_ENUMERATOR(self, 0, NULL);
+ 
+     each_arg.self = self;
+     each_arg.func = each_i;
+     each_arg.arg = node;
+     return rb_ensure(rbtree_each_starting_with_body, (VALUE)&each_arg,
+                      rbtree_each_ensure, self);
+ }
+ 
  /*
   * call-seq:
   *   rbtree.each {|key, value| block} => rbtree
***************
*** 1616,1621 ****
--- 1657,1663 ----
      rb_define_method(MultiRBTree, "length", rbtree_size, 0);

      rb_define_method(MultiRBTree, "each", rbtree_each, 0);
+     rb_define_method(MultiRBTree, "each_starting_with", rbtree_each_starting_with, 1);
      rb_define_method(MultiRBTree, "each_value", rbtree_each_value, 0);
      rb_define_method(MultiRBTree, "each_key", rbtree_each_key, 0);
      rb_define_method(MultiRBTree, "each_pair", rbtree_each_pair, 0);

그런 다음 실행하면 make 설치된 rbtree gem의 소스 디렉터리에서 확장 기능을 다시 만들어야 하며 정상적으로 사용할 수 있습니다:

% irb
irb> require 'rubygems'
=> true
irb> require 'rbtree'
=> true
irb> x = RBTree[ 'a', 1, 'b', 2, 'c', 3, 'd', 4 ]
=> #<RBTree: {"a"=>1, "b"=>2, "c"=>3, "d"=>4}, default=nil, cmp_proc=nil>
irb> x.each { |k,v| p [k, v] }
["a", 1]
["b", 2]
["c", 3]
["d", 4]
=> #<RBTree: {"a"=>1, "b"=>2, "c"=>3, "d"=>4}, default=nil, cmp_proc=nil>
irb> x.each_starting_with('b') { |k,v| p [k, v] }
["b", 2]
["c", 3]
["d", 4]
=> #<RBTree: {"a"=>1, "b"=>2, "c"=>3, "d"=>4}, default=nil, cmp_proc=nil>

이렇게 변경했다는 사실을 기억하고 수정된 gem을 변경 사항과 함께 배포하세요.아니면 제출해 주세요. Rubyforge의 보석 제작자, 모든 사람이 그들을 활용할 수 있도록합니다.