Feature #13884 » array_opt.diff
| array.c | ||
|---|---|---|
|
VALUE rb_cArray;
|
||
|
const long SMALL_ARRAY_LEN = 32;
|
||
|
/* for OPTIMIZED_CMP: */
|
||
|
#define id_cmp idCmp
|
||
| ... | ... | |
|
VALUE hash;
|
||
|
long i;
|
||
|
hash = ary_make_hash(to_ary(ary2));
|
||
|
ary3 = rb_ary_new();
|
||
|
for (i=0; i<RARRAY_LEN(ary1); i++) {
|
||
|
if (st_lookup(rb_hash_tbl_raw(hash), RARRAY_AREF(ary1, i), 0)) continue;
|
||
|
rb_ary_push(ary3, rb_ary_elt(ary1, i));
|
||
|
if (RARRAY_LEN(ary2) <= SMALL_ARRAY_LEN) {
|
||
|
for (i=0; i<RARRAY_LEN(ary1); i++) {
|
||
|
VALUE elt = rb_ary_elt(ary1, i);
|
||
|
if (rb_ary_includes(ary2, elt)) continue;
|
||
|
rb_ary_push(ary3, elt);
|
||
|
}
|
||
|
} else {
|
||
|
hash = ary_make_hash(to_ary(ary2));
|
||
|
for (i=0; i<RARRAY_LEN(ary1); i++) {
|
||
|
if (st_lookup(rb_hash_tbl_raw(hash), RARRAY_AREF(ary1, i), 0)) continue;
|
||
|
rb_ary_push(ary3, rb_ary_elt(ary1, i));
|
||
|
}
|
||
|
ary_recycle_hash(hash);
|
||
|
}
|
||
|
ary_recycle_hash(hash);
|
||
|
return ary3;
|
||
|
}
|
||
| ... | ... | |
|
ary2 = to_ary(ary2);
|
||
|
ary3 = rb_ary_new();
|
||
|
if (RARRAY_LEN(ary2) == 0) return ary3;
|
||
|
hash = ary_make_hash(ary2);
|
||
|
table = rb_hash_tbl_raw(hash);
|
||
|
for (i=0; i<RARRAY_LEN(ary1); i++) {
|
||
|
v = RARRAY_AREF(ary1, i);
|
||
|
vv = (st_data_t)v;
|
||
|
if (st_delete(table, &vv, 0)) {
|
||
|
rb_ary_push(ary3, v);
|
||
|
if (RARRAY_LEN(ary1) <= SMALL_ARRAY_LEN && RARRAY_LEN(ary2) <= SMALL_ARRAY_LEN) {
|
||
|
for (i=0; i<RARRAY_LEN(ary1); i++) {
|
||
|
VALUE elt = rb_ary_elt(ary1, i);
|
||
|
if (!rb_ary_includes(ary2, elt)) continue;
|
||
|
if (rb_ary_includes(ary3, elt)) continue;
|
||
|
rb_ary_push(ary3, elt);
|
||
|
}
|
||
|
} else {
|
||
|
hash = ary_make_hash(ary2);
|
||
|
table = rb_hash_tbl_raw(hash);
|
||
|
for (i=0; i<RARRAY_LEN(ary1); i++) {
|
||
|
v = RARRAY_AREF(ary1, i);
|
||
|
vv = (st_data_t)v;
|
||
|
if (st_delete(table, &vv, 0)) {
|
||
|
rb_ary_push(ary3, v);
|
||
|
}
|
||
|
}
|
||
|
ary_recycle_hash(hash);
|
||
|
}
|
||
|
ary_recycle_hash(hash);
|
||
|
return ary3;
|
||
|
}
|
||
| ... | ... | |
|
long i;
|
||
|
ary2 = to_ary(ary2);
|
||
|
hash = ary_make_hash(ary1);
|
||
|
for (i=0; i<RARRAY_LEN(ary2); i++) {
|
||
|
VALUE elt = RARRAY_AREF(ary2, i);
|
||
|
if (!st_update(RHASH_TBL_RAW(hash), (st_data_t)elt, ary_hash_orset, (st_data_t)elt)) {
|
||
|
RB_OBJ_WRITTEN(hash, Qundef, elt);
|
||
|
if (RARRAY_LEN(ary1) + RARRAY_LEN(ary2) <= SMALL_ARRAY_LEN) {
|
||
|
ary3 = rb_ary_new();
|
||
|
for (i=0; i<RARRAY_LEN(ary1); i++) {
|
||
|
VALUE elt = rb_ary_elt(ary1, i);
|
||
|
if (rb_ary_includes(ary3, elt)) continue;
|
||
|
rb_ary_push(ary3, elt);
|
||
|
}
|
||
|
for (i=0; i<RARRAY_LEN(ary2); i++) {
|
||
|
VALUE elt = rb_ary_elt(ary2, i);
|
||
|
if (rb_ary_includes(ary3, elt)) continue;
|
||
|
rb_ary_push(ary3, elt);
|
||
|
}
|
||
|
} else {
|
||
|
hash = ary_make_hash(ary1);
|
||
|
for (i=0; i<RARRAY_LEN(ary2); i++) {
|
||
|
VALUE elt = RARRAY_AREF(ary2, i);
|
||
|
if (!st_update(RHASH_TBL_RAW(hash), (st_data_t)elt, ary_hash_orset, (st_data_t)elt)) {
|
||
|
RB_OBJ_WRITTEN(hash, Qundef, elt);
|
||
|
}
|
||
|
}
|
||
|
ary3 = rb_hash_values(hash);
|
||
|
ary_recycle_hash(hash);
|
||
|
}
|
||
|
ary3 = rb_hash_values(hash);
|
||
|
ary_recycle_hash(hash);
|
||
|
return ary3;
|
||
|
}
|
||
| test/ruby/test_array.rb | ||
|---|---|---|
|
assert_equal(@cls[], @cls[ 1, 2, 3 ] & @cls[ 4, 5, 6 ])
|
||
|
end
|
||
|
def test_AND_big_array # '&'
|
||
|
assert_equal(@cls[1, 3], @cls[ 1, 1, 3, 5 ]*64 & @cls[ 1, 2, 3 ]*64)
|
||
|
assert_equal(@cls[], @cls[ 1, 1, 3, 5 ]*64 & @cls[ ])
|
||
|
assert_equal(@cls[], @cls[ ] & @cls[ 1, 2, 3 ]*64)
|
||
|
assert_equal(@cls[], @cls[ 1, 2, 3 ]*64 & @cls[ 4, 5, 6 ]*64)
|
||
|
end
|
||
|
def test_MUL # '*'
|
||
|
assert_equal(@cls[], @cls[]*3)
|
||
|
assert_equal(@cls[1, 1, 1], @cls[1]*3)
|
||
| ... | ... | |
|
assert_equal(@cls[1, 2, 3], @cls[1, 2, 3] - @cls[4, 5, 6])
|
||
|
end
|
||
|
def test_MINUS_big_array # '-'
|
||
|
assert_equal(@cls[1]*64, @cls[1, 2, 3, 4, 5]*64 - @cls[2, 3, 4, 5]*64)
|
||
|
# Ruby 1.8 feature change
|
||
|
#assert_equal(@cls[1], @cls[1, 2, 1, 3, 1, 4, 1, 5]*64 - @cls[2, 3, 4, 5]*64)
|
||
|
assert_equal(@cls[1, 1, 1, 1]*64, @cls[1, 2, 1, 3, 1, 4, 1, 5]*64 - @cls[2, 3, 4, 5]*64)
|
||
|
a = @cls[]
|
||
|
1000.times { a << 1 }
|
||
|
assert_equal(1000, a.length)
|
||
|
#assert_equal(@cls[1], a - @cls[2])
|
||
|
assert_equal(@cls[1] * 1000, a - @cls[2])
|
||
|
end
|
||
|
def test_LSHIFT # '<<'
|
||
|
a = @cls[]
|
||
|
a << 1
|
||
| ... | ... | |
|
def initialize(name) @name = name; end
|
||
|
def inspect; "test_OR_in_order(#{@name})"; end
|
||
|
def hash; 0; end
|
||
|
def eql?(a) true; end
|
||
|
def ==(a) true; end
|
||
|
break [new("1"), new("2")]
|
||
|
end
|
||
|
assert_equal([obj1], [obj1]|[obj2])
|
||
|
end
|
||
|
def test_OR_big_array # '|'
|
||
|
assert_equal(@cls[1,2], @cls[1]*64 | @cls[2]*64)
|
||
|
assert_equal(@cls[1,2], @cls[1, 2]*64 | @cls[1, 2]*64)
|
||
|
a = (1..64).to_a
|
||
|
b = (1..128).to_a
|
||
|
c = a | b
|
||
|
assert_equal(c, b)
|
||
|
assert_not_same(c, b)
|
||
|
assert_equal((1..64).to_a, a)
|
||
|
assert_equal((1..128).to_a, b)
|
||
|
end
|
||
|
def test_combination
|
||
|
a = @cls[]
|
||
|
assert_equal(1, a.combination(0).size)
|
||