Macierz Rzadka

0

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,

0

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.

0

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

0

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.

0

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

1

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.

0

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

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?

0

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.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0