حذف المان‌ها از ArrayList در جاوا ۸

3,741 خواندن این مطلب 1 دقیقه زمان می‎برد

همانطور که می‌دانید پیاده‌سازی ArrayList به این شکل است که المان‌ها را در واقع در یک آرایه نگه می‌دارد. حذف المان‌ها از ArrayList قدری هزینه‌بر بوده و از مرتبه زمانی n^2 می‌باشد. آیا جاوا ۸ می‌تواند این هزینه را کاهش دهد؟

فرض کنید یک لیست از اعداد صحیح داریم و می‌خواهیم تمام اعداد غیر اول آن را حذف کنیم.

کاری که می‌کنیم استفاده از itarator و یک حلقه while است. نمی‌توانیم همزمان که روی آرایه حرکت می‌کنیم، عناصر آن را حذف کنیم. (با خطای concurrent modification exception روبرو می‌شویم.)

بنابراین…

Iterator<Integer> iterator = numbers.iterator();
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            if (!isPrime(next)) {
                iterator.remove();
            }
        }

Iterator<Integer> iterator = numbers.iterator();

while (iterator.hasNext()) {

Integer next = iterator.next();

if (!isPrime(next)) {

iterator.remove();

}

اما چنین کدی پیچیدگی زمانی n^2 دارد. در این کد دو کار را انجام دادیم،‌ حرکت روی لیست که از مرتبه n است. در ArrayList وقتی المانی را از یک اندیس حذف می‌کنید، هر چیزی در ادامه آرایه لازم است یک واحد شیفت پیدا کند. در واقع کاری که تابع remove انجام می‌دهد این است که داده‌های آرایه را در هر فراخوانی تابع کپی می‌کند. به این معنی است که n بار کپی خواهیم داشت و در کل مرتبه زمانی n^2 داریم.

جاوا ۸ یک تابع removeif در واسط collection دارد. این تابع برای ArrayList یک پیاده‌سازی پیچیده‌ای دارد که در نهایت به مرتبه‌زمانی n ختم می‌شود.

numbers.removeIf(integer -> !isPrime(integer));

1	numbers.removeIf(integer -> !isPrime(integer));

سورس کد تابع removeif از جاوا ۸ نیز به شکل زیر است.

public boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        // figure out which elements are to be removed
        // any exception thrown from the filter predicate at this stage
        // will leave the collection unmodified
        int removeCount = 0;
        final BitSet removeSet = new BitSet(size);
        final int expectedModCount = modCount;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            @SuppressWarnings("unchecked")
            final E element = (E) elementData[i];
            if (filter.test(element)) {
                removeSet.set(i);
                removeCount++;
            }
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        // shift surviving elements left over the spaces left by removed elements
        final boolean anyToRemove = removeCount > 0;
        if (anyToRemove) {
            final int newSize = size - removeCount;
            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
                i = removeSet.nextClearBit(i);
                elementData[j] = elementData[i];
            }
            for (int k=newSize; k < size; k++) {
                elementData[k] = null;  // Let gc do its work
            }
            this.size = newSize;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            modCount++;
        }
        return anyToRemove;
    }

public boolean removeIf(Predicate<? super E> filter) {

Objects.requireNonNull(filter);

// figure out which elements are to be removed

// any exception thrown from the filter predicate at this stage

// will leave the collection unmodified

int removeCount = 0;

final BitSet removeSet = new BitSet(size);

final int expectedModCount = modCount;

final int size = this.size;

for (int i=0; modCount == expectedModCount && i < size; i++) {

@SuppressWarnings("unchecked")

final E element = (E) elementData[i];

if (filter.test(element)) {

removeSet.set(i);

removeCount++;

}

if (modCount != expectedModCount) {

throw new ConcurrentModificationException();

}

// shift surviving elements left over the spaces left by removed elements

final boolean anyToRemove = removeCount > 0;

if (anyToRemove) {

final int newSize = size - removeCount;

for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {

i = removeSet.nextClearBit(i);

elementData[j] = elementData[i];

}

for (int k=newSize; k < size; k++) {

elementData[k] = null; // Let gc do its work

}

this.size = newSize;

if (modCount != expectedModCount) {

throw new ConcurrentModificationException();

}

modCount++;

}

return anyToRemove;

}

به نظر می‌رسد اگر هنوز پایبندی خود را به نسخه‌های قبلی جاوا حفظ کرده‌اید، وقت آن است تجدید نظری بکنید. نظر شما چیست؟

برچسب ها

فروغ مهرعلیان 20 مهر 1395

3,741 خواندن این مطلب 1 دقیقه زمان می‎برد

‫۲ دیدگاه ها

زهرا خوبی گفت:
27 آبان 1395 در 5:42 ق.ظ
جالب بود
متشکرم
پاسخ
مهدی گفت:
22 مهر 1395 در 11:04 ق.ظ
عالی بود. مطالب خوبی منتشر میکنید. خیلی ممنونم.
پاسخ