2

所以我得到了这个大屁股集合对吗？它的树支持（RBTree），因此查找速度很快，并且对值进行了排序。

假设我得到了 X 值。我可以在登录时间内在我的树中查找 X，很酷。但我也想要树中 X 右侧的值，直到其中一个满足测试。即，获取 >= X 和 < Y 的所有元素

我可以得到 X, i 的索引，然后得到 i+1, i+2.... 的值，直到 val(i+z) > Y。除了花费 z * logn。如果您在树上进行枚举，则树内的枚举器不会花费 logn 来继续下一个元素 - 它只是跟随树中的指针。

那么，有没有办法从特定的索引开始枚举呢？这样我就不必跳过 i 元素，然后我就可以开始枚举我想要的范围了。

告诉我你是否认为我疯了。

4

1 回答 1

3

好吧，如果您自己将集合的元素放在那里，并且不介意在插入之前对它们进行排序，则可以用链表类型包装它们。只需确保每个元素的链表项包装器的键使用元素的键作为其树排序的键。然后查找将为您提供链接列表中的位置，您可以从那里步行。

但是，如果你不能那样做，你唯一的办法就是修改 RBTree，这需要在 C 中做一些工作，因为它是 ruby​​ 的原生扩展。您需要的大部分内容已经在那里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 上的 gem 创建者，这样每个人都可以利用它们。

于 2009-03-27T18:29:32.623 回答