ArrayList algorithms: filter and the remove bug · ⁨Thuật toán ArrayList: lọc và lỗi 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.

Tiếng Việt

Thực hiện tác vụ trên toàn bộ danh sách

Bây giờ bạn có thể lưu dữ liệu vào một ArrayList. Tiếp theo chúng ta sẽ xử lý nó.
Các công việc phổ biến: đếm các mục thỏa mãn quy tắc, lọc chúng vào danh sách mới, và loại bỏ một số mục.
Tất cả những việc này đều sử dụng vòng lặp trên danh sách.

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.

Tiếng Việt

Đếm theo quy tắc

Duyệt qua danh sách, kiểm tra từng mục, và cộng 1 vào bộ đếm khi kiểm tra trả về true.
n % 2 == 0 là true khi n là chẵn. n % 2 != 0 là true khi n là lẻ.
Việc này chỉ đọc danh sách, nên vòng lặp for nâng cao là đủ.

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.

Tiếng Việt

Lọc vào danh sách mới

Lọc chỉ giữ lại các mục pass (thỏa mãn) bài kiểm tra.
Mẫu an toàn: tạo một danh sách mới trống, sau đó add mỗi mục pass.
Danh sách cũ không bị thay đổi. Điều này tránh lỗi chúng ta sẽ gặp ngay sau đây.

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.

Tiếng Việt

Lỗi remove-while-iterating (xóa trong lúc duyệt)

Nó trông rất dễ: duyệt từ đầu và remove(i) các mục bạn không muốn.
Nhưng remove(i) sẽ đẩy mọi mục sau đó một bước sang trái. Vòng lặp sau đó tăng 1 lên i và bỏ sót mục vừa di chuyển vào vị trí cũ.
Ví dụ dưới đây cố gắng xóa tất cả các số chẵn nhưng bỏ sót một số.

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.

Tiếng Việt

Tại sao lại bỏ sót

Ban đầu: [2, 4, 5], i = 0. 2 là số chẵn, xóa nó. Danh sách trở thành [4, 5].
4 đã trượt xuống chỉ mục 0. Nhưng vòng lặp giờ đây sẽ gán i = 1.
Tại i = 1, ta nhìn vào 5, không phải 4. 4 đã không bao giờ được kiểm tra. Nó vẫn nằm trong danh sách.

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.

Tiếng Việt

Giải pháp: duyệt ngược

Duyệt từ chỉ số cuối cùng xuống đến 0.
Khi bạn xóa chỉ số i, chỉ các mục sau i bị dịch chuyển — và bạn đã đi qua những mục đó rồi.
Các chỉ số bạn vẫn cần truy cập sẽ nhỏ hơn i, nên không có mục nào bị đẩy khỏi vị trí của bạn.

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.

Tiếng Việt

Lưu ý về vòng lặp for nâng cao

Bạn có thể bị cám dỗ muốn xóa bên trong for (int x : nums).
Đừng. Thay đổi kích thước danh sách trong lúc vòng lặp for nâng cao sẽ ném ra một ConcurrentModificationException và dừng chương trình.
Đối với việc xóa, luôn sử dụng vòng lặp chỉ số ngược ở trên.

English

Common mistakes

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

Tiếng Việt

Lỗi thường gặp

Xóa trong lúc duyệt từ đầu theo chỉ số sẽ bỏ sót mục tiếp theo (lỗi xóa).
Hãy duyệt ngược, hoặc sử dụng iterator, khi cần xóa.

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.

Tiếng Việt

Bây giờ bạn thử

Mỗi nhiệm vụ điền sẵn khung lớp — viết mã của bạn bên trong main, hoặc hoàn thành phương thức được hiển thị.
Nhấn Chạy để biên dịch và chạy, sau đó Kiểm tra câu trả lời.
Mã của bạn được biên dịch và chạy trên máy chủ, vì vậy ngay cả lần chạy đầu tiên cũng rất nhanh.

Explore · ⁨Khám phá⁩

Filtering a list · ⁨Lọc một danh sách⁩

Removing while looping shifts indices — step through to see why. · ⁨Xóa phần tử trong khi duyệt làm dịch chuyển chỉ mục — hãy bước từng bước để thấy lý do tại sao.⁩

Complete countOdds(ArrayList<Integer> a) so it returns how many numbers in the list are odd. A number is odd when x % 2 != 0. · ⁨Hoàn thiện countOdds(ArrayList<Integer> a) sao cho nó trả về số lượng các số lẻ trong danh sách. Một số được coi là lẻ khi 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. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

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. · ⁨Hoàn thiện keepPositives(ArrayList<Integer> a). Tạo và trả về một ArrayList<Integer> mới chỉ chứa các số lớn hơn 0, giữ nguyên thứ tự ban đầu. Không thay đổi 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. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

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). · ⁨Hoàn thiện removeEvens(ArrayList<Integer> a) sao cho nó xóa tất cả các số chẵn khỏi chính a. Duyệt ngược theo chỉ mục để không bỏ sót phần tử nào. Không trả về gì (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. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

ArrayList algorithms: filter and the remove bug · ⁨Thuật toán ArrayList: lọc và lỗi remove⁩

Doing work on a whole list

Thực hiện tác vụ trên toàn bộ danh sách

Counting with a rule

Đếm theo quy tắc

Filtering into a new list

Lọc vào danh sách mới

The remove-while-iterating bug

Lỗi remove-while-iterating (xóa trong lúc duyệt)

Why it skips

Tại sao lại bỏ sót

The fix: loop backwards

Giải pháp: duyệt ngược

A note on the enhanced for-loop

Lưu ý về vòng lặp for nâng cao

Common mistakes

Lỗi thường gặp

Now you try

Bây giờ bạn thử

Filtering a list · ⁨Lọc một danh sách⁩

Handout · ⁨Tài liệu⁩

Log in or create account · ⁨Đăng nhập hoặc tạo tài khoản⁩

Your subject · ⁨Môn học của bạn⁩

All sections · ⁨Tất cả các mục⁩

Feedback & help · ⁨Phản hồi & hỗ trợ⁩