Znaleźć maksymalny i minimalny element tablicy - wątki

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.

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ł.

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.

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.

@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)

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 ;-)

Typowe zadania na ForkJoina, poczytaj o tym

@Henryk VIII Tudor: no chyba nie bardzo. ForkJoin jest do rekursji i bardzije nadaje się np. do Merge Sort, a tu nie ma rekursji :)

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).

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...

Zauważyliście, ze kolega odpadł na zakrętach?

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.

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?

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)

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.

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?

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.

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.