Macierz Rzadka

Witam,
Mam napisać program który, będzie tworzył macierz rzadka. Program ma tylko wstawiac do poszczególnych komórek macierzy wartości oraz wypisywać je. na razie popełniłem coś takiego:

private final int N;           
private ArrayList[] rzad;  


    public macierzrzadka(int N) {
        this.N  = N;
        rows = new ArrayList[N];
        for (int i = 0; i < N; i++) rows[i] = new ArrayList(N);
    }
 

nie wiem teraz jak się dobrać do poszczególnych komórek macierzy, czyli jak się odwołać np. do komóki [2,2]. Mile widziane są też jakieś inne pomysły.
Pozdrawiam,

A nie lepiej było dwuwymiarową zrobić? Ten ArrayList to taka lista-tablicowa? Napisz funkcję sobie, która zwróci referencję do pola macierzy np. rows[1].get(2) na logikę pobiera 2. element 1. wiersza.

Mam napisać dwuwymiarową tablicę i po prostu wstawić w nią macierz? To jest srasznie pamiecio żerne rozwiązanie. raczej z niego nie skożystam.

Pisać tablicy nie musisz ;p Czy ja wiem czy pamięciożerne, zwykła tablica vs tablica ArrayList'ów. Ja bym zrobił tablicę ww, prostsza w obsłudze jak to ma być tylko macierz bez jakichś dodatkowych funkcji.

w tablicach pracujesz na typach prostych, natomiast w kolekcjach na obiektach...co jest bardziej pamięciożerne? :).

Macierz rzadka

Czyste tablicy są pamięciożeerne ponieważ alokujesz tablicę NxN a większość elementów jest zerowa. Wystarczy w listach trzmać lokalizację elementów niezerowych i ich wartość. Poczytajcie mój post z linku wyżej.

Ja proponuję mapę map ;p Pierwszy indeks to np. x, drugi to y a wartość wewnętrznej mapy to wartość na [x,y].

Zajrzyj też tu:
http://4programmers.net/Forum/C_i_C++/170543-macierz_rzadka?hl=macierze%20rzadkie
http://4programmers.net/Forum/C_i_C++/131474-C++_Transponowanie_macierzy_rzadkiej?start=0

@lukas_gab
Ciekawi mnie to rozwiązanie z listami.
Czy ten kod który napisalem na początku to dobry wstęp do twojego pomysłu?
Ja próbuję zrobić tablicę której poszczególny element to bedzie nr. kolumny a element listy to nr wiersza i wartość.

@[losowa nazwa]
A jak się twój pomysł tyczy pamięciożerności?

Nie dokońca. Musisz zrobić klasę węzłów, a potem klasę macierzy która będzie przechowywała węzły w listach. Możesz to zrobić niskopoziomowo przez wskaźniki. Poczytaj przykłady z strony nvidi co podałem. Tam jest zaimplementowane mnożenie na reprezentacji listowej. Co prawda tam jest CUDA C jednak to prawie to samo co C. Jeśli chcesz oszczędzać pamięć to proponuję zainteresować się przechowywaniem macierzy w datagramie - to ten angielski artykuł co wrzuciłem. Tam jest najwyższy stopień kompresji jednak nie ma za bardzo materiałów à propos operacji na tym formacie czyli mnożenia. Musiał byś sam opracować kod pod to, z drugiej strony listowo masz mega wiele przykładów przy czym pamieciowo gorzej. Reprezentacje mapowe czy o zgrozo tablicowe są najgorsze z możliwych, jeśli chodzi o pamięć, a jak wiemy w macierzy rzadkiej nie ma co liczyć a wartości zerowych sporo więc lepiej obliczać wolniej niż szybciej i trzymać 90% zaalokowanej pamięci która nic nie wnosi do wyniku. Najbardziej optymalnie to chyba listowo. Pamiętać, należy że nvidia jest mistrzem w macierzach rzadkich ponieważ to nic innego jak obrabianie grafiki więc specjalne procki i specjalne implementacje. Jeżeli chcesz szybko to liczyć zainteresuj się zaprzegnięciem kart graficznych. Pisałem to na Tesle i Fermi i powiem, że CPU przy tym to debil liczący na palcach do 3 ;p

Dzis jestem po kolokwium i nie dam rady, ale jutro poszukam mojego kodu zaimplementowanego mnożenia i reprezentacji macierzy na listach w ANSI C.

to miłe, ale ja mam oddać kod do północy :)
Oraz w javie nie ma wskaźników, tylko referencje.

A to sorry nie uściśliłeś, że w javie. W takim razie nie pomogę, javę umię, ale nie przepadam zabardzo. W takim razie zrób klasę węzła i jakąś kolekcję co będzie przechowywać listy tych węzłów. Bezpośredni dostęp do nadrzędnej kolekcji okraśla jaka to kolumna a kolejne elementy listy ( która reprezentuje kolumne ) podaje kolejne węzły które z kolei określają wiersz i wartość.

węzeł przechowujący np

   1         |      2           |      n

{int,double}{int,double}...{int,double}
{int,double}{int,double}...{int,double}
. . .
. . .
. . .
{int,double}{int,double}...{int,double}

W takim razie 1-n to tablica o szerokości n-elementów czyli rozmiar macierzy. Tytaj lokalizujemy kolumne. Natomiast węzeł {int,double} odpowiada za pozycje w wierszu(int) i wartość (double). Mogą to być n list w tablicy. Mnożyć to już umiesz, bo można tutaj zaimplementować klasyczny algorytm a sama reprezentacja sprawia, że metoda jest dla macierzy rzadkich.

Mam nadzieje, że już sobie to przepiszesz na jave.

W linkach, które dałem był kod (w Javie!) tworzenia mapy i wypisywania macierzy.

int rows=...; //ilość wierszy
int cols=...; //ilość kolumn
HashMap<Point,Double> macierz=new HashMap<Point,Double>();
macierz.add(new Point(77,123),23.6);
...
macierz.add(new Point(57,102),12.879);
for(int w=0;w<rows;w++)
   for(int k=0;k,cols;k++)
      if(macierz.get(new Point(w,k)==null)
         //wypisz zero
      else
         //wypisz wyraz

@bo
Wiem widziałem nie jestem ślepy :P
Chciałem zrobić coś sam.
No coż popełniłem coś samemu, tylko nie działa :(

import java.util.ArrayList;
import java.util.Hashtable;

class MacierzRzadka {
   
    Hashtable []tab;
   /** Konstruktor */
   public MacierzRzadka( int N ) {
       tab = new Hashtable[N];
   }
   
   /** Metoda pozwala odczytac wartosc z pozycji i,j macierzy */
   public int get( int i, int j ) {
       Integer n = (Integer)tab[i].get(j);
       if(n != null)
       {
           return n;
       }
       else
           return 0;
   }
   
   /** Metoda pozwala wpisac wartosc na pozycje i,j macierzy */
   public void set( int i, int j, int wartosc ) {
      tab[i].put(j, new Integer(wartosc));
   }
   public static void main(String[] args) {
            int N = 3;
            int test;
            MacierzRzadka m = new MacierzRzadka(N);
            m.set(1,1,99);
            test = m.get(1, 1);
            
            System.out.println(test);
    }
   
}
 

wywala pointer exeptions przy próbie set'a w main.