Witam,
Mam stworzyć macierz symetryczną o wielkości NxN, która będzie zajmować mniej miejsca niż tablica dwuwymiarowa NxN, podpowiedź którą uzyskalem to: skorzystać z a[j][i] = a[i][j].
No i dalej nie wiem, czy mam stworzyć tab[n/2][n/2] i gdy zostanie wysłane zapytanie o komórkę macierzy, ktora jest poza zakresem tablicy[n/2][n/2], to odwrócić współrzędne, czyli skorzystać z a[j][i] = a[i][j]?
Tylko nie bardzo wiem jak, i czy w ogóle, da się to zaimplementować?
0
0
fiman napisał(a)
No i dalej nie wiem, czy mam stworzyć tab[n/2][n/2]
Czyli chcesz "pół" macierzy zmieścić w 1/4 pamięci? :|
Pół w cudzysłowie, bo to zawsze będzie więcej niż pół, np. dla macierzy 3x3 będą to 2/3, a dla 2x2 aż 3/4. Nie wspominając o skalarach. ;)
odwrócić współrzędne, czyli skorzystać z a[j][i] = a[i][j]
Gdybyś miał tablicę tablic, które mają od 1 do n elementów, to pewno tak by się dało.
Myślę jednak, że w takiej sytuacji lepiej trzymać elementy macierzy w jednej tablicy, a jedynie przeliczać indeksy.
0
Ten moj pomysł to jest średni i wolę po niego sięgnąć w ostateczności, głównie dlatego, że nie bardzo wiem jak to zaimplementować.
somekind napisał(a)
Myślę jednak, że w takiej sytuacji lepiej trzymać elementy macierzy w jednej tablicy, a jedynie przeliczać indeksy.
Mógłbyś trochę rozwinąć?
1
Wszystkie liczby trzymasz w jednej tablicy double[], rząd za rzędem.
Np. macierz:
1 2 3
2 4 5
3 5 6
będzie zapisana jako: 1 2 3 4 5 6
Kwestia tylko obliczenia indeksów, aby odwołanie się przez [3,3] zwracało 6, a przez [1, 2] oraz [2, 1] zwracało 2.
0
Gotowe rozwiązanie:
class SymetrycznaMacierz(val wymiar: Int) {
val macierz = new Array[Int](wymiar * (wymiar + 1) / 2)
def indeks(x: Int, y: Int): Int =
if (x < y)
indeks(y, x)
else
x * (x + 1) / 2 + y
def apply(x: Int, y: Int) = macierz(indeks(x, y))
def update(x: Int, y: Int, e: Int) = macierz(indeks(x, y)) = e
}
object Main {
def main(args: Array[String]): Unit = {
val macierz = new SymetrycznaMacierz(10)
macierz(1, 0) = 5
macierz(2, 2) = 8
macierz(4, 8) = 9
(0 to 9).map { row =>
(0 to 9).map { col =>
print(macierz(row, col) + " ")
}
println
}
}
}
0
somekind napisał(a)
Kwestia tylko obliczenia indeksów, aby odwołanie się przez [3,3] zwracało 6, a przez [1, 2] oraz [2, 1] zwracało 2.
Nijak nie mogę połączyć indeksy w tablicach z współrzędnymi (?) w macierzy :(
Spróbowałem zapisywać do tablicy nie przez przez rzędy, ale po przekątnych np.
1 4 6
4 2 5
6 5 3
dzieki temu jak wywołamy [1][1] lub [2][2] to wystarczy wypisać tab[1] lub tab[2].
Ale nie widzę rozwiazania gdy np. wywołujemy [2][3] lib [1][8] itd.
No i to wszystko co udało mi się wymyślić :(
Wibowit napisał(a)
Gotowe rozwiązanie:
class SymetrycznaMacierz(val wymiar: Int) {
val macierz = new Array[Int](wymiar * (wymiar + 1) / 2)
def indeks(x: Int, y: Int): Int =
if (x < y)
indeks(y, x)
else
x * (x + 1) / 2 + y
def apply(x: Int, y: Int) = macierz(indeks(x, y))
def update(x: Int, y: Int, e: Int) = macierz(indeks(x, y)) = e
}
object Main {
def main(args: Array[String]): Unit = {
val macierz = new SymetrycznaMacierz(10)
macierz(1, 0) = 5
macierz(2, 2) = 8
macierz(4, 8) = 9
(0 to 9).map { row =>
(0 to 9).map { col =>
print(macierz(row, col) + " ")
}
println
}
}
}
Nie piszę w javascript, niewiele z tego zrozumiałem.
1
Wersyja w Javie:
class SymetrycznaMacierz {
final int wymiar;
final int[] macierz;
public SymetrycznaMacierz(final int wymiar) {
this.wymiar = wymiar;
macierz = new int[wymiar * (wymiar + 1) / 2];
}
private int indeks(int x, int y) {
return x < y ? indeks(y, x) : x * (x + 1) / 2 + y;
}
public int get(int x, int y) {
return macierz[indeks(x, y)];
}
public void set(int x, int y, int e) {
macierz[indeks(x, y)] = e;
}
}
public class Main {
public static void main(String[] args) {
new Main().run();
}
public void run() {
SymetrycznaMacierz macierz = new SymetrycznaMacierz(10);
macierz.set(1, 0, 5);
macierz.set(2, 2, 8);
macierz.set(4, 8, 9);
for (int row = 0; row <= 9; row++) {
for (int col = 0; col <= 9; col++) {
System.out.print(macierz.get(row, col) + " ");
}
System.out.println();
}
}
}
0
fiman napisał(a)
Nijak nie mogę połączyć indeksy w tablicach z współrzędnymi (?) w macierzy
Nie rozumiesz jak zapisać dwuwymiarową tablicę liczb jako jeden ciąg liczb?
0
W moim rozwiązaniu indeksy w macierzy wyglądają tak:
1x1:
0
2x2:
0 1
1 2
3x3:
0 1 3
1 2 4
3 4 5
4x4:
0 1 3 6
1 2 4 7
3 4 5 8
6 7 8 9
itd
0
Zgodnie z wezwaniem @somekinda, trochę bardziej dydaktycznie (przynajmniej mam taka nadzieję). Tablice w Javie nie muszą być prostokątne.
tab=new int[n][];
for (int j=0;j<tab.length;j++)
{
tab[j]=new int[n-j];
}
W takie tablicy zapamiętujesz tylko liczby leżące na przekątnej i powyżej przekątnej.
0
somekind napisał(a)
Nie rozumiesz jak zapisać dwuwymiarową tablicę liczb jako jeden ciąg liczb?
To rozumiem!!!
Nie mogłem znaleźć jedynie zależności tzn.
1 2 4
2 3 5 (zapisuję do tablicy po rzędach)
4 5 6
gdy wywołam element macierzy [2][2] to ma się wyświetlić 3 element tablicy.
Wzór na rozmiar tablicy też wymyslilem, skorzystam teraz z tego kawałka kodu:
return x < y ? indeks(y, x) : x * (x + 1) / 2 + y;
i wszystko będzie grać, swoja drogą taki wzorek to ciężko wymyślić.
Zmienię tylko tak aby pierwszy element macierzy był [1][1], a nie [0][0], czyli dodam + 1 wszędzie i powinno działać.
0
bo napisał(a)
Tablice w Javie nie muszą być prostokątne.
A czy Java trzyma takie tablice tablic w pamięci w jednym kawałku?
fiman napisał(a)
swoja drogą taki wzorek to ciężko wymyślić.
Hmm... No trzeba się chwilę zastanowić, może coś pobazgrać na kartce, rozrysować sobie na spokojnie. Jeżeli to dla Ciebie było ciężkie, to strach się bać, co będzie dalej. ;]
0
Nie jestem pewien, ale chyba nawet tablica prostokątna nie musi być w jednym kawałku. Tablica dwuwymiarowa jest tablicą tablic, tzn przechowuje referencje do tablic jednowymiarowych, a one chyba nie muszą leżeć w pomięci koło siebie.
Byłbym zaskoczony gdyby tablica tab
int[][] tab=new int[2][0];
int[] t1={1,2,3};
String s="dupa";
int[] t2={11,12,13};
tab[0]=t1;
tab[1]=t2;
była w jednym kawałku.
0
bo napisał(a)
Tablica dwuwymiarowa jest tablicą tablic, tzn przechowuje referencje do tablic jednowymiarowych, a one chyba nie muszą leżeć w pomięci koło siebie.
Czyli jak w .NET, tylko że tam przynajmniej są dostępne prawdziwe tablice wielowymiarowe.
Wydaje mi się, że jest rozwiązanie z tablicami tablic jest słabe pod względem wydajności, lepiej chyba użyć jednej tablicy.
0
tablica jednowymiarowa
Random r=new Random();
int rozmiar=1000;
int[] tab1=new int[rozmiar*(rozmiar+1)/2];
//start
for(int i=0;i<proby;i++)
{
w=r.nextInt(rozmiar);
k=r.nextInt(rozmiar);
wart=r.nextInt(100);
if(k<=w)
{
tab1[(w+1)*w/2+k]=wart;
}
else
{
tab1[(k+1)*k/2+2]=wart;
}
}
//stop
tablica trójkątna
int[][] tab2=new int[rozmiar][];
for(int i=0;i<rozmiar;i++)
{
tab2[i]=new int[i+1];
}
//start
for(int i=0;i<proby;i++)
{
w=r.nextInt(rozmiar);
k=r.nextInt(rozmiar);
wart=r.nextInt(100);
set(w,k,wart);
}
//stop
void set(int w,int k,int wart)
{
if(k<=w)
{
tab2[w][k]=wart;
}
else
{
tab2[k][w]=wart;
}
}
dla małych wartości zmiennej proby trójkątna wygrywa, około 300tys. czasy się wyrównują, dalej idą łeb w łeb.
0
bogdans:
Popełniłeś kilka błędów:
- +2 zamiast +w, przez co twój kod źle działa
- Nie rozgrzewasz HotSpota, więc wyniki nie są miarodajne
2.1 Jeżeli HotSpot zdąży nawet skompilować kod, to nastąpi to równolegle do wykonywania początkowej części kodu, a więc pierwsza metoda dostanie zawyżony czas. - Większość czasu jest spędzane w obliczaniu kolejnych liczb pseudolosowych.
Przygotowałem kod (brzydki, nie wzorować się na nim), mierzący wydajność obydwu metod, nie posiadający błędów, które są w kodzie bogdansa:
import java.util.Random;
class Indeksy {
final int ilość;
final int[] x;
final int[] y;
Indeksy(final int ilość, final int wymiar) {
this.ilość = ilość;
x = new int[ilość];
y = new int[ilość];
Random random = new Random();
for (int i = 0; i < ilość; i++) {
x[i] = random.nextInt(wymiar);
y[i] = random.nextInt(wymiar);
}
}
}
interface Macierz {
int get(int x, int y);
void set(int x, int y, int e);
}
class MacierzRozwinięta implements Macierz {
final int[] macierz;
MacierzRozwinięta(final int wymiar) {
macierz = new int[wymiar * (wymiar + 1) / 2];
}
private int indeks(int x, int y) {
int min = x > y ? y : x;
int max = x > y ? x : y;
return max * (max + 1) / 2 + min;
}
@Override
public int get(int x, int y) {
return macierz[indeks(x, y)];
}
@Override
public void set(int x, int y, int e) {
macierz[indeks(x, y)] = e;
}
}
class MacierzWielowymiarowa implements Macierz {
final int[][] macierz;
MacierzWielowymiarowa(final int wymiar) {
macierz = new int[wymiar][];
for (int i = 0; i < wymiar; i++) {
macierz[i] = new int[i + 1];
}
}
public int get(int x, int y) {
int min = x > y ? y : x;
int max = x > y ? x : y;
return macierz[max][min];
}
public void set(int x, int y, int e) {
int min = x > y ? y : x;
int max = x > y ? x : y;
macierz[max][min] = e;
}
}
public class Main {
public static void main(String[] args) {
new Main().run();
}
void run() {
final int wymiar = 1000;
Macierz m1 = new MacierzRozwinięta(wymiar);
wypełnij(m1, wymiar);
Macierz m2 = new MacierzWielowymiarowa(wymiar);
wypełnij(m2, wymiar);
Indeksy indeksy = new Indeksy(123456, wymiar);
{
int suma = 0;
for (int i = 0; i < 1234; i++) {
suma += zsumuj(m1, indeksy);
suma += zsumuj(m2, indeksy);
}
System.out.println("suma: " + suma);
}
{
final long czas = System.currentTimeMillis();
int suma = 0;
for (int i = 0; i < 1234; i++) {
suma += zsumuj(m1, indeksy);
}
System.out.println("suma: " + suma);
System.out.println("czas: " + (System.currentTimeMillis() - czas));
}
{
final long czas = System.currentTimeMillis();
int suma = 0;
for (int i = 0; i < 1234; i++) {
suma += zsumuj(m2, indeksy);
}
System.out.println("suma: " + suma);
System.out.println("czas: " + (System.currentTimeMillis() - czas));
}
}
void wypełnij(Macierz macierz, int wymiar) {
Random random = new Random();
for (int i = 0; i < wymiar; i++) {
for (int j = 0; j < wymiar; j++) {
macierz.set(i, j, random.nextInt());
}
}
}
int zsumuj(Macierz macierz, Indeksy indeksy) {
int suma = 0;
for (int i = 0; i < indeksy.ilość; i++) {
suma += macierz.get(indeksy.x[i], indeksy.y[i]);
}
return suma;
}
}
Wyniki:
run:
suma: 689487776
suma: -1276746718
czas: 7365
suma: 1966234494
czas: 10593
BUILD SUCCESSFUL (total time: 36 seconds)
A więc metoda z jednowymiarową tablicą jest 1.44 razy szybsza niż metoda z tablicą wielowymiarową.
Dlaczego wersja trójkątna musi być wolniejsza? Trójkątna: referencja tablicy=>adres tablicy=>adres+4w=>referencja wiersza=>adres wiersza=>adres+4k. Jednowymiarowa: referencja tablicy=>adres tablicy=>adres+w*(w+1)/2+k. W pierwszym przypadku mamy mnożenie tylko przez 4, które jest szybkie.
Masz poważne braki jeśli chodzi o wiedzę o budowie procesora. Wiesz przynajmniej co to jest superskalarność i out-of-order execution? Zresztą czego się spodziewać, nie wiesz nawet co to JIT compiling.
0
Proszę bardzo. Kod jest brzydki, jest bowiem static.
import java.util.*;
public class Testy
{
private static int rozmiar=1000;
private static int[] tab1=new int[rozmiar*(rozmiar+1)/2];
private static int[][] tab2=new int[rozmiar][];
//------------------------
public static void main(String[] args)
{
int proby=10000;
if(args.length>0)
{
proby=Integer.parseInt(args[0]);
}
for(int i=0;i<rozmiar;i++)
{
tab2[i]=new int[i+1];
}
Random r=new Random();
int w;
int k;
int wart;
int[] wspW=new int[proby];
int[] wspK=new int[proby];
int[] values=new int[proby];
for(int i=0;i<proby;i++)
{
wspW[i]=r.nextInt(rozmiar);
wspK[i]=r.nextInt(rozmiar);;
values[i]=r.nextInt(100);
}
long start1=System.nanoTime();
for(int i=0;i<proby;i++)
{
k=wspW[i];
w=wspW[i];
wart=values[i];
if(k<=w)
{
tab1[(w+1)*w/2+k]=wart;
}
else
{
tab1[(k+1)*k/2+w]=wart;
}
}
long stop1=System.nanoTime();
long start2=System.nanoTime();
for(int i=0;i<proby;i++)
{
k=wspW[i];
w=wspW[i];
wart=values[i];
set(w,k,wart);
}
long stop2=System.nanoTime();
long start3=System.nanoTime();
for(int i=0;i<proby;i++)
{
k=wspW[i];
w=wspW[i];
wart=values[i];
if(k<=w)
{
tab1[(w+1)*w/2+k]=wart;
}
else
{
tab1[(k+1)*k/2+w]=wart;
}
}
long stop3=System.nanoTime();
System.out.println("Jeden wymiar "+(stop1-start1));
System.out.println(" Dwa wymiary "+(stop2-start2));
System.out.println("Jeden wymiar "+(stop3-start3));
}
//------------------------
private static void set(int w,int k,int wart)
{
if(k<=w)
{
tab2[w][k]=wart;
}
else
{
tab2[k][w]=wart;
}
}
}
0
Dalej twój kod jest kulawy. Usunąłem static, bo przy całym statycznym programie HotSpot może zgłupieć (przynajmniej kiedyś tak było). Zwiększyłem ilość prób do 50 mln.
import java.util.*;
public class Testy
{
private int rozmiar=1000;
private int[] tab1=new int[rozmiar*(rozmiar+1)/2];
private int[][] tab2=new int[rozmiar][];
//------------------------
public static void main(String[] args)
{
new Testy().run();
}
void run() {
int proby=50000000;
for(int i=0;i<rozmiar;i++)
{
tab2[i]=new int[i+1];
}
Random r=new Random();
int w;
int k;
int wart;
int[] wspW=new int[proby];
int[] wspK=new int[proby];
int[] values=new int[proby];
for(int i=0;i<proby;i++)
{
wspW[i]=r.nextInt(rozmiar);
wspK[i]=r.nextInt(rozmiar);;
values[i]=r.nextInt(100);
}
long start1=System.nanoTime();
for(int i=0;i<proby;i++)
{
k=wspW[i];
w=wspW[i];
wart=values[i];
if(k<=w)
{
tab1[(w+1)*w/2+k]=wart;
}
else
{
tab1[(k+1)*k/2+w]=wart;
}
}
long stop1=System.nanoTime();
long start2=System.nanoTime();
for(int i=0;i<proby;i++)
{
k=wspW[i];
w=wspW[i];
wart=values[i];
set(w,k,wart);
}
long stop2=System.nanoTime();
long start3=System.nanoTime();
for(int i=0;i<proby;i++)
{
k=wspW[i];
w=wspW[i];
wart=values[i];
if(k<=w)
{
tab1[(w+1)*w/2+k]=wart;
}
else
{
tab1[(k+1)*k/2+w]=wart;
}
}
long stop3=System.nanoTime();
System.out.println("Jeden wymiar "+(stop1-start1));
System.out.println(" Dwa wymiary "+(stop2-start2));
System.out.println("Jeden wymiar "+(stop3-start3));
}
//------------------------
private void set(int w,int k,int wart)
{
if(k<=w)
{
tab2[w][k]=wart;
}
else
{
tab2[k][w]=wart;
}
}
}
Wyniki:
run:
Jeden wymiar 563670343
Dwa wymiary 1498329345
Jeden wymiar 526231260
BUILD SUCCESSFUL (total time: 12 seconds)
- Nadal nie rozgrzewałeś HotSpota i działał tylko interpreter. W wersji serwerowej HotSpota instrukcje są kompilowane dopiero po ok 100 tysiącach wykonań (przez interpreter oczywiście).
- Jak zrobisz copy&paste to niby HotSpot ma pomyśleć, że to jedna metoda? HotSpot optymalizuje każdą pętlę oddzielnie.
- Po moich przeróbkach twój kod dalej poprawnie nie rozgrzewa HotSpota, ale efekt JIT przy 50 mln wykonań pętli jest już (a przynajmniej wydaje się) dość zaniedbywalny.
0
To mamy zagadkę.
Mój kod (dla 50mln.):
Jeden wymiar 1140558088
Dwa wymiary 492663732
Jeden wymiar 1135667801
Twój kod:
Jeden wymiar 1139588691
Dwa wymiary 496612000
Jeden wymiar 1135265236
Prawie identyczne wyniki otrzymałem na dwa sposoby:
- Java 7, programy kompilowane i wykonywane "z ręki",
- Java 6, programy kompilowane i wykonywane w Eclipse.
0
Przerobiłem jeszcze raz twój kod (kod ze zmiennymi min/ max działa szybciej od twojego rozwiązania z dużym ifem i powtarzającym się kodem, ale możesz go z powrotem zamienić, jak ci pasi), bo benchmark trwający 0.5s to żaden benchmark (496612000ns = 0.5s).
import java.util.*;
public class Main {
private int rozmiar = 1000;
private int[] tab1 = new int[rozmiar * (rozmiar + 1) / 2];
private int[][] tab2 = new int[rozmiar][];
//------------------------
public static void main(String[] args) {
new Main().run();
}
void run() {
int proby = 50000000;
for (int i = 0; i < rozmiar; i++) {
tab2[i] = new int[i + 1];
}
Random r = new Random();
int w;
int k;
int wart;
int[] wspW = new int[proby];
int[] wspK = new int[proby];
int[] values = new int[proby];
for (int i = 0; i < proby; i++) {
wspW[i] = r.nextInt(rozmiar);
wspK[i] = r.nextInt(rozmiar);
values[i] = r.nextInt(100);
}
long start2 = System.nanoTime();
for (int j = 0; j < 12; j++) {
for (int i = 0; i < proby; i++) {
k = wspW[i];
w = wspW[i];
wart = values[i];
int min = k < w ? k : w;
int max = k < w ? w : k;
tab2[max][min] = wart;
}
}
long stop2 = System.nanoTime();
long start3 = System.nanoTime();
for (int j = 0; j < 12; j++) {
for (int i = 0; i < proby; i++) {
k = wspW[i];
w = wspW[i];
wart = values[i];
int min = k < w ? k : w;
int max = k < w ? w : k;
tab1[(max + 1) * max / 2 + min] = wart;
}
}
long stop3 = System.nanoTime();
System.out.println(" Dwa wymiary " + (stop2 - start2));
System.out.println("Jeden wymiar " + (stop3 - start3));
}
}
0
Hej, mialbym prosbe. z tego kodu nie rozumiem za bardzo tej czesci:
macierz = new int[wymiar * (wymiar + 1) / 2];
a konkretnie chodzi o część
[wymiar * (wymiar + 1) / 2]
Mógłby mi ktoś to wytłumaczyć skąd taka operacja na wymiarze macierzy?
0
Jeśli masz kwadratową macierz symetryczną to wystarczy, że zapamiętasz macierz trójkątną dolną. A długości kolejnych wierszy w takiej macierzy to 1, 2, ..., n. Suma liczb od 1 do n to n * (n + 1) / 2. Podobnie, jeżeli chcesz przeskoczyć m wierszy, tzn odnieść się do m-tego wiersza to musisz przeskoczyć wiersze od długościach 1, 2, ..., m (wiersze numerujemy od zera, i-ty wiersz ma i+1 elementów) czyli suma ich długości to m * (m + 1) / 2.
0
Macierz jest symetryczna, wystarczy pamiętać jedną liczbę z pierwszego wiersza, dwie liczby z drugiego wiersza,....,wszystkie liczby z ostatniego wiersza. Jeżeli rozmiar oznacza ilość wierszy, to musimy zapamiętać 1+2+....+rozmiar liczb. Mnie uczyli w szkole (jest to zresztą oczywiste), że 1+2+...+n=n(n+1)/2.