Java: Lọc ArrayList hiệu quả?

Question

Tôi cần lọc ArrayList và xóa các phần tử đã tìm thấy. Tương đối mới với Java, tôi tự hỏi phương pháp hiệu quả nhất là đạt được điều này (vấn đề bởi vì nó chạy trên các thiết bị di động). Hiện tại tôi làm điều này:

// We display only top-level dealers (parentId=-10) 
ArrayList<DealerProductCount> subDealers = new ArrayList<DealerProductCount>(); 
for (DealerProductCount dealer : wsResponse.Dealers) { 
    if (dealer.ParentId != -10) subDealers.add(dealer); 
} 
wsResponse.Dealers.removeAll(subDealers); 

Nó có thể được thực hiện mà không có vật thể tạm thời không? Có thể bằng cách trực tiếp thao tác (loại bỏ) các phần tử của danh sách đang được lặp lại?

Answer 1

hiệu quả loại bỏ một số yếu tố từ một ArrayList đòi hỏi một số suy nghĩ. Cách tiếp cận ngây thơ là một cái gì đó như thế này:

Iterator<DealerProductCount> it = wsResponse.Dealers.iterator(); 
while (it.hasNext()) { 
    if (it.next().ParentId != -10) { 
     it.remove(); 
    } 
} 

Vấn đề là mỗi lần bạn loại bỏ phần tử bạn sao chép (trung bình) một nửa số phần tử còn lại. Điều này là do việc loại bỏ một phần tử khỏi ArrayList đòi hỏi phải sao chép tất cả các phần tử sau khi phần tử đã xóa một vị trí sang trái.

Giải pháp ban đầu của bạn liên quan đến danh sách các thành phần cần xóa cũng thực sự giống nhau. Thật không may, các thuộc tính của một ArrayList không cho phép removeAll làm tốt hơn so với ở trên.

Nếu bạn mong đợi để loại bỏ một số yếu tố, sau đây là hiệu quả hơn:

ArrayList<DealerProductCount> retain = 
     new ArrayList<DealerProductCount>(wsResponse.Dealers.size()); 
for (DealerProductCount dealer : wsResponse.Dealers) { 
    if (dealer.ParentId == -10) { 
     retain.add(dealer); 
    } 
} 
// either assign 'retain' to 'wsResponse.Dealers' or ... 
wsResponse.Dealers.clear(); 
wsResponse.Dealers.addAll(retain); 

Chúng tôi đang sao chép (gần như) toàn bộ danh sách hai lần, vì vậy đây sẽ chia đều (trung bình) nếu bạn loại bỏ ít nhất là 4 phần tử.

---

Thật thú vị khi lưu ý rằng ngôn ngữ lập trình chức năng/thư viện điển hình hỗ trợ phương pháp lọc và có thể thực hiện tác vụ này trong một lần chuyển qua danh sách; tức là hiệu quả hơn rất nhiều. Tôi nghĩ chúng ta có thể mong đợi những cải tiến đáng kể nếu/khi Java hỗ trợ lambdas, và các API thu thập được nâng cao để sử dụng chúng.

Answer 2

Nếu bạn sử dụng trình lặp, bạn có thể xóa các phần tử an toàn trong khi lặp lại.

Answer 3

Một cách sẽ sử dụng lặp thay vì cho từng:

Iterator<DealerProductCount> iter = wsResponse.Dealers.iterator() 
while(iter.hasNext()) { 
    if (iter.next().ParentId != -10) iter.remove(); 
}