Chọn phần tử có số lần xuất hiện tối đa trong đa số

Question

Tôi có thể muốn thuật lại câu hỏi thành "Làm cách nào để chọn mục đầu tiên trong một Multiset?" bởi vì có vẻ như Multiset đã được sắp xếp theo tần số.

Tôi có một Multiset myList = Multiset.create();

[maa00 mfnt11 malignlft mbold mlt18 mfl x 3, caa00 cfnt11 calignlft cbold clt17 cfl] 

Tôi không thể tìm thấy bất kỳ phương pháp nào như myList.getIndex (0). Xin lưu ý, cuối cùng, tôi cần số lượng phần tử có tần suất tối đa.

Có một lớp lót nào cho điều này không? Hay tôi phải lặp lại điều đó?

Cập nhật: Tôi nhận được tần số tối đa sử dụng:

myList.count(Multisets.copyHighestCountFirst(myList).asList().get(0))); 

Nhưng điều này là quá chậm. Bạn có thể đề nghị, tôi nên sử dụng chính xác những gì?

Cập nhật 1: Sử dụng bản sao ở trênHighestCountPhương pháp đầu tiên đang chứng minh quá chậm. Trong một ví dụ của vòng lặp, nó được lấy 80 + mili giây trái ngược với trung bình 40 mili giây sử dụng mà không có nó. Trong vòng lặp lớn, tôi có nên lặp lại đơn giản không?

Cập nhật 2: Got nó làm việc sử dụng:

myList.count(myList.entrySet().iterator().next().getElement()) 

Nếu không có gần như bằng không ảnh hưởng đến hiệu suất. Tôi vẫn tự hỏi liệu có cách nào tốt hơn để làm điều đó không.

Phụ chú: Trong Python tôi đã làm như vậy với:

j = defaultdict(int) 
for k in clList: 
    j[k] +=1 
result1 = max(j.iteritems(), key=lambda x:x[1]) //count of frequency of item with max count 

Answer 1

Đã có rất nhiều lựa chọn thay thế ném khoảng giữa câu hỏi của bạn và câu trả lời khác được đăng, nhưng nhiều người trong số họ dường như phụ thuộc vào ý tưởng rằng .get(0) hoặc .iterator().next() sẽ giúp bạn có được các yếu tố thường gặp nhất. Nó sẽ không!

Hai lựa chọn hợp lý duy nhất của bạn là Multisets.copyHighestCountFirst(bag).elementSet().iterator().next(), lãng phí như bạn nói, hoặc lặp qua số entrySet theo cách thủ công và kiểm tra từng xem liệu đó có phải là thường xuyên nhất từ ​​trước đến nay hay không.

Bạn nên gửi yêu cầu tính năng ổi để trích xuất phần tử thường xuyên nhất. Tôi không thể hứa điều gì sẽ xảy ra với nó, nhưng nó đáng yêu cầu.

Answer 2

Do sửa đổi của bạn và phân nhịp nó không rõ ràng những gì bạn muốn. Ngoài ra, bằng cách sử dụng myList làm tên biến là bội số không phải là mô tả - tôi sẽ sử dụng bag làm tên biến cho multiset (sau cùng là túi).

1. "có vẻ như MultiSet đã được sắp xếp theo tần số" - là nó hay là nó không sắp xếp theo tần số?

   ImmutableMultiset<String> bag = ImmutableMultiset.of(
       "c0ffee", "abba", "mfl", "mfl", "mfl", "c0ffee"); 
   

   là [c0ffee x 2, abba, mfl x 3] vì nó sử dụng để chèn, vì vậy bộ sưu tập của bạn thể được đặt đúng cách trùng hợp ngẫu nhiên (Tôi không biết nếu nó là một trường hợp ở đây). Nếu bạn không chắc về đặt hàng, chỉ cần sử dụng

   ImmutableMultiset<String> sortedBag = Multisets.copyHighestCountFirst(bag) 
   

   cung cấp [mfl x 3, c0ffee x 2, abba]. Kể từ khi Multisets.copyHighestCountFirst trả về nhiều lần không thể thay đổi, bạn không phải sử dụng nó trong vòng lặp giả định rằng multiset của bạn không thay đổi. Nếu bạn vừa làm một microbenchmark ngớ ngẩn và thấy rằng việc sử dụng Multisets.copyHighestCountFirst có nghĩa là gấp đôi so với 80 ms so với 40 ms - hãy quên nó vì premature optimization is the root of all evil. Tôi cho rằng chúng tôi đã đặt hàng đúng cách sortedBag vào thời điểm này.

2. Từ những gì tôi nhìn thấy bạn muốn đếm của hầu hết các yếu tố chung trong túi mà chỉ đơn giản là:

   int count = sortedBag.entrySet().iterator().next().getCount(); 
   

   hoặc nếu MultiSet của bạn là ImmutableMultiset:

   int count = sortedBag.entrySet().asList().get(0).getCount(); 
   

   Lưu ý rằng sortedBag.entrySet() là một bộ sưu tập của Multiset.Entry trong đó có cả phần tử và đếm để chọn một trong những bạn muốn.

3. Có ImmutableMultiset phép bạn sử dụng nó ImmutableList xem trên đó bạn có thể gọi get(0) để lấy phần tử:

   sortedBag.asList().get(0) 
   

   mang đến cho bạn chỉ phần tử (đây: a string) mà không cần đếm, vì vậy nếu kế hoạch của bạn là chỉ lấy phần tử bạn có thể sử dụng asList() thay vì chơi với trình vòng lặp.

Answer 3

giải pháp Một thay thế mà không cần một vòng lặp rõ ràng - nhưng sẽ chạy trong thời gian tuyến tính trong số các yếu tố khác nhau, trong đó hầu hết các giải pháp khác không thể - sẽ

Ordering.natural().onResultOf(new Function<Multiset.Entry<Foo>, Integer>() { 
    public Integer apply(Multiset.Entry<Foo> entry) { 
    return entry.getCount(); 
    } 
}.max(multiset.entrySet()).getElement();