Re: Array#flatten works quadratic time on length of resulting array. It could be linear

Hi,

At Fri, 7 Dec 2007 10:14:02 +0900,
Artem Voroztsov wrote in [ruby-core:13898]:
> Method Array#join has the same drawback.
> It joins recursively, checks for recursive arrays,  and works quadratic time.

HTH.


Index: thread.c
===================================================================
--- thread.c	(revision 14122)
+++ thread.c	(working copy)
@@ -2584,8 +2573,6 @@ static ID recursive_key;
 
 static VALUE
-recursive_check(VALUE obj)
+recursive_check(VALUE hash, VALUE obj)
 {
-    VALUE hash = rb_thread_local_aref(rb_thread_current(), recursive_key);
-
     if (NIL_P(hash) || TYPE(hash) != T_HASH) {
 	return Qfalse;
@@ -2594,14 +2581,15 @@ recursive_check(VALUE obj)
 	VALUE list = rb_hash_aref(hash, ID2SYM(rb_frame_this_func()));
 
-	if (NIL_P(list) || TYPE(list) != T_ARRAY)
+	if (NIL_P(list) || TYPE(list) != T_HASH)
+	    return Qfalse;
+	if (NIL_P(rb_hash_lookup(list, rb_obj_id(obj))))
 	    return Qfalse;
-	return rb_ary_includes(list, rb_obj_id(obj));
+	return Qtrue;
     }
 }
 
-static void
-recursive_push(VALUE obj)
+static VALUE
+recursive_push(VALUE hash, VALUE obj)
 {
-    VALUE hash = rb_thread_local_aref(rb_thread_current(), recursive_key);
     VALUE list, sym;
 
@@ -2615,15 +2603,15 @@ recursive_push(VALUE obj)
 	list = rb_hash_aref(hash, sym);
     }
-    if (NIL_P(list) || TYPE(list) != T_ARRAY) {
-	list = rb_ary_new();
+    if (NIL_P(list) || TYPE(list) != T_HASH) {
+	list = rb_hash_new();
 	rb_hash_aset(hash, sym, list);
     }
-    rb_ary_push(list, rb_obj_id(obj));
+    rb_hash_aset(list, rb_obj_id(obj), Qtrue);
+    return hash;
 }
 
 static void
-recursive_pop(void)
+recursive_pop(VALUE hash, VALUE obj)
 {
-    VALUE hash = rb_thread_local_aref(rb_thread_current(), recursive_key);
     VALUE list, sym;
 
@@ -2639,5 +2627,5 @@ recursive_pop(void)
     }
     list = rb_hash_aref(hash, sym);
-    if (NIL_P(list) || TYPE(list) != T_ARRAY) {
+    if (NIL_P(list) || TYPE(list) != T_HASH) {
 	VALUE symname = rb_inspect(sym);
 	VALUE thrname = rb_inspect(rb_thread_current());
@@ -2645,5 +2633,5 @@ recursive_pop(void)
 		 StringValuePtr(symname), StringValuePtr(thrname));
     }
-    rb_ary_pop(list);
+    rb_hash_delete(list, obj);
 }
 
@@ -2651,5 +2639,7 @@ VALUE
 rb_exec_recursive(VALUE (*func) (VALUE, VALUE, int), VALUE obj, VALUE arg)
 {
-    if (recursive_check(obj)) {
+    VALUE hash = rb_thread_local_aref(rb_thread_current(), recursive_key);
+
+    if (recursive_check(hash, obj)) {
 	return (*func) (obj, arg, Qtrue);
     }
@@ -2658,5 +2648,5 @@ rb_exec_recursive(VALUE (*func) (VALUE, 
 	int state;
 
-	recursive_push(obj);
+	hash = recursive_push(hash, obj);
 	PUSH_TAG();
 	if ((state = EXEC_TAG()) == 0) {
@@ -2664,5 +2654,5 @@ rb_exec_recursive(VALUE (*func) (VALUE, 
 	}
 	POP_TAG();
-	recursive_pop();
+	recursive_pop(hash, obj);
 	if (state)
 	    JUMP_TAG(state);


-- 
Nobu Nakada