[suggestion] sorted flag for Array


#1

e$B1sF#$G$9!#e(B

e$B;W$$IU$-$G$9$,!"e(BArray
e$B$K!V%=!<%H:Q$_!W$rI=$9%U%i%0$r;}$?$;$k$N$O$I$&e(B
e$B$G$7$g$&$+!#e(B

e$B!V%=!<%H:Q$_!W$NG[Ns$KBP$7$F$O!"e(B

  • Array#index e$B$de(B include? e$B$GFsJ,C5:w$r;H$&e(B
  • Array#uniq e$B$de(B - e$B!"e(B& e$B!"e(B|
    e$B$G$O!"0l;~%O%C%7%e$r:n$i$:!"e(B1 e$B%Q%9$G=hM}$9$ke(B

e$B$H$$$&:GE,2=$,$G$-$^$9!#FC$KA0<T$Oe(B O(n) e$B$+$ie(B O(log n)
e$B$K$J$j$^$9!#e(B
e$BA0<T$O%F!<%V%k$rG[Ns$G<BAu$7$F$$$k%W%m%0%i%$G;H$($=$&$G!"8e<T$O=89g$re(B e$BG[Ns$GBeBXI=8=$7$F$$$k%W%m%0%i%$G;H$($=$&$G$9!#e(B

e$B%U%i%0$N4IM}$Oe(B

  • e$B%V%m%C%/$J$7e(B Array#sort e$B$de(B Array#sort!
    e$B$NJV$jCM$N%U%i%0$rN)$F$ke(B
  • e$BGK2uE*JQ99$r9T$C$?$i%U%i%0$r>C$9e(B

e$B$H$9$k$@$1$J$N$G!"%*!<%P!<%X%C%I$OL5;k$G$-$kNL$@$H;W$$$^$9e(B
(e$BL$8!>Ze(B) e$B!#e(B

e$B;n83E*$Ke(B Array#include? e$B$@$1<BAu$7$^$7$?!#e(B
e$BHs>o$K6KC<$JNc$G<BB,$7$?$H$3$m!"%%j%8%J%k$Ge(B 30
e$BIC!"%Q%C%A8e$Ge(B 0.04 e$BICe(B
e$B$G$7$?e(B (e$B%
!<%@$N2~A1$J$N$G?tCM$K$"$^$j0UL#$O$J$$$G$9$,e(B)
e$B!#e(B

a = ([0] * 100000 + [1]).sort; 1000.times { a.include?(1) }

e$B<+J,$G$b$3$NDs0F$,$I$N$/$i$$JXMx$J$N$+e(B
(e$B$^$?$OJXMx$G$J$$$N$+!"$b$7$/$Oe(B
e$B$^$:$$$N$+e(B) e$BFI$$-$l$F$$$^$;$s!#$$J$5$s$I$&;W$o$l$^$9$+!#e(B

e$B0J2<!"<+J,$G9M$(IU$$$?5DO@e(B:

  • sort e$B$,JV$7$?G[Ns$@$1B.$$$H$$$&$N$,$o$+$j$K$/$$e(B
    (e$B%V%m%C%/$D$-e(B sort e$B$de(B sort_by
    e$B$G$O%@%a$H$$$&$N$b$o$+$j$K$/$$$+e(B)

  • e$B%=!<%H$9$Y$-$G$J$$G[Nse(B (<=> e$B$,A4=g=x$K$J$C$F$$$J$$G[Nse(B)
    e$B$r%=!<%H$7$?e(B
    e$BG[Ns$G$O!":GE,2=$G7k2L$,JQ$o$k$3$H$,$"$k$,!“8=<BE*$K$^$:$$Nc$O$”$k$+e(B

  • <=> e$B$He(B ==
    e$B$,L7=b$9$k$h$&$JMWAG$r4^$`G[Ns$G$b7k2L$,JQ$o$k$,!“8=<BE*$Ke(B
    e$B$^$:$$Nc$O$”$k$+e(B

Index: array.c

— array.c (revision 23590)
+++ array.c (working copy)
@@ -140,6 +140,14 @@
FL_SET(ary, RARRAY_SHARED_ROOT_FLAG);
} while (0)

+#define RARRAY_SORTED_FLAG FL_USER6
+#define ARY_SORTED_P(ary) (FL_TEST(ary, RARRAY_SORTED_FLAG))
+#define FL_SET_SORTED(ary) do { \

  • assert(!ARY_SORTED_P(ary)); \
  • FL_SET(ary, RARRAY_SORTED_FLAG);
    +} while (0)
    +#define FL_UNSET_SORTED(ary) FL_UNSET(ary, RARRAY_SORTED_FLAG)

static void
ary_resize_capa(VALUE ary, long capacity)
{
@@ -268,6 +276,9 @@
ARY_SET_PTR(ary, ptr);
}
}

  • if (ARY_SORTED_P(ary)) {
  • FL_UNSET_SORTED(ary);
  • }
    }

VALUE
@@ -1863,6 +1874,7 @@
}
/* tmp will be GC’ed. */
RBASIC(tmp)->klass = rb_cArray;

  • if (!rb_block_given_p()) FL_SET_SORTED(ary);
    }
    return ary;
    }
    @@ -2856,6 +2868,25 @@
    {
    long i;

  • if (ARY_SORTED_P(ary)) {

  • long j;

  • struct ary_sort_data data;

  • volatile VALUE tmp = rb_ary_tmp_new(0);

  • data.ary = tmp;

  • data.opt_methods = 0;

  • data.opt_inited = 0;

  • i = 0; j = RARRAY_LEN(ary) - 1;

  • if (j == -1) return Qfalse;

  • while (i <= j) {

  •  long m = i + (j - i) / 2;
    
  •  long r = sort_2(&RARRAY_PTR(ary)[m], &item, &data);
    
  •  if (!ARY_SORTED_P(ary)) goto unsorted;
    
  •  if (r == 0) return Qtrue;
    
  •  if (r > 0) j = m - 1; else i = m + 1;
    
  • }

  • return Qfalse;

  • }

  • unsorted:
    for (i=0; i<RARRAY_LEN(ary); i++) {
    if (rb_equal(RARRAY_PTR(ary)[i], item)) {
    return Qtrue;


#2

e$B@>;3OB9-$G$9!#e(B

At Tue, 26 May 2009 22:58:16 +0900,
Yusuke ENDOH wrote:

e$B<+J,$G$b$3$NDs0F$,$I$N$/$i$$JXMx$J$N$+e(B (e$B$^$?$OJXMx$G$J$$$N$+!"$b$7$/$Oe(B
e$B$^$:$$$N$+e(B) e$BFI$$-$l$F$$$^$;$s!#$$J$5$s$I$&;W$o$l$^$9$+!#e(B

e$B%=!<%H8e$K!Ve(B<=>e$B!W$r:FDj5A$7$?$j!"e(B
(0…100).map{|i|[i]}.sort.map!{|a|a[0]=-a[0]}
e$B$N$h$&$K%=!<%H8e$KCf?H$NCf?H$rJQ99$7$?$j$7$?>l9g$Ne(B
e$B5sF0$,JQ$o$k$N$O$o$+$j$K$/$$$H;W$$$^$9!#e(B


#3

e$B1sF#$G$9!#e(B

2009/06/01 19:09 Kazuhiro NISHIYAMA removed_email_address@domain.invalid:

e$B$N$h$&$K%=!<%H8e$KCf?H$NCf?H$rJQ99$7$?$j$7$?>l9g$Ne(B
e$B5sF0$,JQ$o$k$N$O$o$+$j$K$/$$$H;W$$$^$9!#e(B

e$B$J$k$[$I!"A0<T$OBP:v$G$-$k5$$,$7$^$9$,!"8e<T$O$I$&$7$h$&$be(B
e$B$J$5$=$&$G$9$M!#8+Mn$H$7$F$^$7$?!#e(B
e$B$3$NDs0F$O<h$j2<$2$^$9!#$*A{$,$;$7$^$7$?!#e(B