Preskočiť na hlavný obsah

Príklad paralelného výpočtu v Jave s využitím Fork/Join frameworku

JDK 7 prišlo s novou možnosťou paralelného programovania. Java bola rozšírené o balíček java.util.concurrent v ktorom sa nachádzajú nové triedy ktoré umožňujú jednoduchšie paralelné programovanie nad viac ako jedným (jednovláknovým) jadrom procesora.

Hlavné triedy frameworku Fork/Join ktorý uľahčuje paralelné programovanie sú:

  • ForkJoinTask<V> – abstraktná trieda definujúca úlohu
  • ForkJoinPool – trieda riadiaca vykonávanie úloh typu ForkJoinTask<V>
  • RecursiveAction – podtrieda triedy ForkJoinTask<V> určená pre úlohy nevracajúce hodnoty
  • RecursiveTask<V> – podtrieda triedy ForkJoinTask<V> určená pre úlohy vracajúce hodnoty

Príklad

V príklade bude zotrieďované pole celých čísel troma triediacimi algoritmami (Bubble sort, Selection sort a Insertion sort) so zložitosťou O(n2). Na lepšiu ukážku budú použité len 2 jadrá procesora čím dosiahneme, že jedna z úloh bude musieť čakať na dokončenie inej.

Trieda Main.java:

import java.util.ArrayList;
import java.util.Collection;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.ForkJoinPool;

public class Main {
	public static final int ARRAY_SIZE = 10;

	public static void main (String[] args) {
		// inicializuje pole
		int[] array = new int[ARRAY_SIZE];

		Random random = new Random();

		// naplni pole
		for (int i = 0; i < ARRAY_SIZE; i++) {
			array[i] = random.nextInt(ARRAY_SIZE * 2);
		}

		// Vytvori zoznam radiacich algoritmov
		Collection<Callable<Boolean>> collection = new ArrayList<Callable<Boolean>>();
		collection.add(new BubbleSort(array.clone()));
		collection.add(new InsertionSort(array.clone()));
		collection.add(new SelectionSort(array.clone()));

		// Vytvori pool ktory ma 2 jadra
		ForkJoinPool forkJoinPool = new ForkJoinPool(2);

		// Spusti vsetky vlakna
		forkJoinPool.invokeAll(collection);
	}
}

Trieda BubbleSort.java:

import java.util.Date;
import java.util.concurrent.Callable;

public class BubbleSort implements Callable<Boolean> {
	private int[] array;

	public BubbleSort (int[] array) {
		this.array = array;
	}

	public int[] getArray () {
		return array;
	}

	private void sort () {
		this.log("start");
		for (int i = 0; i < this.array.length; i++) {
			for (int j = 0; j < this.array.length - i - 1; j++) {
				if (this.array[j] < this.array[j+1]) {
					this.log("vymena: " + this.array[j]  + " za " + this.array[j+1]);
					int tmp  = this.array[j];
					this.array[j] = this.array[j+1];
					this.array[j+1] = tmp;
				}
			}
		}
		this.log("koniec");
	}

	private void log (String message) {
		System.out.println(new Date().toString() + " [BubbleSort] " + message);
	}

	@Override
	public Boolean call () {
		this.sort();
		return true;
	}
}

Trieda InsertionSort.java:

import java.util.Date;
import java.util.concurrent.Callable;

public class InsertionSort implements Callable<Boolean> {
	private int[] array;

	public InsertionSort (int[] array) {
		this.array = array;
	}

	public int[] getArray () {
		return array;
	}

	private void sort () {
		this.log("start");
		for (int i = 0; i < this.array.length - 1; i++) {
			int j = i + 1;
			int tmp = this.array[j];
			while (j > 0 && tmp > this.array[j-1]) {
				this.log("pusun prvku " + this.array[j]);
				this.array[j] = this.array[j-1];
				j--;
			}
			this.array[j] = tmp;
		}
		this.log("koniec");
	}

	private void log (String message) {
		System.out.println(new Date().toString() + " [InsertionSort] " + message);
	}

	@Override
	public Boolean call () {
		this.sort();
		return true;
	}
}

Trieda SelectionSort.java:

import java.util.Date;
import java.util.concurrent.Callable;

public class SelectionSort implements Callable<Boolean> {
	private int[] array;

	public SelectionSort (int[] array) {
		this.array = array;
	}

	public int[] getArray () {
		return array;
	}

	private void sort () {
		this.log("start");
		for (int i = 0; i < this.array.length - 1; i++) {
			int maxIndex = i;
			for (int j = i + 1; j < this.array.length; j++) {
				if (this.array[j] > this.array[maxIndex]) maxIndex = j;
			}
			this.log("vymena : " + this.array[i] + " za " + this.array[maxIndex]);
			int tmp = this.array[i];
			this.array[i] = this.array[maxIndex];
			this.array[maxIndex] = tmp;
		}
		this.log("koniec");
	}

	private void log (String message) {
		System.out.println(new Date().toString() + " [SelectionSort] " + message);
	}

	@Override
	public Boolean call () throws Exception {
		this.sort();
		return true;
	}
}

Výstup programu:

Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] start
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] start
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 17
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 0 za 18
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 1
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 17 za 17
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 13
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 1 za 13
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 18
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 1 za 7
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 3
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 0 za 6
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 7
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 3 za 3
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 6
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 1 za 3
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 1
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 0 za 1
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 3
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 0 za 1
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 1 za 13
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] koniec
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 1 za 18
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 1 za 3
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] start
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 1 za 7
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 17
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 1 za 6
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 1
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 1 za 3
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 13
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 13 za 18
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 0
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 3 za 7
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 18
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 3 za 6
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 0
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 1 za 3
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 17 za 18
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] koniec
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 1
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 13
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 3
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 0
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 7
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 0
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 1
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 6
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 0
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 1
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 1
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 3
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 0
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 1
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] koniec

Komentáre

Obľúbené príspevky z tohto blogu

XSLT transformacia v Jave

XSLT ( Extensible Stylesheet Language Transformations ) je jazyk určený na transformovanie XML dokumentov na iné XML dokumenty, alebo iné formáty ako napríklad HTML pre web, obyčajný text alebo do XSL Formatting Objects, ktoré môžu byť zkonvertované do iných formátov, ako napríklad PDF, PostScript, RTF či PNG. Originálny dokument nie je zmenený, namiesto toho sa vytvorí nový dokument na základe už existujúceho. Vstupné dokumenty sú zväčša typu XML, ale môže byt použité čokoľvek, z čoho procesor dokáže zostaviť XQuery a XPath Data Model. [1] V jednoduchom príklade ukazujem XSLT transformaciu pomocou programovacieho jazyka Java. Súbor: library.xml <?xml version="1.0" encoding="utf-8" ?> <library> <book> <id>1</id> <name>Java 7</name> </book> <book> <id>2</id> <name>Java 8</name> </book> </library> Súbor: library_stylesheet

Java - Súčet Listu s objektami BigDecimal

Pri používaní typu BigDecimal som narazil na zaujímavú úlohu a to sčítanie všetkých hodnôt v Liste. Majmä nasledovne definovaný list: List < BigDecimal > listOfBigDecimals = new LinkedList (); 1. spôsob je klasicke preiterovanie celého listu: BigDecimal sum = BigDecimal . ZERO ; for ( BigDecimal number : listOfBigDecimals ) { sum = sum . add ( number ); } 2. spôsobom je využitie stream.reduce() : BigDecimal sum = listOfBigDecimals . stream () . reduce ( BigDecimal . ZERO , BigDecimal :: add ); BONUS: spôsob s použitím reduce() v Kotline : val sum : BigDecimal = listOfBigDecimal . reduce { a , n -> a . add ( n ) }