it-swarm-vi.tech

Cách hiệu quả nhất để tăng giá trị Bản đồ trong Java

Tôi hy vọng câu hỏi này không được coi là quá cơ bản cho diễn đàn này, nhưng chúng ta sẽ thấy. Tôi đang tự hỏi làm thế nào để cấu trúc lại một số mã để có hiệu năng tốt hơn đang được chạy rất nhiều lần.

Giả sử tôi đang tạo danh sách tần suất Word, sử dụng Bản đồ (có thể là HashMap), trong đó mỗi khóa là một Chuỗi có Word được tính và giá trị là một Số nguyên tăng lên mỗi khi tìm thấy mã thông báo của Word.

Trong Perl, việc tăng giá trị như vậy sẽ rất dễ dàng:

$map{$Word}++;

Nhưng trong Java, nó phức tạp hơn nhiều. Đây là cách tôi đang làm:

int count = map.containsKey(Word) ? map.get(Word) : 0;
map.put(Word, count + 1);

Tất nhiên, điều này phụ thuộc vào tính năng autoboxing trong các phiên bản Java mới hơn. Tôi tự hỏi nếu bạn có thể đề xuất một cách hiệu quả hơn để tăng giá trị như vậy. Thậm chí còn có lý do hiệu suất tốt để tránh khung công tác Bộ sưu tập và sử dụng cái gì khác thay thế?

Cập nhật: Tôi đã thực hiện một bài kiểm tra một số câu trả lời. Xem bên dưới.

327
gregory

Một số kết quả kiểm tra

Tôi đã nhận được rất nhiều câu trả lời hay cho câu hỏi này - cảm ơn mọi người - vì vậy tôi quyết định thực hiện một số thử nghiệm và tìm ra phương pháp nào thực sự nhanh nhất. Năm phương pháp tôi đã thử nghiệm là:

  • phương thức "ContainsKey" mà tôi đã trình bày trong câu hỏi
  • phương pháp "TestForNull" được đề xuất bởi Aleksandar Dimitrov
  • phương pháp "AtomicLong" được đề xuất bởi Hank Gay
  • phương pháp "Trove" được đề xuất bởi jrudolph
  • phương pháp "MutableInt" được đề xuất bởi phax.myopenid.com

Phương pháp

Đây là những gì tôi đã làm ...

  1. đã tạo ra năm lớp giống hệt nhau ngoại trừ sự khác biệt được hiển thị bên dưới. Mỗi lớp phải thực hiện một thao tác điển hình cho kịch bản tôi đã trình bày: mở tệp 10 MB và đọc nó, sau đó thực hiện đếm tần số của tất cả các mã thông báo Word trong tệp. Vì việc này chỉ mất trung bình 3 giây, tôi đã thực hiện việc đếm tần số (không phải I/O) 10 lần.
  2. đã tính thời gian cho vòng lặp 10 lần lặp nhưng không phải là thao tác I/O và ghi lại tổng thời gian thực hiện (tính bằng giây đồng hồ) về cơ bản bằng cách sử dụng phương pháp của Ian Darwin trong Sách dạy nấu ăn Java .
  3. thực hiện tất cả năm bài kiểm tra theo chuỗi, và sau đó thực hiện ba lần nữa.
  4. tính trung bình bốn kết quả cho mỗi phương pháp.

Các kết quả

Tôi sẽ trình bày kết quả trước và mã dưới đây cho những ai quan tâm.

Phương thức ContainsKey , như mong đợi, chậm nhất, vì vậy tôi sẽ đưa ra tốc độ của từng phương thức so với tốc độ của phương thức đó.

  • Chứa khóa: 30.654 giây (đường cơ sở)
  • AtomicLong: 29,780 giây (nhanh gấp 1,03 lần)
  • TestForNull: 28,80 giây (nhanh gấp 1,06 lần)
  • Trove: 26.313 giây (nhanh gấp 1,16 lần)
  • MutableInt: 25,747 giây (nhanh gấp 1,19 lần)

Kết luận

Dường như chỉ có phương pháp MutableInt và phương pháp Trove nhanh hơn đáng kể, trong đó chỉ có chúng giúp tăng hiệu suất hơn 10%. Tuy nhiên, nếu phân luồng là một vấn đề, thì AtomicLong có thể hấp dẫn hơn các luồng khác (tôi không thực sự chắc chắn). Tôi cũng đã chạy TestForNull với các biến final, nhưng sự khác biệt là không đáng kể.

Lưu ý rằng tôi chưa sử dụng bộ nhớ định hình trong các tình huống khác nhau. Tôi rất vui khi được nghe từ bất kỳ ai có hiểu biết tốt về cách các phương thức MutableInt và Trove có thể ảnh hưởng đến việc sử dụng bộ nhớ.

Cá nhân, tôi thấy phương thức MutableInt hấp dẫn nhất, vì nó không yêu cầu tải bất kỳ lớp bên thứ ba nào. Vì vậy, trừ khi tôi phát hiện ra vấn đề với nó, đó là cách tôi có khả năng nhất.

Mật mã

Đây là mã quan trọng từ mỗi phương pháp.

Chứa khóa

import Java.util.HashMap;
import Java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
int count = freq.containsKey(Word) ? freq.get(Word) : 0;
freq.put(Word, count + 1);

TestForNull

import Java.util.HashMap;
import Java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
Integer count = freq.get(Word);
if (count == null) {
    freq.put(Word, 1);
}
else {
    freq.put(Word, count + 1);
}

Nguyên tử

import Java.util.concurrent.ConcurrentHashMap;
import Java.util.concurrent.ConcurrentMap;
import Java.util.concurrent.atomic.AtomicLong;
...
final ConcurrentMap<String, AtomicLong> map = 
    new ConcurrentHashMap<String, AtomicLong>();
...
map.putIfAbsent(Word, new AtomicLong(0));
map.get(Word).incrementAndGet();

Quân đội

import gnu.trove.TObjectIntHashMap;
...
TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();
...
freq.adjustOrPutValue(Word, 1, 1);

MutableInt

import Java.util.HashMap;
import Java.util.Map;
...
class MutableInt {
  int value = 1; // note that we start at 1 since we're counting
  public void increment () { ++value;      }
  public int  get ()       { return value; }
}
...
Map<String, MutableInt> freq = new HashMap<String, MutableInt>();
...
MutableInt count = freq.get(Word);
if (count == null) {
    freq.put(Word, new MutableInt());
}
else {
    count.increment();
}
344
gregory

OK, có thể là một câu hỏi cũ, nhưng có một cách ngắn hơn với Java 8:

Map.merge(key, 1, Integer::sum)

Nó làm gì: if key không tồn tại, đặt 1 làm giá trị , nếu không tổng 1 với giá trị được liên kết với khóa . Thêm thông tin tại đây

175
LE GALL Benoît

Một nghiên cứu nhỏ trong năm 2016: https://github.com/leventov/Java-Word-count , mã nguồn chuẩn

Kết quả tốt nhất cho mỗi phương pháp (nhỏ hơn là tốt hơn):

                 time, ms
kolobokeCompile  18.8
koloboke         19.8
trove            20.8
fastutil         22.7
mutableInt       24.3
atomicInteger    25.3
Eclipse          26.9
hashMap          28.0
hppc             33.6
hppcRt           36.5

Thời gian\kết quả không gian: 

42
leventov

Google ổi là bạn của bạn ...

... ít nhất là trong một số trường hợp. Họ có cái này đẹp AtomicLongMap . Đặc biệt tốt vì bạn đang xử lý dài làm giá trị trong bản đồ của bạn.

Ví dụ.

AtomicLongMap<String> map = AtomicLongMap.create();
[...]
map.getAndIncrement(Word);

Cũng có thể thêm nhiều hơn 1 vào giá trị:

map.getAndAdd(Word, 112L); 
33
H6.

@Hank Gay

Theo dõi nhận xét (khá vô dụng) của riêng tôi: Trove trông giống như con đường để đi. Nếu, vì bất kỳ lý do gì, bạn muốn gắn bó với JDK tiêu chuẩn, Bản đồ đồng thờiAtomicLong có thể làm cho mã trở thành tiny bit đẹp hơn, mặc dù YMMV.

    final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
    map.putIfAbsent("foo", new AtomicLong(0));
    map.get("foo").incrementAndGet();

sẽ để lại 1 làm giá trị trong bản đồ cho foo. Trên thực tế, tăng sự thân thiện với luồng là tất cả những gì phương pháp này phải khuyến nghị.

31
Hank Gay

Luôn luôn là một ý tưởng tốt để xem Thư viện bộ sưu tập của Google cho loại điều này. Trong trường hợp này, một Multiset sẽ thực hiện thủ thuật:

Multiset bag = Multisets.newHashMultiset();
String Word = "foo";
bag.add(Word);
bag.add(Word);
System.out.println(bag.count(Word)); // Prints 2

Có các phương pháp giống như Bản đồ để lặp lại các khóa/mục, v.v. Trong thực tế, việc triển khai hiện đang sử dụng HashMap<E, AtomicInteger>, vì vậy bạn sẽ không phải chịu chi phí đấm bốc.

25
Chris Nokleberg
Map<String, Integer> map = new HashMap<>();
String key = "a random key";
int count = map.getOrDefault(key, 0);
map.put(key, count + 1);

Và đó là cách bạn tăng giá trị bằng mã đơn giản.

Lợi ích:

  • Không tạo lớp khác cho int mutable
  • Mã ngắn
  • Dễ hiểu
  • Không có ngoại lệ con trỏ null

Một cách khác là sử dụng phương thức hợp nhất, nhưng điều này là quá nhiều cho việc chỉ tăng giá trị.

map.merge(key, 1, (a,b) -> a+b);

Đề xuất: bạn nên quan tâm đến khả năng đọc mã nhiều hơn là tăng hiệu suất trong hầu hết thời gian.

20
off99555

Một cách khác sẽ là tạo một số nguyên có thể thay đổi:

class MutableInt {
  int value = 0;
  public void inc () { ++value; }
  public int get () { return value; }
}
...
Map<String,MutableInt> map = new HashMap<String,MutableInt> ();
MutableInt value = map.get (key);
if (value == null) {
  value = new MutableInt ();
  map.put (key, value);
} else {
  value.inc ();
}

tất nhiên điều này có nghĩa là tạo ra một đối tượng bổ sung nhưng chi phí so với việc tạo một Integer (ngay cả với Integer.valueOf) không nên quá nhiều.

18
Philip Helger

Bạn có thể sử dụng phương thức compute IfAbsent trong giao diện Map được cung cấp trong Java 8 .

final Map<String,AtomicLong> map = new ConcurrentHashMap<>();
map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet();
map.computeIfAbsent("B", k->new AtomicLong(0)).incrementAndGet();
map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet(); //[A=2, B=1]

Phương thức computeIfAbsent kiểm tra xem khóa đã chỉ định đã được liên kết với một giá trị hay chưa? Nếu không có giá trị liên quan thì nó cố gắng tính giá trị của nó bằng hàm ánh xạ đã cho. Trong mọi trường hợp, nó trả về giá trị hiện tại (hiện tại hoặc được tính toán) được liên kết với khóa được chỉ định hoặc null nếu giá trị được tính là null.

Ở một mặt lưu ý nếu bạn gặp tình huống nhiều luồng cập nhật một số tiền chung, bạn có thể xem LongAdder class.Under tranh chấp cao, thông lượng dự kiến ​​của lớp này cao hơn đáng kể so với AtomicLong, với chi phí tiêu thụ không gian cao hơn.

9
i_am_zero

Xoay vòng bộ nhớ có thể là một vấn đề ở đây, vì mỗi quyền anh của một int lớn hơn hoặc bằng 128 gây ra sự phân bổ đối tượng (xem Integer.valueOf (int)). Mặc dù trình thu gom rác xử lý rất hiệu quả với các đối tượng có thời gian tồn tại ngắn, nhưng hiệu suất sẽ bị ảnh hưởng ở một mức độ nào đó.

Nếu bạn biết rằng số lượng gia tăng được thực hiện sẽ nhiều hơn số lượng khóa (= từ trong trường hợp này), hãy xem xét sử dụng một người giữ int thay thế. Phax đã trình bày mã cho điều này. Đây là một lần nữa, với hai thay đổi (lớp chủ được thực hiện giá trị tĩnh và giá trị ban đầu được đặt thành 1):

static class MutableInt {
  int value = 1;
  void inc() { ++value; }
  int get() { return value; }
}
...
Map<String,MutableInt> map = new HashMap<String,MutableInt>();
MutableInt value = map.get(key);
if (value == null) {
  value = new MutableInt();
  map.put(key, value);
} else {
  value.inc();
}

Nếu bạn cần hiệu năng cao, hãy tìm kiếm triển khai Bản đồ được điều chỉnh trực tiếp theo các loại giá trị nguyên thủy. jrudolph đã đề cập GNU Trove .

Nhân tiện, một thuật ngữ tìm kiếm tốt cho chủ đề này là "biểu đồ".

7
volley

Thay vì gọi chứaKeyKey (), nhanh hơn là gọi map.get và kiểm tra xem giá trị trả về có phải là null hay không.

    Integer count = map.get(Word);
    if(count == null){
        count = 0;
    }
    map.put(Word, count + 1);
5
Glever

Có một vài cách tiếp cận:

  1. Sử dụng một alorithm Bag giống như các bộ có trong Bộ sưu tập của Google.

  2. Tạo vùng chứa có thể thay đổi mà bạn có thể sử dụng trong Bản đồ:

[.__.] 
    class My{
        String Word;
        int count;
    }
 [.__.]

Và sử dụng put ("Word", My mới ("Word")); Sau đó, bạn có thể kiểm tra nếu nó tồn tại và gia tăng khi thêm.

Tránh cuộn giải pháp của riêng bạn bằng cách sử dụng danh sách, bởi vì nếu bạn nhận được tìm kiếm và sắp xếp bên trong, hiệu suất của bạn sẽ bốc mùi. Giải pháp HashMap đầu tiên thực sự khá nhanh, nhưng một giải pháp phù hợp như được tìm thấy trong Bộ sưu tập của Google có lẽ tốt hơn.

Đếm các từ bằng cách sử dụng Bộ sưu tập của Google, trông giống như thế này:

[.__.] 

    HashMultiset s = new HashMultiset();
    s.add("Word");
    s.add("Word");
    System.out.println(""+s.count("Word") );

 [.__.]

Sử dụng HashMultiset khá thanh lịch, bởi vì thuật toán túi chỉ là thứ bạn cần khi đếm từ.

3
tovare

Bộ sưu tập Google HashMultiset:
[.__.] - khá thanh lịch để sử dụng
[.__.] - nhưng tiêu thụ CPU và bộ nhớ

Tốt nhất là có một phương pháp như: Entry<K,V> getOrPut(K); (thanh lịch và chi phí thấp)

Phương pháp như vậy sẽ tính toán hàm băm và chỉ mục một lần, và sau đó chúng ta có thể làm những gì chúng ta muốn với mục nhập (thay thế hoặc cập nhật giá trị).

Thanh lịch hơn:
[.__.] - lấy HashSet<Entry>
[.__.] - mở rộng nó để get(K) đặt một mục mới nếu cần
[.__.] - Entry có thể là đối tượng của riêng bạn.
[.__.] -> (new MyHashSet()).get(k).increment();

3
the felis leo

Một biến thể của cách tiếp cận MutableInt thậm chí có thể nhanh hơn, nếu một chút hack, là sử dụng một mảng int phần tử đơn:

Map<String,int[]> map = new HashMap<String,int[]>();
...
int[] value = map.get(key);
if (value == null) 
  map.put(key, new int[]{1} );
else
  ++value[0];

Sẽ rất thú vị nếu bạn có thể chạy lại các bài kiểm tra hiệu suất của mình với biến thể này. Nó có thể là nhanh nhất.


Chỉnh sửa: Mẫu trên hoạt động tốt với tôi, nhưng cuối cùng tôi đã thay đổi sử dụng các bộ sưu tập của Trove để giảm kích thước bộ nhớ trong một số bản đồ rất lớn mà tôi đang tạo - và như một phần thưởng, nó cũng nhanh hơn.

Một tính năng thực sự thú vị là lớp TObjectIntHashMap có một lệnh gọi adjustOrPutValue duy nhất, tùy thuộc vào việc đã có một giá trị tại khóa đó hay chưa, sẽ đặt một giá trị ban đầu hoặc tăng giá trị hiện có. Điều này là hoàn hảo để tăng:

TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
...
map.adjustOrPutValue(key, 1, 1);
3

Tôi nghĩ rằng giải pháp của bạn sẽ là cách tiêu chuẩn, nhưng - như bạn đã lưu ý - có lẽ đó không phải là cách nhanh nhất có thể.

Bạn có thể nhìn vào GNU Trove . Đó là một thư viện chứa tất cả các loại Bộ sưu tập nguyên thủy nhanh chóng. Ví dụ của bạn sẽ sử dụng một TObjectIntHashMap có phương thức điều chỉnhOrPutValue thực hiện chính xác những gì bạn muốn.

3
jrudolph

Bạn có chắc chắn rằng đây là một nút cổ chai? Bạn đã thực hiện bất kỳ phân tích hiệu suất?

Hãy thử sử dụng trình tạo hồ sơ NetBeans (miễn phí và được tích hợp vào NB 6.1) để xem các điểm nóng.

Cuối cùng, một bản nâng cấp JVM (giả sử từ 1.5-> 1.6) thường là một bộ tăng cường hiệu năng giá rẻ. Ngay cả một bản nâng cấp về số lượng bản dựng cũng có thể giúp tăng hiệu suất tốt. Nếu bạn đang chạy trên Windows và đây là một ứng dụng lớp máy chủ, hãy sử dụng -server trên dòng lệnh để sử dụng JVM của Hotspot máy chủ. Trên máy Linux và Solaris, điều này được tự động phát hiện.

3
John Wright

Khá đơn giản, chỉ cần sử dụng hàm dựng sẵn trong Map.Java như sau

map.put(key, map.getOrDefault(key, 0) + 1);
2
sudoz

"Đặt" cần "lấy" (để đảm bảo không có khóa trùng lặp).
[.__.] Vì vậy, trực tiếp thực hiện "đặt",
[.__.] và nếu có một giá trị trước đó, thì hãy thêm vào:

Map map = new HashMap ();

MutableInt newValue = new MutableInt (1); // default = inc
MutableInt oldValue = map.put (key, newValue);
if (oldValue != null) {
  newValue.add(oldValue); // old + inc
}

Nếu số bắt đầu bằng 0, sau đó thêm 1: (hoặc bất kỳ giá trị nào khác ...)

Map map = new HashMap ();

MutableInt newValue = new MutableInt (0); // default
MutableInt oldValue = map.put (key, newValue);
if (oldValue != null) {
  newValue.setValue(oldValue + 1); // old + inc
}

Lưu ý : Mã này không phải là luồng an toàn. Sử dụng nó để xây dựng sau đó sử dụng bản đồ, không đồng thời cập nhật nó.

Tối ưu hóa : Trong một vòng lặp, giữ giá trị cũ để trở thành giá trị mới của vòng lặp tiếp theo.

Map map = new HashMap ();
final int defaut = 0;
final int inc = 1;

MutableInt oldValue = new MutableInt (default);
while(true) {
  MutableInt newValue = oldValue;

  oldValue = map.put (key, newValue); // insert or...
  if (oldValue != null) {
    newValue.setValue(oldValue + inc); // ...update

    oldValue.setValue(default); // reuse
  } else
    oldValue = new MutableInt (default); // renew
  }
}
2
the felis leo

Nếu bạn đang sử dụng Bộ sưu tập Eclipse , bạn có thể sử dụng HashBag. Nó sẽ là cách tiếp cận hiệu quả nhất về mặt sử dụng bộ nhớ và nó cũng sẽ hoạt động tốt về tốc độ thực thi.

HashBag được hỗ trợ bởi một MutableObjectIntMap lưu trữ các int nguyên thủy thay vì các đối tượng Counter. Điều này làm giảm chi phí bộ nhớ và cải thiện tốc độ thực hiện.

HashBag cung cấp API mà bạn cần vì đó là Collection cũng cho phép bạn truy vấn số lần xuất hiện của một mục.

Đây là một ví dụ từ Bộ sưu tập Eclipse Kata .

MutableBag<String> bag =
  HashBag.newBagWith("one", "two", "two", "three", "three", "three");

Assert.assertEquals(3, bag.occurrencesOf("three"));

bag.add("one");
Assert.assertEquals(2, bag.occurrencesOf("one"));

bag.addOccurrences("one", 4);
Assert.assertEquals(6, bag.occurrencesOf("one"));

Lưu ý: Tôi là người đi làm cho Bộ sưu tập Eclipse.

1
Craig P. Motlin

Tôi sẽ sử dụng Bản đồ lười biếng của Bộ sưu tập Apache (để khởi tạo các giá trị thành 0) và sử dụng MutableIntegers từ Apache Lang làm các giá trị trong bản đồ đó.

Chi phí lớn nhất là phải cắt bản đồ hai lần trong phương pháp của bạn. Trong tôi bạn phải làm điều đó một lần. Chỉ cần lấy giá trị (nó sẽ được khởi tạo nếu vắng mặt) và tăng nó.

1
jb.

Cơ sở hạ tầng Java chức năng cơ sở dữ liệu TreeMap của thư viện có phương thức update trong phần đầu thân mới nhất:

public TreeMap<K, V> update(final K k, final F<V, V> f)

Ví dụ sử dụng:

import static fj.data.TreeMap.empty;
import static fj.function.Integers.add;
import static fj.pre.Ord.stringOrd;
import fj.data.TreeMap;

public class TreeMap_Update
  {public static void main(String[] a)
    {TreeMap<String, Integer> map = empty(stringOrd);
     map = map.set("foo", 1);
     map = map.update("foo", add.f(1));
     System.out.println(map.get("foo").some());}}

Chương trình này in "2".

1
Apocalisp

Tôi không biết hiệu quả của nó như thế nào nhưng đoạn mã dưới đây cũng hoạt động. Bạn cần xác định BiFunction ngay từ đầu. Thêm vào đó, bạn có thể thực hiện nhiều hơn là chỉ tăng với phương pháp này.

public static Map<String, Integer> strInt = new HashMap<String, Integer>();

public static void main(String[] args) {
    BiFunction<Integer, Integer, Integer> bi = (x,y) -> {
        if(x == null)
            return y;
        return x+y;
    };
    strInt.put("abc", 0);


    strInt.merge("abc", 1, bi);
    strInt.merge("abc", 1, bi);
    strInt.merge("abc", 1, bi);
    strInt.merge("abcd", 1, bi);

    System.out.println(strInt.get("abc"));
    System.out.println(strInt.get("abcd"));
}

đầu ra là

3
1
1
MGoksu

Các trình bao bọc nguyên thủy khác nhau, ví dụ: Integer là bất biến nên thực sự không có cách nào ngắn gọn hơn để làm những gì bạn yêu cầu trừ khi bạn có thể làm điều đó với một cái gì đó như AtomicLong . Tôi có thể cho nó đi trong một phút và cập nhật. BTW, Hashtable là một phần của Bộ sưu tập Khung .

1
Hank Gay

@Vilmantas Baranauskas: Về câu trả lời này, tôi sẽ bình luận nếu tôi có điểm đại diện, nhưng tôi thì không. Tôi muốn lưu ý rằng lớp Counter được định nghĩa là KHÔNG an toàn luồng vì nó không đủ để chỉ đồng bộ hóa inc () mà không đồng bộ hóa giá trị (). Các luồng khác gọi giá trị () không được đảm bảo để xem giá trị trừ khi mối quan hệ xảy ra trước khi được thiết lập với bản cập nhật.

1
Alex Miller