ArrayList algorithms: filter and the remove bug · ⁨ArrayList algorithms: filter และ error bug ของ remove⁩

English

Doing work on a whole list

Now you can store data in an ArrayList. Next we process it.
Common jobs: count items that match a rule, filter them into a new list, and remove some of them.
All of these use a loop over the list.

ไทย

การทำงานกับทั้งรายการ

ตอนนี้คุณสามารถเก็บข้อมูลใน ArrayList接下来 เรา process ข้อมูลนั้น
งานทั่วไป: count องค์ประกอบที่ตรงกับกฎ, filter它们 into一个新列表, และ remove บางส่วนออก
ทั้งหมดนี้ใช้ลูปวนรอบรายการ

English

Counting with a rule

Walk the list, test each item, and add 1 to a counter when the test is true.
n % 2 == 0 is true when n is even. n % 2 != 0 is true when n is odd.
This only reads the list, so an enhanced for-loop is fine.

ไทย

การนับด้วยกฎ

เดินผ่านรายการ ทดสอบแต่ละองค์ประกอบ และเพิ่ม 1 ไปยังตัวนับเมื่อการทดสอบเป็นจริง
n % 2 == 0 เป็นจริงเมื่อ n เป็น คู่ n % 2 != 0 เป็นจริงเมื่อ n เป็น คี่
สิ่งนี้เพียง read รายการ ดังนั้น enhanced for-loop ก็เพียงพอแล้ว

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(4);
        nums.add(7);
        nums.add(10);
        nums.add(3);

        int evens = 0;
        for (int x : nums) {
            if (x % 2 == 0) {
                evens = evens + 1;
            }
        }
        System.out.println(evens);   // 2
    }
}

English

Filtering into a new list

Filtering keeps only the items that pass a test.
A safe pattern: make an empty new list, then add each item that passes.
The old list is not changed. This avoids the bug we see next.

ไทย

การกรองเข้ารายการใหม่

Filtering เก็บไว้เฉพาะองค์ประกอบที่ผ่านการทดสอบ
รูปแบบที่ปลอดภัย: สร้าง empty รายการใหม่ แล้ว add 각元素ที่ผ่านการทดสอบ
รายการเก่าไม่ถูกเปลี่ยน สิ่งนี้จะหลีกเลี่ยง bug ที่เราจะเห็นต่อไป

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(4);
        nums.add(7);
        nums.add(10);
        nums.add(3);

        ArrayList<Integer> bigOnes = new ArrayList<Integer>();
        for (int x : nums) {
            if (x >= 5) {
                bigOnes.add(x);
            }
        }
        System.out.println(bigOnes);   // [7, 10]
    }
}

English

The remove-while-iterating bug

It looks easy: loop forward and remove(i) the items you do not want.
But remove(i) shifts every later item one place left. The loop then adds 1 to i and skips the item that moved into the old spot.
The example below tries to remove all evens but misses one.

ไทย

Bug ของการ remove ขณะ iterate

ดูง่าย: ลูปไปข้างหน้าและ remove(i)的元素ที่ไม่ต้องการ
แต่ remove(i) will shift ทุกองค์ประกอบถัดไป one place left. Then the loop adds 1 to i and skips the element that moved into the old spot.
ตัวอย่างด้านล่างพยายามลบเลขคู่ทั้งหมดแต่ misses หนึ่งตัว

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(2);
        nums.add(4);   // this one gets skipped!
        nums.add(5);

        // BUGGY: forward loop while removing
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) % 2 == 0) {
                nums.remove(i);
            }
        }
        System.out.println(nums);   // [4, 5]  -- wrong, 4 was missed
    }
}

English

Why it skips

Start: [2, 4, 5], i = 0. 2 is even, remove it. List becomes [4, 5].
The 4 slid down into index 0. But the loop now sets i = 1.
At i = 1 we look at 5, not 4. The 4 was never checked. It stays in.

ไทย

ทำไมถึง skip

Start: [2, 4, 5], i = 0. 2 is even, remove it. List becomes [4, 5].
4 ได้เลื่อนลงไปยัง index 0 แต่ตอนนี้ลูปจะตั้งค่า i = 1
ที่ i = 1 เราจะดูที่ 5 ไม่ใช่ 4 ค่า 4 ไม่เคยถูก ตรวจสอบ มันจึงยังคงอยู่ในที่เดิม

English

The fix: loop backwards

Walk from the last index down to 0.
When you remove index i, only items after i shift — and you have already passed those.
The indexes you still need to visit are smaller than i, so nothing moves out from under you.

ไทย

The fix: loop backwards

Walk from the last index down to 0.
เมื่อคุณลบ index i ออก รายการอื่นๆ ที่อยู่ ถัดไป จาก i จะเลื่อน position แต่คุณได้ผ่านจุดเหล่านั้นไปแล้ว
Index ที่คุณยังต้อง访问มีค่าน้อยกว่า i ดังนั้นไม่มีอะไรเคลื่อนย้ายออกใต้เท้าของคุณ

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(2);
        nums.add(4);
        nums.add(5);

        // SAFE: backward loop while removing
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (nums.get(i) % 2 == 0) {
                nums.remove(i);
            }
        }
        System.out.println(nums);   // [5]  -- correct
    }
}

English

A note on the enhanced for-loop

You may be tempted to remove inside for (int x : nums).
Do not. Changing the list size during an enhanced for-loop throws a ConcurrentModificationException and stops the program.
For removing, always use the backward index loop above.

ไทย

A note on the enhanced for-loop

You may be tempted to remove inside for (int x : nums).
ห้ามทำ การเปลี่ยนขนาดของลิสต์ขณะอยู่ใน enhanced for-loop จะเกิด ConcurrentModificationException และทำให้โปรแกรมหยุดทำงาน
สำหรับการจัดลบ ให้ใช้ always loop แบบ backward index ข้างบนเสมอ

English

Common mistakes

Removing while looping forward by index skips the next item (the remove bug).
Loop backwards, or use an iterator, when removing.

ไทย

ข้อผิดพลาดที่พบบ่อย

การจัดลบขณะวนลูปไปข้างหน้าด้วย index จะข้ามรายการถัดไป (ความผิดพลาดของการจัดลบ)
Loop backwards, or use an iterator, when removing.

English

Now you try

Each task pre-fills the class skeleton — write your code inside main, or complete the method shown.
Press Run to compile and run, then Check answer.
Your code compiles and runs on the server, so even the first run is fast.

ไทย

ลองดูเลย

Each task เติม skeleton class ไว้ล่วงหน้า — เขียนโค้ดของคุณ ภายใน main, หรือเติมเต็ม method ที่แสดง
กด Run เพื่อ compile และ run, แล้วกด Check answer
โค้ดของคุณ compile และ run บน server, ดังนั้นแม้การ run ครั้งแรกก็เร็ว

Explore · ⁨สำรวจ⁩

Filtering a list · ⁨การกรอง (filtering) list⁩

Removing while looping shifts indices — step through to see why. · ⁨การลบขณะ遍历 ทำให้ indices เลื่อน — Iterate เพื่อให้เห็นเหตุผล.⁩

Complete countOdds(ArrayList<Integer> a) so it returns how many numbers in the list are odd. A number is odd when x % 2 != 0. · ⁨เติม countOdds(ArrayList<Integer> a) ให้สมบูรณ์เพื่อให้กลับคืนว่ามีตัวเลข奇数กี่ตัวใน list. ตัวเลขเป็น奇数เมื่อ x % 2 != 0.⁩

import java.util.ArrayList;

public class ListUtil {
    // Return how many numbers in a are odd.
    public static int countOdds(ArrayList<Integer> a) {
        return 0;   // change this
    }
}

Click Run to see the output here. · ⁨คลิก Run เพื่อดูผลลัพธ์ที่นี่⁩

Complete keepPositives(ArrayList<Integer> a). Build and return a new ArrayList<Integer> that holds only the numbers greater than 0, in their original order. Do not change a. · ⁨เติม keepPositives(ArrayList<Integer> a) ให้สมบูรณ์. สร้างและกลับคืน ArrayList<Integer> ใหม่ ที่เก็บเฉพาะตัวเลขที่มีค่ามากกว่า 0,按照顺序เดิม. อย่า แก้ไข a.⁩

import java.util.ArrayList;

public class ListUtil {
    // Return a new list with only the numbers > 0.
    public static ArrayList<Integer> keepPositives(ArrayList<Integer> a) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        // add the positives here
        return result;
    }
}

Click Run to see the output here. · ⁨คลิก Run เพื่อดูผลลัพธ์ที่นี่⁩

Complete removeEvens(ArrayList<Integer> a) so it removes every even number from a itself. Loop backwards by index so you do not skip items. Return nothing (void). · ⁨เติม removeEvens(ArrayList<Integer> a) ให้สมบูรณ์เพื่อลบ ทุก คู่จาก a เอง.遍历 ถอยหลัง bằng index เพื่อไม่ให้ข้าม item. กลับคืนอะไรเลย (void).⁩

import java.util.ArrayList;

public class ListUtil {
    // Remove every even number from a. Loop backwards!
    public static void removeEvens(ArrayList<Integer> a) {
        // your code here
    }
}

Click Run to see the output here. · ⁨คลิก Run เพื่อดูผลลัพธ์ที่นี่⁩

ArrayList algorithms: filter and the remove bug · ⁨ArrayList algorithms: filter และ error bug ของ remove⁩

Doing work on a whole list

การทำงานกับทั้งรายการ

Counting with a rule

การนับด้วยกฎ

Filtering into a new list

การกรองเข้ารายการใหม่

The remove-while-iterating bug

Bug ของการ remove ขณะ iterate

Why it skips

ทำไมถึง skip

The fix: loop backwards

The fix: loop backwards

A note on the enhanced for-loop

A note on the enhanced for-loop

Common mistakes

ข้อผิดพลาดที่พบบ่อย

Now you try

ลองดูเลย

Filtering a list · ⁨การกรอง (filtering) list⁩

Handout · ⁨เอกสารประกอบการเรียน⁩

Log in or create account · ⁨เข้าสู่ระบบหรือสร้างบัญชี⁩

Your subject · ⁨วิชาของคุณ⁩

All sections · ⁨ทุกส่วน⁩

Feedback & help · ⁨ความคิดเห็น &ความช่วยเหลือ⁩