[JAVA] [ArrayList] removeIf에 대해서

1. 사용법

//given
List<Integer> list = new ArrayList<>(Arrays.asList(1,2,3,4,5,6));
//when
list.removeIf(n -> (n % 3 == 0));
//then
System.out.println(list);
//[1, 2, 4, 5]

필터링해서 해당 조건에 맞는 변수를 삭제한다.

 

 

2. 구현

    public boolean removeIf(Predicate<? super E> filter) {
        return removeIf(filter, 0, size);
    }

    /**
     * Removes all elements satisfying the given predicate, from index
     * i (inclusive) to index end (exclusive).
     */
    boolean removeIf(Predicate<? super E> filter, int i, final int end) {
        Objects.requireNonNull(filter);
        int expectedModCount = modCount;
        final Object[] es = elementData;
        // Optimize for initial run of survivors
        for (; i < end && !filter.test(elementAt(es, i)); i++)
            ;
        // Tolerate predicates that reentrantly access the collection for
        // read (but writers still get CME), so traverse once to find
        // elements to delete, a second pass to physically expunge.
        if (i < end) {
            final int beg = i;
            final long[] deathRow = nBits(end - beg);
            deathRow[0] = 1L;   // set bit 0
            for (i = beg + 1; i < end; i++)
                if (filter.test(elementAt(es, i)))
                    setBit(deathRow, i - beg);
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            modCount++;
            int w = beg;
            for (i = beg; i < end; i++)
                if (isClear(deathRow, i - beg))
                    es[w++] = es[i];
            shiftTailOverGap(es, w, end);
            return true;
        } else {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            return false;
        }
    }

 

여기서 Predicate 란?

 

predicate는 함수형 인터페이스로서 

• test
• and
• negate
• or
• isEqual
• not

의 메소드가 있다.

이 중 test는 해당 조건이 맞으면 true, 아니면 false를 반환한다.

 

Optimize for initial run of survivors

for (; i < end && !filter.test(elementAt(es, i)); i++)
            ;

 

Tolerate predicates that reentrantly access the collection for read (but writers still get CME), so traverse once to find elements to delete, a second pass to physically expunge.

        Random random = new Random();
        //given
        List<Integer> list = new CustomArrayList<>();
        //when
        for (int i = 0; i < 100_000_000; i++) {
            list.add(random.nextInt(1000000));
        }
        long start = System.currentTimeMillis();
        list.removeIf(n -> (n % 7 == 0));
        long end = System.currentTimeMillis();
        //then
        System.out.println(end-start); // 630, 651

테스트를 진행했을 때는 위의 유무는 큰 차이가 없었다.

 

 

관리는 Drop the Bit로

    private static long[] nBits(int n) {
        return new long[((n - 1) >> 6) + 1];
    }
    private static void setBit(long[] bits, int i) {
        bits[i >> 6] |= 1L << i;
    }
    private static boolean isClear(long[] bits, int i) {
        return (bits[i >> 6] & (1L << i)) == 0;
    }

 

// removeIf 에서 사용되는 부분
final long[] deathRow = nBits(end - beg);

setBit(deathRow, i - beg);

isClear(deathRow, i - beg)

 

2의 6승 단위로 데이터의 길이에 대한 값을 관리하게 된다. 

 

1~63 까지가 하나의 비트 안에서 관리된다.
그리고 64~127, 128~255 이런식으로 관리가 되는 구조를 가지고 있다.

final int beg = i;
final long[] deathRow = nBits(end - beg);
deathRow[0] = 1L;   // set bit 0
for (i = beg + 1; i < end; i++)
    if (filter.test(elementAt(es, i)))
        setBit(deathRow, i - beg);

값이 1~6으로 element가 저장되어 있고 위에 for문을 통해 2까지 오게되었다. 

• beg = 2
• 나머지 길이가 4인데 63까지는 하나의 비트에서 관리되므로 0번째 비트에서 관리된다.
• 이미 위에서 첫 번째 비트가 삭제되었으므로 값을 1로 초기화 한다.
• 만약에 주어진 조건에 맞는다면 비트를 or 연산을 통해 더해나간다. (필자의 경우에는 n%3==0 으로 했으므로 8의 값이 더해진다.)

int w = beg;
for (i = beg; i < end; i++)
    if (isClear(deathRow, i - beg))
        es[w++] = es[i];

• 우선 첫 번째 비트는 무조건 isClear 조건에서 패스된다. ( 그 이유는 0번째 비트와 1의 and 조건을 통해 0인지 비교하는데 0번째 비트에서 9의 값을 가지고 있기 때문에 false의 값을 준다.)
• 이렇게 뒤의 값들이 앞으로 땡겨진다.
• 그러다 마지막 원소(5번째 위치)에서 8의 값은 0번째 비트의 값 and 조건에서 1이므로 패스되고 끝난다.

 

마무리

shiftTailOverGap(es, w, end);

private void shiftTailOverGap(Object[] es, int lo, int hi) {
        System.arraycopy(es, hi, es, lo, size - hi);
        for (int to = size, i = (size -= hi - lo); i < to; i++)
            es[i] = null;
    }

안쓰여지는 부부은 null로 해서 지워준다.