2010-05-27 35 views
5

Tôi đã tạo một phương thức lấy hai số Collection<String> làm đầu vào và sao chép một cái khác.Câu hỏi về hiệu suất Bộ sưu tập Java

Tuy nhiên, tôi không chắc liệu tôi có nên kiểm tra xem các bộ sưu tập có chứa các phần tử giống nhau trước khi tôi bắt đầu sao chép hay không hoặc chỉ cần sao chép bất kể. Đây là phương pháp:

/** 
    * Copies from one collection to the other. Does not allow empty string. 
    * Removes duplicates. 
    * Clears the too Collection first 
    * @param src 
    * @param dest 
    */ 
public static void copyStringCollectionAndRemoveDuplicates(Collection<String> src, Collection<String> dest) { 
    if(src == null || dest == null) 
    return; 

    //Is this faster to do? Or should I just comment this block out 
    if(src.containsAll(dest)) 
    return; 

    dest.clear(); 
    Set<String> uniqueSet = new LinkedHashSet<String>(src.size()); 
    for(String f : src) 
    if(!"".equals(f)) 
    uniqueSet.add(f); 

    dest.addAll(uniqueSet); 
} 

Có lẽ nó là nhanh hơn để chỉ loại bỏ các

if(src.containsAll(dest)) 
    return; 

Bởi vì phương pháp này sẽ lặp qua các bộ sưu tập anyways.

+2

Chỉ là một nhận xét nhỏ, không liên quan đến câu hỏi của bạn: mục tiêu và có ý nghĩa tương tự. Vì bạn đang sao chép chuỗi không trống từ đích đến đích, có lẽ nó có thể được đổi tên thành src? –

Trả lời

7

Tôi muốn nói: Xóa nó! Đó là 'mã' trùng lặp, Set đang thực hiện thao tác 'contains()' tương tự để không cần phải xử lý trước nó ở đây. Trừ khi bạn có một bộ sưu tập đầu vào lớn và kiểm tra O (1) rực rỡ cho containsAll() ;-)

Tập hợp đủ nhanh. Nó có độ phức tạp O (n) dựa trên kích thước của đầu vào (một chứa() và (có thể) một phép toán thêm() cho mỗi String) và nếu test target.containsAll() thất bại, hàm contains() được thực hiện hai lần cho mỗi Chuỗi -> ít hiệu suất hơn.

EDIT

Một số mã giả để hình dung câu trả lời của tôi

void copy(source, dest) { 
    bool:containsAll = true; 
    foreach(String s in source) { // iteration 1 
    if (not s in dest) {   // contains() test 
     containsAll=false 
     break 
    } 
    } 
    if (not containsAll) { 
    foreach(String s in source) { // iteration 2 
     if (not s in dest) {  // contains() test 
     add s to dest 
     } 
    } 
    } 
} 

Nếu tất cả các yếu tố nguồn là trong ĐÍCH, sau đó chứa() được gọi một lần cho mỗi yếu tố nguồn. Nếu tất cả trừ các phần tử nguồn cuối cùng là dest (trường hợp xấu nhất), thì hàm contains() được gọi (2n-1) lần (n = kích thước của tập hợp nguồn). Nhưng tổng số thử nghiệm chứa() với phép thử bổ sung luôn bằng hoặc lớn hơn thì cùng mã mà không có phép thử bổ sung.

EDIT 2 Cho phép giả định, chúng tôi có những bộ sưu tập sau:

source = {"", "a", "b", "c", "c"} 
dest = {"a", "b"} 

Thứ nhất, kiểm tra containsAll thất bại, bởi vì chuỗi rỗng trong nguồn không phải là trong dest (đây là một lỗ hổng thiết kế nhỏ trong ma cua ban ;)). Sau đó, bạn tạo một tập hợp tạm thời sẽ là {"a", "b", "c"} (chuỗi rỗng và bỏ qua "c" thứ hai). Cuối cùng, bạn thêm everthing vào dest và giả sử, dest là một ArrayList đơn giản, kết quả là {"a", "b", "a", "b", "c"}. Đó có phải là ý định? Cách thay thế ngắn hơn:

void copy(Collection<String> in, Collection<String> out) { 
    Set<String> unique = new HashSet<String>(in); 
    in.remove(""); 
    out.addAll(unique); 
} 
+0

Cho phép giả định chúng tôi xóa Set và chỉ tạo một bản sao có 'Bộ sưu tập '. Liệu nó có khả thi hơn để kiểm tra sự bình đẳng trước khi thêm vào? –

2

Bạn có thể đánh giá nó nếu nó quan trọng đến mức đó. Tôi nghĩ rằng cuộc gọi tới containsAll() có thể không giúp ích, mặc dù điều đó có thể phụ thuộc vào tần suất hai bộ sưu tập có cùng nội dung.

Nhưng mã này khó hiểu. Tôi đang cố gắng thêm các mục mới vào dest? Vậy tại sao nó rõ ràng đầu tiên? Thay vào đó, hãy trả lại số mới uniqueSet cho người gọi thay vì làm phiền. Và không phải séc containsAll() của bạn đã được đảo ngược chưa?

+0

Rất có khả năng các bộ sưu tập có cùng nội dung và được gọi ít nhất 10 lần –

3

Các containsAll() sẽ không giúp đỡ nếu target có yếu tố hơn dest:
mục tiêu: [a, b, c, d]
dest: [a, b, c]
target.containsAll(dest) là đúng, vì vậy dest là [a, b, c] nhưng phải là [a, b, c, d].

Tôi nghĩ rằng đoạn mã sau là tao nhã hơn:

Set<String> uniqueSet = new LinkedHashSet<String>(target.size()); 
uniqueSet.addAll(target); 
if(uniqueSet.contains("")) 
    uniqueSet.remove(""); 

dest.addAll(uniqueSet); 
+0

Đồng ý ... Tôi thậm chí sẽ bỏ qua cuộc gọi đến 'chứa'. –

+0

Cảm ơn, tôi không nghĩ về điều đó. Trên thực tế, mục tiêu có nhiều khả năng nhiều yếu tố hơn số phận –

1
  1. Quá nhiều tên tham số khó hiểu. desttarget có ý nghĩa gần giống nhau. Bạn nên chọn một cái gì đó như destsource. Nó sẽ làm cho mọi việc rõ ràng hơn cho bạn.

  2. Tôi có một cảm giác (không chắc chắn rằng đó là chính xác) mà bạn sử dụng API bộ sưu tập một cách sai. Giao diện Collection không nói bất kỳ điều gì về tính độc đáo của các phần tử của nó nhưng bạn thêm chất lượng này vào nó.

  3. Sửa đổi các bộ sưu tập được chuyển thành tham số không phải là ý tưởng hay nhất (nhưng như thường lệ, nó phụ thuộc). Trong trường hợp chung, tính đột biến là có hại và không cần thiết. Hơn nữa, những gì nếu bộ sưu tập được thông qua là unmodifiable/không thay đổi? Tốt hơn là trả lại bộ sưu tập mới, sau đó sửa đổi các bộ sưu tập đến.

  4. Collection giao diện có phương thức addAll, removeAll, retainAll. Bạn có thử chúng trước không? bạn đã thực hiện các bài kiểm tra hiệu suất cho các mã như:

    Collection<String> result = new HashSet<String> (dest); 
    result.addAll (target); 
    

    hoặc

    target.removeAll (dest); 
    dest.addAll (target); 
    
1

Mã này là khó có thể đọc và không phải là rất hiệu quả. Tham số "dest" gây nhầm lẫn: Nó được truyền vào như một tham số, sau đó nó được xóa và kết quả được thêm vào nó. Điểm của nó là một tham số? Tại sao không chỉ đơn giản là trả lại một bộ sưu tập mới? Lợi ích duy nhất tôi có thể thấy là người gọi có thể xác định loại bộ sưu tập. Điều đó có cần thiết không?

Tôi nghĩ rằng mã này có thể rõ ràng hơn và có lẽ được viết một cách hiệu quả hơn như sau:

public static Set<String> createSet(Collection<String> source) { 
    Set<String> destination = new HashSet<String>(source) { 
     private static final long serialVersionUID = 1L; 

     public boolean add(String o) { 
      if ("".equals(o)) { 
       return false; 
      } 
      return super.add(o); 
     } 
    }; 
    return destination; 
} 

Một cách khác là tạo ra loại thiết lập riêng của bạn:

public class NonEmptyStringSet extends HashSet<String> { 
    private static final long serialVersionUID = 1L; 

    public NonEmptyStringSet() { 
     super(); 
    } 

    public NonEmptyStringSet(Collection<String> source) { 
     super(source); 
    } 

    public boolean add(String o) { 
     if ("".equals(o)) { 
      return false; 
     } 
     return super.add(o); 
    } 
} 

Cách sử dụng:

createSet(source); 
new NonEmptyStringSet(source); 

Trả lại tập hợp có hiệu suất cao hơn vì trước tiên bạn không phải tạo tập hợp tạm thời và sau đó quảng cáo d tất cả để thu thập số phận.

Lợi ích của loại NonEmptyStringSet là bạn có thể tiếp tục thêm chuỗi và vẫn có kiểm tra chuỗi rỗng.

EDIT1:

Loại bỏ các "if (src.containsAll (dest)) return;" mã giới thiệu một "lỗi" khi gọi phương thức với nguồn == dest; Kết quả là nguồn sẽ trống Ví dụ:.

Collection<String> source = new ArrayList<String>(); 
source.add("abc"); 
copyStringCollectionAndRemoveDuplicates(source, source); 
System.out.println(source); 

EDIT2:

Tôi đã làm một điểm chuẩn nhỏ cho thấy rằng việc triển khai của tôi nhanh hơn khoảng 30%, sau đó là một phiên bản đơn giản của việc triển khai ban đầu của bạn. Ngoài ra, việc triển khai của tôi không sử dụng HashSet thay vì LinkedHashSet, điều này làm cho việc triển khai của tôi nhanh hơn một chút,

đang 63.210

Benchmark:

public class SimpleBenchmark { 
public static void main(String[] args) { 
    Collection<String> source = Arrays.asList("abc", "def", "", "def", "", 
      "jsfldsjdlf", "jlkdsf", "dsfjljka", "sdfa", "abc", "dsljkf", "dsjfl", 
      "js52fldsjdlf", "jladsf", "dsfjdfgljka", "sdf123a", "adfgbc", "dslj452kf", "dsjfafl", 
      "js21ldsjdlf", "jlkdsvbxf", "dsfjljk342a", "sdfdsa", "abxc", "dsljkfsf", "dsjflasd4"); 

    int runCount = 1000000; 
    long start1 = System.currentTimeMillis(); 
    for (int i = 0; i < runCount; i++) { 
     copyStringCollectionAndRemoveDuplicates(source, new ArrayList<String>()); 
    } 
    long time1 = (System.currentTimeMillis() - start1); 
    System.out.println("Time 1: " + time1); 


    long start2 = System.currentTimeMillis(); 
    for (int i = 0; i < runCount; i++) { 
     new NonEmptyStringSet(source); 
    } 
    long time2 = (System.currentTimeMillis() - start2); 
    System.out.println("Time 2: " + time2); 

    long difference = time1 - time2; 
    double percentage = (double)time2/(double) time1; 

    System.out.println("Difference: " + difference + " percentage: " + percentage); 
} 

public static class NonEmptyStringSet extends HashSet<String> { 
    private static final long serialVersionUID = 1L; 

    public NonEmptyStringSet() { 
    } 

    public NonEmptyStringSet(Collection<String> source) { 
     super(source); 
    } 

    @Override 
    public boolean add(String o) { 
     if ("".equals(o)) { 
      return false; 
     } 
     return super.add(o); 
    } 
} 

public static void copyStringCollectionAndRemoveDuplicates(
     Collection<String> src, Collection<String> dest) { 
    Set<String> uniqueSet = new LinkedHashSet<String>(src.size()); 
    for (String f : src) 
     if (!"".equals(f)) 
      uniqueSet.add(f); 

    dest.addAll(uniqueSet); 
} 
} 
0

tôi không thực sự nghĩ rằng tôi hiểu tại sao bạn lại muốn phương pháp này, nhưng giả định rằng nó là đáng giá, tôi sẽ thực hiện nó như sau:

public static void copyStringCollectionAndRemoveDuplicates(
     Collection<String> src, Collection<String> dest) { 
    if (src == dest) { 
     throw new IllegalArgumentException("src == dest"); 
    } 
    dest.clear(); 
    if (dest instanceof Set) { 
     dest.addAll(src); 
     dest.remove(""); 
    } else if (src instance of Set) { 
     for (String s : src) { 
      if (!"".equals(s)) { 
       dest.add(s); 
      } 
     } 
    } else { 
     HashSet<String> tmp = new HashSet<String>(src); 
     tmp.remove(""); 
     dest.addAll(tmp); 
    } 
} 

Ghi chú:

  1. Điều này không giữ nguyên thứ tự của các phần tử trong đối số src trong mọi trường hợp, nhưng chữ ký phương thức ngụ ý rằng điều này không liên quan.
  2. Tôi cố ý không kiểm tra giá trị rỗng. Nó là một lỗi nếu một null được cung cấp như một đối số, và điều đúng đắn cần làm là để cho phép một NullPointerException được ném ra.
  3. Cố gắng sao chép bộ sưu tập vào chính nó cũng là một lỗi.
Các vấn đề liên quan