所以我收集了这么多东西对吧?它的树备份(rbtree),因此查找速度很快,并且值被排序。
假设我得到了x值。我可以在logn时间内在树上查找x,酷。但我也希望这些值在树的x右边,直到其中一个满足测试。
即,获取所有大于等于x且小于y的元素
我可以得到x,i的指数,然后得到i+1,i+2的值……直到val(i+z)大于y。
但那要花Z*logn的钱。
如果在树上枚举,则树内的枚举器不会花费logn来继续下一个元素——它只是跟随树中的指针。
那么,有没有办法从一个特定的索引开始枚举呢?这样我就不必跳过i元素,然后才能开始枚举我想要的范围。
如果你觉得我疯了,告诉我。
最佳答案
好吧,如果您自己将集合中的元素放在其中,并且不介意在插入之前对它们进行排序,那么可以使用链接列表类型包装它们。只需确保每个元素的链表项包装器的键使用元素的键作为其键
对于树类型。然后,一个查找会在链接列表中找到一个位置,您可以从那里走过去。
但是,如果你不能这样做,你唯一的办法就是修改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);
然后,如果在已安装的rbtree gem的源目录中运行
make
,则应重新生成扩展名,并可以正常使用它:% 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与您的更改一起分发。或者,嘿,把它们交给the gem creator on Rubyforge,
这样每个人都能利用他们。