Guida a FastUtil

1. Introduzione

In questo tutorial, esamineremo la libreria FastUtil .

Innanzitutto, codificheremo alcuni esempi delle sue raccolte specifiche per tipo.

Quindi, analizzeremo le prestazioni che danno il nome a FastUtil .

Infine, diamo uno sguardo a FastUtil s' BigArray utilità.

2. Caratteristiche

La libreria FastUtil Java cerca di estendere il Java Collections Framework. Fornisce mappe, set, elenchi e code specifici del tipo con un ingombro di memoria inferiore e accesso e inserimento rapidi. FastUtil fornisce anche una serie di utilità per lavorare e manipolare array, insiemi ed elenchi di grandi dimensioni (64 bit).

La libreria include anche una moltitudine di pratiche classi di input / output per file binari e di testo.

La sua ultima versione, FastUtil 8, ha anche rilasciato una serie di funzioni specifiche del tipo, estendendo le interfacce funzionali di JDK .

2.1. Velocità

In molti casi, le implementazioni FastUtil sono le più veloci disponibili. Gli autori hanno persino fornito un proprio rapporto di benchmark approfondito, confrontandolo con librerie simili tra cui HPPC e Trove.

In questo tutorial, cercheremo di definire i nostri benchmark utilizzando Java Microbench Harness (JMH).

3. Dipendenza di dimensioni complete

Oltre alla solita dipendenza JUnit , utilizzeremo le dipendenze FastUtils e JMH in questo tutorial.

Avremo bisogno delle seguenti dipendenze nel nostro file pom.xml :

 it.unimi.dsi fastutil 8.2.2   org.openjdk.jmh jmh-core 1.19 test   org.openjdk.jmh jmh-generator-annprocess 1.19 test 

O per gli utenti Gradle:

testCompile group: 'org.openjdk.jmh', name: 'jmh-core', version: '1.19' testCompile group: 'org.openjdk.jmh', name: 'jmh-generator-annprocess', version: '1.19' compile group: 'it.unimi.dsi', name: 'fastutil', version: '8.2.2'

3.1. File Jar personalizzato

A causa della mancanza di generici, FastUtils genera un gran numero di classi specifiche del tipo. E sfortunatamente, questo porta a un enorme file jar.

Tuttavia, fortunatamente per noi, FastUtils include uno script find-deps.sh che consente la generazione di vasi più piccoli e più mirati che comprendono solo le classi che vogliamo utilizzare nella nostra applicazione.

4. Raccolte specifiche per tipo

Prima di iniziare, diamo una rapida occhiata al semplice processo di istanziazione di una raccolta specifica del tipo. Scegliamo una HashMap che memorizzi chiavi e valori usando double.

A questo scopo, FastUtils fornisce un'interfaccia Double2DoubleMap e un'implementazione Double2DoubleOpenHashMap :

Double2DoubleMap d2dMap = new Double2DoubleOpenHashMap();

Ora che abbiamo istanziato la nostra classe, possiamo semplicemente popolare i dati come faremmo con qualsiasi mappa dall'API Java Collections:

d2dMap.put(2.0, 5.5); d2dMap.put(3.0, 6.6);

Infine, possiamo verificare che i dati siano stati aggiunti correttamente:

assertEquals(5.5, d2dMap.get(2.0));

4.1. Prestazione

FastUtils si concentra sulle sue implementazioni performanti. In questa sezione, utilizzeremo JMH per verificare questo fatto. Confrontiamo l'implementazione diJava Collections HashSet con IntOpenHashSet di FastUtil .

Per prima cosa, vediamo come implementare IntOpenHashSet:

@Param({"100", "1000", "10000", "100000"}) public int setSize; @Benchmark public IntSet givenFastUtilsIntSetWithInitialSizeSet_whenPopulated_checkTimeTaken() { IntSet intSet = new IntOpenHashSet(setSize); for(int i = 0; i < setSize; i++) { intSet.add(i); } return intSet; }

Sopra, abbiamo semplicemente dichiarato l'IntOpenHashSet attuazione del IntSet interfaccia. Abbiamo anche dichiarato la dimensione iniziale setSize con l' annotazione @Param .

In parole povere, questi numeri vengono inseriti in JMH per produrre una serie di test di benchmark con diverse dimensioni di set.

Successivamente, facciamo la stessa cosa usando l'implementazione delle raccolte Java:

@Benchmark public Set givenCollectionsHashSetWithInitialSizeSet_whenPopulated_checkTimeTaken() { Set intSet = new HashSet(setSize); for(int i = 0; i < setSize; i++) { intSet.add(i); } return intSet; }

Infine, eseguiamo il benchmark e confrontiamo le due implementazioni:

Benchmark (setSize) Mode Cnt Score Units givenCollectionsHashSetWithInitialSizeSet... 100 avgt 2 1.460 us/op givenCollectionsHashSetWithInitialSizeSet... 1000 avgt 2 12.740 us/op givenCollectionsHashSetWithInitialSizeSet... 10000 avgt 2 109.803 us/op givenCollectionsHashSetWithInitialSizeSet... 100000 avgt 2 1870.696 us/op givenFastUtilsIntSetWithInitialSizeSet... 100 avgt 2 0.369 us/op givenFastUtilsIntSetWithInitialSizeSet... 1000 avgt 2 2.351 us/op givenFastUtilsIntSetWithInitialSizeSet... 10000 avgt 2 37.789 us/op givenFastUtilsIntSetWithInitialSizeSet... 100000 avgt 2 896.467 us/op

Questi risultati rendono chiaro che l' implementazione di FastUtils è molto più performante dell'alternativa delle Java Collections.

5. Grandi collezioni

Un'altra caratteristica importante di Fa stUtils è la capacità di utilizzare array a 64 bit. Gli array in Java, per impostazione predefinita, sono limitati a 32 bit.

Per iniziare, diamo un'occhiata alla classe BigArrays per i tipi Integer . IntBigArrays fornisce metodi statici per lavorare con matrici Integer bidimensionali . Utilizzando questi metodi forniti, possiamo essenzialmente avvolgere il nostro array in un array unidimensionale più user-friendly.

Diamo un'occhiata a come funziona.

Innanzitutto, inizieremo inizializzando un array unidimensionale e convertendolo in un array bidimensionale utilizzando il metodo wrap di IntBigArray :

int[] oneDArray = new int[] { 2, 1, 5, 2, 1, 7 }; int[][] twoDArray = IntBigArrays.wrap(oneDArray.clone());

Dovremmo assicurarci di utilizzare il metodo clone per garantire una copia completa dell'array.

Ora, come faremmo con un elenco o una mappa , possiamo accedere agli elementi utilizzando il metodo get :

int firstIndex = IntBigArrays.get(twoDArray, 0); int lastIndex = IntBigArrays.get(twoDArray, IntBigArrays.length(twoDArray)-1);

Infine, aggiungiamo alcuni controlli per assicurarci che il nostro IntBigArray restituisca i valori corretti:

assertEquals(2, firstIndex); assertEquals(7, lastIndex);

6. Conclusione

In questo articolo, abbiamo preso un tuffo nel FastUtils caratteristiche principali.

Abbiamo esaminato alcune delle raccolte specifiche del tipo offerte da FastUtil , prima di giocare con alcune BigCollection .

Come sempre, il codice può essere trovato su GitHub