Discussion :

[LinuxUser]

Bonjour, je souhaiterais avoir vos avis au sujet du choix de la structure de données pour un tableau.

En fait je souhaite définir un tableau à deux dimensions de taille fixe, dans lequel je vais simplement mettre des valeurs (enitères) et lire des valeurs.

J'hésite entre un tableau simple d'entiers "int tab[n][m]"et une array list(ou plutôt deux) , je préfère éviter d'utiliser une collection ou vector.

Bien que l'accès à une case du tableau(tab[i][j]) est sensé se faire en temps constant, j'opte pour l'insant pour les array list car je risque de manipuler des tableau 100.000 x 100.000 et je souhaite que ce ne soit pas trop lent.

Qu' en pensez vous.
Merci de votre attention.

[herve91]

Bonjour,
l'accès à t[i][j] sera toujours plus rapide que t.get(i).get(j)
Par contre 100.000 * 100.000 * 4 octets pour un int = 40 Go, tu risques fort de ne pas avoir assez de mémoire !

[LinuxUser]

On va dire un tableau de byte alors.
Si je comprend bien vous me conseillez d'utiliser un simple tableau

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

byte[][]

.
En fait j'ai besoin d'un grand tableau car je souhaite faire tourner des algorithmes d'alignements de mots(ou sequences) et in fine les tester sur des sequences d' ADN donc des centaines de milliers de lettres.

[gifffftane]

Pour les gros tableaux on peut mieux jouer avec les Buffer. Mais, faut bien jouer... heureusement il y a de la doc à peu près partout.

[hibour]

Bonsoir
Je te conseille d'utiliser un tableau d'une seule dimension car : un tableau de 2 dimension n'est qu'un tableau de tableau càd :
Soit tab un tableau d'entier: int[][] tab.
chaque tab[i] est un tableau d'entier et il peut avoir un length différent
par exemple tab[0] = new int[10], tab[1] = new int[20], ...etc
Si tu utilise des matrices M*N tu peux déclarer un tableau[M*N]
tab[i][j] = tab[i*M + j], tu gagnera N * sizeof(int) (sizeof est le nombre d'octet pris par ton type) bytes de mémoire :-)
a++

[LinuxUser]

Je ne vois pas bien l'intêret de la chose, car c'est la même chose, sauf que je dois me trimbaler des indices mois triviaux avec une seule dimension.
Au final les tableaux 2 dimensions sont de toute manière stocker en mémoire sur un tableau à une dimension.

[hibour]

Salut
Tu n'a pas à trimbaler des indices moins triviaux :-). tu écris une méthode de la sorte :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
int get(int i, int j) {
return tabl[i*M + j]
}

Idem pour le

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

void set(int i, int j, int value)

Un tableau de 2 dimension n'est pas sauvegardé en java comme un tableau d'une seule dimension.. ce n'est pas comme en C/C++.
En java pour 1 tableau d'int de N élément est allouer N*(4 = taille en octet d'un int) + ( 4 = 1 int pour le length du tableau).
Pour un tableau d'int 2d (matrice) qui est un tableau de tableau, si On a un M*N élément donc ca sera un tableau de M élément ou chaque élément sera lui même un tableau de N élément càd: M*(taille en octet d'un tableau d'int de N élément) + (1 int de length) = M*(N* 4 + 1) + 4 = (M*N*4 + 4) + M octet

a++

[LinuxUser]

Merci beaucoup de votre aide.

Un tableau de 2 dimension n'est pas sauvegardé en java comme un tableau d'une seule dimension.. ce n'est pas comme en C/C++.
a++

Au temps pour moi.

Une dernière question, est ce que vous pensez que cela sera assez efficace pour que l'on sente la différence à l'execution (avec des très grands tableaux) ?

[hibour]

Non je ne pense pas car M octet de + ou de - c'est pas ça qui fera améliorer les performances. Je ne sais pas combien d'élément tu veux mettre dans ton tableau mais sache que t'es deja limité par la mémoire, Si t'a 1Go de mémoire + de 100000 int ca va chauffer. Je te recommande si tu as + de 50% d'élément null d'utiliser une List qui contiendra que les élément non null des triplet(i, j, valeur) dans un ordre bien défini comme ca quand tu voudra accéder a l'élément (i, j) tu saura s'il n'est pas a la position pos qu'il est = 0, regarde les matrice creuse pour + ample d'infos
a++

[LinuxUser]

Non, je n'ai pas ou peux d'éléments nul.
Au début je vais tester avec des tableaux 10x10, mais in fine il faut que cela marche avec des 100 000 x 100 000 par exemple.

[hibour]

Tu ne pourra jamais avoir autant d'élément, pour 10milliard d'int il faut au moins 40Go de mémoire vive (comme cité + haut par herve91) c'est impossible sauf si tu as un super calculateur . Si ton application a vraiment besoin d'autant de données il faut revoir ta conception, pratiquement ce n'est pas faisable sur une machine ordinaire..
Voila pour t'aider un petit programme pour savoir combien tu peux alloué de mémoire maximale sur ton heap (le tas)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
int[] buf;
int size = 0;
int n = 1;
try {
	while (true) {
		buf = new int[n];
		size += n << 2 + 1; // n*4 + 1
		n = n << 1; //2*n
	}
 
} catch (Throwable e) {
	System.out.println("heap alloué = " + size + " bytes");
}

Bonne chance
A+