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;