Đó là hiệu quả hơn: sử dụng RemoveAll() hoặc sử dụng kỹ thuật HashMap sau để giữ lại chỉ thay đổi bản ghi trong một ArrayList

Question

tôi có 2 ArrayList s A và B của cùng một datastructure C (hashCode() và equals() ghi đè). C đại diện cho hồ sơ của học sinh. Hai danh sách có cùng kích thước và đại diện cho hồ sơ học sinh mới và các bản ghi cũ tương ứng (các sinh viên giống nhau trong cả hai danh sách, thứ tự có thể khác nhau). Tôi chỉ muốn giữ những bản ghi trong A đã được thay đổi. Như vậy, tôi làm:

A.removeAll(B) 

Theo javadocs, điều này sẽ mất mỗi bản ghi của A và so sánh với mỗi bản ghi của B, và nếu nó tìm thấy cả hai bằng nhau, nó sẽ loại bỏ các bản ghi từ A. Nếu một hồ sơ của A không được tìm thấy bằng bất kỳ bản ghi nào trong B, và vì tất cả học sinh trong A cũng ở B, điều đó có nghĩa là bản ghi A đã thay đổi. Vấn đề là nó dễ dàng của n phức tạp vuông.

cách tiếp cận khác có thể là:

Map<C> map = new HashMap<C>(); 
for (C record : B){ 
    map.add(record.getStudentId(),record); 
} 
List<C> changedRecords = new ArrayList<C>(); 
for (C record : A){ 
    if (record.equals(map.get(record.getStudentId())){ 
     changedRecords.add(record); 
    } 
} 

Tôi nghĩ rằng đây có thể là của một phức tạp thấp hơn so với giải pháp trên. Đúng không ?

Answer 1

Có các thuật toán thứ hai là tốt hơn so với O(n^2), kể từ khi bạn có hai vòng, một khác nhau, trên B và khác qua A và bạn (khấu hao) làm việc liên tục trong mỗi vòng lặp, giải pháp mới của bạn chạy trong O(|A| + |B|).

Tôi cho rằng bạn không có bất kỳ mục nhập trùng lặp nào. Nếu đây là trường hợp, bạn cũng có thể đi qua một HashSet (thay đổi để LinkedHashSet nếu bạn muốn giữ gìn trật tự trong A):

HashSet<C> tmp = new HashSet<C>(A); 
tmp.removeAll(B);      // Linear operation 
A = new ArrayList<C>(tmp); 

(Hoặc nếu tự không quan trọng với bạn, bạn có thể sử dụng HashSet là tất cả các cách thức thông qua.)

---

Như đã chỉ ra bởi @Daud trong các ý kiến ​​dưới đây, HashSet.removeAll(Collection c) thực sự gọi c.contains lặp đi lặp lại nếu kích thước của tập băm nhỏ hơn bộ sưu tập ảnh hưởng đến sự phức tạp (ít nhất là trong OpenJDK). Điều này là do việc triển khai luôn chọn để lặp qua bộ sưu tập nhỏ hơn.

Answer 2

Những gì bạn có thể tiết kiệm về sự phức tạp mà bạn có thể bị mất trong phân bổ bộ nhớ vì vậy không nhất thiết phải hiệu quả hơn. Arrraylist sử dụng một cái gì đó tương tự như một thuật toán phân vùng tại chỗ để chạy xuống mảng sao lưu và kiểm tra so sánh.

Khi so sánh nó chỉ đơn giản là tìm kiếm chỉ mục lần xuất hiện đầu tiên của trận đấu với mảng sao lưu Object[]. Thuật toán duy trì hai chỉ mục, một để lặp qua mảng sao lưu và một là một trình giữ chỗ cho các kết quả phù hợp. Trong trường hợp của một trận đấu nó chỉ đơn giản là di chuyển chỉ số trên mảng sao lưu và chuyển sang phần tử đến tiếp theo; điều này tương đối rẻ.

Nếu nói đến một điểm mà nó nhận thấy bộ sưu tập đến không chứa giá trị tại chỉ mục hiện tại trong mảng sao lưu, nó chỉ ghi đè phần tử ở vị trí cuối cùng xảy ra với phần tử tại chỉ mục hiện tại mà không bị phát sinh. cấp phát bộ nhớ mới. Mẫu này lặp lại cho đến khi tất cả các phần tử trong ArrayList đã được so sánh với bộ sưu tập đến, do đó sự phức tạp mà bạn quan tâm.

Ví dụ: Hãy xem xét danh sách mảng A có 1,2,4,5 và tập hợp 'C' với 4,1 mà chúng tôi đối sánh; muốn xóa 4 và 1. ở đây là mỗi lần lặp trên vòng lặp for mà sẽ đi 0 -> 4

Iteration: r là vòng lặp for index trên ArrayList một for (; r < size; r++)

r = 0 (không chứa C 1 ? Có, bỏ qua phần tiếp theo) A: 1,2,4,5 w = 0

r = 1 (C có 2 không? Không, sao chép giá trị tại r vào điểm được trỏ tới bởi w ++) A: 2,2,4,5 w = 1

r = 2 (Liệu C chứa 4 ?, Có skip) A: 2,2,4,5 w = 1

r = 3 (C có chứa 5? Không, sao chép các giá trị tại r vào vị trí trỏ đến bởi w ++)

A: 2,5,4,5 w = 2

r = 4, dừng

Hãy so sánh w với kích thước của mảng sao lưu là 4. Vì chúng không bằng Null ra các giá trị từ w vào cuối mảng và đặt lại kích thước.

A: 2,5 kích thước 2

Được xây dựng trong removeAll cũng xem ArrayLists có thể chứa null. Bạn có thể ném một NPE vào record.getStudentId() trong giải pháp của bạn ở trên. Cuối cùng, removeAll bảo vệ chống lại các ngoại lệ trong so sánh trên Collection.contains. nếu điều đó xảy ra, nó sử dụng cuối cùng để làm một memcopy bản địa để bảo vệ mảng sao lưu từ tham nhũng một cách hiệu quả cao.

Answer 3

Chắc chắn 'thuật toán' thứ hai tốt hơn so với lần đầu tiên xem xét phân tích phân bổ. nó là cách tốt nhất? bạn có cần nó không nó sẽ gây ra bất kỳ tác động có thể nhìn thấy cho người dùng về hiệu suất hiện số lượng các mục trong danh sách phát triển rất lớn, rằng điều này sẽ trở thành một nút cổ chai trong hệ thống?

Cách tiếp cận đầu tiên dễ đọc hơn, chuyển tải ý định của bạn đến những người duy trì mã. Ngoài ra, nên sử dụng API 'thử nghiệm' thay vì phát minh lại bánh xe (trừ khi thật cần thiết) Máy vi tính đã trở nên nhanh đến nỗi chúng tôi không nên thực hiện bất kỳ tối ưu hóa sớm nào.

nếu thấy cần thiết tôi có thể đi với một giải pháp sử dụng Set, tương tự như

Answer 4

Tôi đã gặp một nút cổ chai hiệu suất trong thành viên RemoveAll trong một số trường (EMF mô hình thao tác liên quan) @ aioob của. Đối với ArrayList như đã đề cập ở trên, chỉ cần sử dụng removeAll tiêu chuẩn, nhưng nếu A là ví dụ một EList, n^2 có thể gặp phải.

Do đó, tránh dựa vào các thuộc tính tốt ẩn của các triển khai cụ thể của Danh sách < T>; Set.contains() O (1) là một bảo đảm, sử dụng nó để ràng buộc thuật toán ràng buộc.

Tôi sử dụng mã sau để tránh các bản sao vô dụng; ý định là bạn đang quét cấu trúc dữ liệu tìm các phần tử không có liên quan mà bạn không muốn và thêm chúng vào "todel".

Vì một số lý do như tránh sửa đổi đồng thời, bạn đang điều hướng một cây, v.v., bạn không thể xóa các phần tử khi đang thực hiện quá trình truyền tải này. Vì vậy, chúng tôi tích lũy chúng vào một HashSet "todel".Trong chức năng, chúng ta cần phải sửa đổi "container" tại chỗ, vì nó thường là một thuộc tính của người gọi, nhưng việc sử dụng remove (int index) trên "container" có thể tạo ra một bản sao vì sự dịch chuyển trái của các phần tử. Chúng tôi sử dụng một bản sao "nội dung" để đạt được điều này.

Đối số mẫu là bởi vì trong quá trình chọn, tôi thường nhận được các kiểu con của C, nhưng vui lòng sử dụng < T> ở mọi nơi.

/** 
* Efficient O (n) operation to removeAll from an aggregation. 
* @param container a container for a set of elements (no duplicates), some of which we want to get rid of 
* @param todel some elements to remove, typically stored in a HashSet. 
*/ 
public static <T> void removeAll (List<T> container, Set<? extends T> todel) { 
    if (todel.isEmpty()) 
     return; 
    List<T> contents = new ArrayList<T>(container); 
    container.clear(); 
    // since container contains no duplicates ensure |B| max contains() operations 
    int torem = todel.size(); 
    for (T elt : contents) { 
     if (torem==0 || ! todel.contains(elt)) { 
      container.add(elt); 
     } else { 
      torem--; 
     } 
    } 
} 

Vì vậy, trong trường hợp của bạn, bạn sẽ gọi với: removeAll (A, new HashSet < C> (B)); thanh toán một bản B nếu bạn thực sự không thể tích lũy vào một Bộ < C> trong giai đoạn lựa chọn.

Đặt trong lớp tiện ích và nhập tĩnh để dễ sử dụng.