Cześć, mam za zadanie stworzyć tablice, a następnie podzielić ją na zakresy i poszukać w niej minimum lokalnego i maksymalnego za pomocą wątków (liczbę podaje użytkownik). Nie mogę użyć kolekcji, ani list. Na końcu z minimum lokalnego i maksimum wyznaczyć min i max dla całej tablicy. Ma ktoś jakiś pomył jak to zrobić? Próbowałem na wiele sposobów, ale każdy nadpisuje mi zmienne globalne i wychodzi od razu minimum i maksimum dla całej tablicy. Nie wiem jak zrobić to inaczej nie używając tych zmiennych globalnych.
0
1
Bo nie powinieneś korzystac z zadnych zmiennych globalnych! Z każdego zakresu zwracasz minimalna i maksymalna liczbę a później z tej grupy wybierasz min/maks. ExecutorService + Callable bym użył.
1
A co ty tam chcesz trzymać w zmiennych globalnych? o_O Użyj Callable<T> i zwracaj wynik cząstkowy z danego wątku, a nie wpisuj go gdzieś do zmiennej globalnej.
0
Shalom napisał(a):
A co ty tam chcesz trzymać w zmiennych globalnych? o_O Użyj
Callable<T>i zwracaj wynik cząstkowy z danego wątku, a nie wpisuj go gdzieś do zmiennej globalnej.
Bo zmiennych globalnych używam do przekazania ile ma być wątków i od jakich do jakich wartości szukać w funkcjach. Jak zrobię voida to nie będę mógł tego wywołać dla każdego wątku, tak, żeby wynik wyszedł mi poprawny. Zresztą nie mam pomysłu jak to zrobić, przejrzałem setki kodów i w każdym jest coś przypisywane do zmiennych globalnych, a z wątkami wcześniej nie pracowałem i ciężko mi to idzie.
1
@klonstoper:
Robisz jakąs klase MinMax która zwiera parę minimalnej i maksymalnej wartości i robisz klase
public final class FindLocalMinMax implements Callable<MinMax> {
private final E[] array//E to Twój typ tablicy
private final int leftIndex; //początek przedziału
private final int rightIndex; //koniec przedziału
// tu powinien być konstrutor
public MinMax call() {
//tu se szukasz
}
}
Później każdtego callabla przekazujesz do ExecutorServica robisz submita, z niego masz Future z którego getem będziesz mogł pobrać rezultat (tylko najpierw trzeba zsubmitować wszystkie taski żeby to miało sens)
0
1 konsument (np. MinMaxFinder/ParallelMinMaxFinder/BlockingParallelMinMaxFinder/MojSzukacz etc.) + N producentów (np. MinMaxWorker)
- Konsument wie ilu ma być producentów (N), zna currentMin, currentMax (inicjalnie - pierwszy element przeszukiwanej tablicy), zna przeszukiwaną tablicę
- Konsument wie ilu odpowiedzi ma się spodziewać (N), aktualizuje min/max na podstawie tego co dostaje od producenta
- Konsument tworzy N producentów i przydziela im zakres do przetworzenia
- Każdy producent zna konsumenta do którego ma przekazać dane i zakres, który ma przetworzyć
W siermiężny sposób na konsumencie możesz mieć metodę synchronized -> updateMinMax(computedMin,computedMax), którą wołają producenci jak skończą przetwarzać zakres...
W tej metodzie zwiększasz licznik odpowiedzi, które otrzymałeś, aktualizujesz min/max.
Konsumpcję można synchronizować inaczej, ale nie wiem co ćwiczyliście na zajęciach ;-)
0
Typowe zadania na ForkJoina, poczytaj o tym
0
@Henryk VIII Tudor: no chyba nie bardzo. ForkJoin jest do rekursji i bardzije nadaje się np. do Merge Sort, a tu nie ma rekursji :)
0
scibi92 napisał(a):
@Henryk VIII Tudor: no chyba nie bardzo. ForkJoin jest do rekursji i bardzije nadaje się np. do Merge Sort, a tu nie ma rekursji :)
ForkJoin jak najbardziej tutaj można użyć, implementując RecursiveTask, który odpowiednio będzie dzielił wejściową tablicę na mniejsze porcje (faza fork) i potem łączył rezultaty, wyznaczając min i max (faza join).
0
MergeSort jest oparty o rekursję, więc RecuirsiveTask się nada. Tutaj stosowanie RT jest overkillem i strzelaniem z armaty do muchy, po po prostu dzielicz sobie tablice na równe części i tyle...
0
Zauważyliście, ze kolega odpadł na zakrętach?
0
Zrobiłem szukanie minimum i maksimum lokalne, na razie zwykłym run, pomyślę jak rozwiążę to z szukaniem w całości tablicy. Program jednak się nie kompiluje...
błąd:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
już nie wiem co jest źle...
kod:
import static java.lang.Math.*;
public class Zadanie3 implements Runnable {
private int id;
private int id2;
private int[] tab = new int[200000000];
public Zadanie3(int id){
this.id=id;
}
public Zadanie3(){
}
public void updateID(int id2){
this.id2=id2;
}
public void wypelnijTablice()
{
for (int i=0; i<tab.length; i++)
{
tab[i]=i;
}
}
public void run() {
int ilosc=(int)floor(200000000/(id2));
int koniec=ilosc*(id+1);
int poczatek=koniec-ilosc;
if (id==0){
poczatek=0;
koniec=ilosc;}
int maxl=tab[poczatek];
int minl=tab[poczatek];
for(int i=poczatek; i<=koniec; i++){
if(maxl>tab[i]){
maxl=tab[i];
}
}
for(int i=poczatek; i<=koniec; i++)
{
if (minl < tab[i]) {
minl = tab[i];
}
}
System.out.println("Watek numer: " +id+1 +"zakres: " +poczatek +"-"+koniec +", Max: " +maxl +", Min: " +minl);
}
}
import java.util.Scanner;
public class Runner extends Zadanie3 {
public Runner(int id) {
super(id);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Podaj ilosc watkow: ");
int ilosc_watkow = scanner.nextInt();
Zadanie3[] runners= new Zadanie3[ilosc_watkow];
Thread[] watki=new Thread[ilosc_watkow];
Zadanie3 id2 = new Zadanie3();
id2.wypelnijTablice();
id2.updateID(ilosc_watkow);
for(int i=0; i<ilosc_watkow; i++) {
runners[i] = new Zadanie3(i);
}
for(int i=0; i<ilosc_watkow; i++) {
watki[i] = new Thread(runners[i]);
}
for(int i=0; i<ilosc_watkow; i++) {
watki[i].start();
}
}
}
Dodatkowo id2 się nie aktualizuje, mimo, że przekazuje tam liczbę wątków.
0
klonstoper napisał(a):
Zrobiłem szukanie minimum i maksimum lokalne, na razie zwykłym run, pomyślę jak rozwiążę to z szukaniem w całości tablicy. Program jednak się nie kompiluje...
błąd:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
- Jak się nie kompiluje, jak dostajesz błąd wykonania?
- Ile pamięci zajmuje tablica intów, którą tworzysz?
- Ile pamięci przydzielasz dla wirtualnej maszyny javy?
0
yarel napisał(a):
- Jak się nie kompiluje, jak dostajesz błąd wykonania?
- Ile pamięci zajmuje tablica intów, którą tworzysz?
- Ile pamięci przydzielasz dla wirtualnej maszyny javy?
Nie uruchamia się, mój błąd.
200 megabajtów kalkulator wyliczył
Mam domyślne ustawienia IntelliJ (parametr -Xmx2048m)
1
Jaki kalkulator wyliczył Ci 200 megabajtów?
Pomnóż to jeszcze przez liczbę wątków, bo tworzysz tę tablicę wielokrotnie -> new Zadanie3[ilosc_watkow]. Przy 2048M na hepa, to pewnie Twój program wywali się przy 3 wątkach, właśnie na braku pamięci.
0
yarel napisał(a):
Pomnóż to jeszcze przez liczbę wątków, bo tworzysz tę tablicę wielokrotnie ->
new Zadanie3[ilosc_watkow]. Przy 2048M na hepa, to pewnie Twój program wywali się przy 3 wątkach, właśnie na braku pamięci.
A jak zrobię private int[] tab = new int[n]; i n przekażę w metodzie updateID?
Problem w tym, że id2 się i tak nie aktualizuje przy takim wywołaniu jak mam. Da się jakoś zrobić tak, żebym z każdym wątkiem nie tworzył tej tablicy wielokrotnie, przy takiej konstrukcji jak mam i id2 podane raz było dla całej tablicy obiektów?
0
klonstoper napisał(a):
...
Problem w tym, że id2 się i tak nie aktualizuje przy takim wywołaniu jak mam.
A co to znaczy, że "id2 się nie aktualizuje" i jakiego zachowania oczekujesz?
Da się jakoś zrobić tak, żebym z każdym wątkiem nie tworzył tej tablicy wielokrotnie, przy takiej konstrukcji jak mam i id2 podane raz było dla całej tablicy obiektów?
Da się. Do tworzonego wątku można przekazać parametry prze konstruktor bądź przez wywołanie metody z tymi parametrami.
0
yarel napisał(a):
A co to znaczy, że "id2 się nie aktualizuje" i jakiego zachowania oczekujesz?
Oczekuję, że metodą updateid przekaże ilość wątków do id2 w klasie Zadanie3, i w run() dla każdego wątku(id) id2 będzie równe liczbie wszystkich wątków, co pozwoli zadziałać tym wątkom tak jak oczekuje. Na razie ani uzupelnianie tabeli nie działa, ani przekazanie id2, a robię to właśnie obiektem wywołanym domyślnym konstruktorem, a nie wątkiem.
1
Ja takie cos na szybko napisalem na maksa.
Jak chcesz tez minimum to jakas Pare stworzyc, czy z biblioteki wziąć.
Jest algorytm na szukanie min i maks jednocześnie o złożoności (1/2N) to możesz to też zmienić).
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
import java.util.concurrent.ThreadLocalRandom;
class MaximumSeeker extends RecursiveTask<Integer> {
private static final int THRESHOLD = 4;
private int[] arr;
private int low;
private int high;
public MaximumSeeker(int[] arr, int low, int high) {
this.arr = arr;
this.low = low;
this.high = high;
}
@Override
protected Integer compute() {
if (high - low <= THRESHOLD) {
return calcMax(arr, low, high);
}else{
int mid = low + (high - low) / 2;
var task = new MaximumSeeker(arr, low, mid);
task.fork();
return Math.max(new MaximumSeeker(arr, mid + 1, high).compute(), task.join());
}
}
private int calcMax(int[] arr, int low, int high) {
int max = 0;
for (int i = low; i <= high; i++) {
if (arr[i] >= max) {
max = arr[i];
}
}
return max;
}
public static void main(String[] args) {
var pool = new ForkJoinPool();
var arr = new int[]{5,4,2,1,10,22,41,43,9,23,11};
var max = pool.invoke(new MaximumSeeker(arr, 0, arr.length - 1));
System.out.println(max);
}
}