[jruby-dev] [Fwd: Re: Array#flatten works quadratic time on length of resulting array. It could be linear]

[Charles Oliver Nutter]

Anyone want to port?

-------- Original Message --------
Subject: Re: Array#flatten works quadratic time on length of resulting 
array. It could be linear
Date: Fri, 07 Dec 2007 11:34:37 +0900
From: Nobuyoshi Nakada <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
References: <[EMAIL PROTECTED]> 
<[EMAIL PROTECTED]> 
<[EMAIL PROTECTED]>

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


---------------------------------------------------------------------
To unsubscribe from this list please visit:

   http://xircles.codehaus.org/manage_email