Table de Hachage

Version imprimable

22/04/2007, 04h00
ayed hedi

Table de Hachage

Y a t'il une méthode de stockage plus rapide que la table de hachage.
En effet j'ai implementé un algorithme (Ant-System) de résolution des problémes de grand taille et le stockage des données et l'un des deffit de ce logiciel et donc il me faut un moyen de stocker bcp de données mais la table de hachage prend bcp de taille memoire et donc c'est pas possible meme si j'augmente la memoire du JVM.:cry:
Merci
22/04/2007, 10h48
Baptiste Wicht

Citation:

Envoyé par ayed hedi

Y a t'il une méthode de stockage plus rapide que la table de hachage.
En effet j'ai implementé un algorithme (Ant-System) de résolution des problémes de grand taille et le stockage des données et l'un des deffit de ce logiciel et donc il me faut un moyen de stocker bcp de données mais la table de hachage prend bcp de taille memoire et donc c'est pas possible meme si j'augmente la memoire du JVM.:cry:
Merci

Le fait d'utiliser une autre collection ne vas pas t'aider. Toutes les collections ont leurs données en mémoire. Ce que tu peux faire, c'est réduire le nombre d'éléments a stocker. Sinon, si tu as vraiment besoin de toutes ces données, tu seras obligé d'en stocker une partie à un autre endroit que dans la mémoire, donc sur le disque...
22/04/2007, 11h05
®om

Citation:

Envoyé par ayed hedi

Y a t'il une méthode de stockage plus rapide que la table de hachage.
En effet j'ai implementé un algorithme (Ant-System) de résolution des problémes de grand taille et le stockage des données et l'un des deffit de ce logiciel et donc il me faut un moyen de stocker bcp de données mais la table de hachage prend bcp de taille memoire et donc c'est pas possible meme si j'augmente la memoire du JVM.:cry:
Merci

C'est quoi comme type de données?
22/04/2007, 11h47
trax44

juste de mannière général, si tu veux avoir plus de performance (du coté mémoire, ou rapidité), java est loins d'être le langage approprié.
22/04/2007, 12h24
®om

Citation:

Envoyé par trax44

juste de mannière général, si tu veux avoir plus de performance (du coté mémoire, ou rapidité), java est loin d'être le langage approprié.

Ça dépend...
22/04/2007, 14h08
trax44

Citation:

Envoyé par ®om

Ça dépend...

De ?
La JVM est une couche d'abstraction du l'OS, qui bouffe pas mal de ressources
22/04/2007, 14h20
sinok

Mais qui fait également un certain nombre d'optis en interne sur le code que en pourrait réaliser un compilo classique, donc tout dépend...

Par exemple le calcul d'un cos ou d'un sin est plutôt lent, par contre certaines récursivités deviennent aussi voir plus rapide que de l'itératif...

Donc ça dépend
22/04/2007, 14h36
trax44
Citation:

Envoyé par sinok

Mais qui fait également un certain nombre d'optis en interne sur le code que en pourrait réaliser un compilo classique, donc tout dépend...

Par exemple le calcul d'un cos ou d'un sin est plutôt lent, par contre certaines récursivités deviennent aussi voir plus rapide que de l'itératif...

Donc ça dépend

Je ne suis pas d'accord, parce que quand je décompile mes .class je retrouve le meme code que j'ai fais. Alors qu'avec gcc par exemple, les optimisations y sont vraiment.
Simple test fait un
Code:

1 2 3 4 5 long ii; for (long i = 0 ; i < 9000000; i++){ ii++; }
et compare avec "i<9"
les temps sont différents :p

alors que gcc aurait remplacer par :
Code:

1 2 ii = 9000000;
D'ou pas d'optimisation en java
22/04/2007, 14h36
®om

Citation:

Envoyé par trax44

De ?
La JVM est une couche d'abstraction du l'OS, qui bouffe pas mal de ressources

http://blog.developpez.com/index.php...&c=1&tb=1&pb=1
22/04/2007, 14h43
sinok

Attention, des optis de ce genre sont réalisé par le compilo JIT et non le compilateur java -> Bytecode
22/04/2007, 14h53
®om
Citation:
Envoyé par trax44

alors que gcc aurait remplacer par :

Code:

1 2 ii = 9000000;
Tu es sûr? Tu as regardé l'assembleur généré?

Sinon de toute façon comme le dit sinok les optimisation c'est par le JIT...
22/04/2007, 17h12
trax44

Citation:

Envoyé par ®om

Tu es sûr? Tu as regardé l'assembleur généré?

Sinon de toute façon comme le dit sinok les optimisation c'est par le JIT...

yop :)

C'est d'ailleurs pour ça que pour les teste de temporisation fait a l'arrache il faut faire plus qu'une simple boucle, ou lui dire de pas optimisé dutout.

Citation:

Envoyé par trax44

yop :)

C'est d'ailleurs pour ça que pour les teste de temporisation fait a l'arrache il faut faire plus qu'une simple boucle, ou lui dire de pas optimisé dutout.

Code:

1
2
3
4
5
6
7
8
int main(char**argv) {
    int i = 0;
    for(i = 0; i < 900000000; i++) {
        i++;
    }
    printf("%d\n",i);
    return 0;
}

Code:

gcc -S test.c

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
$ more test.s
        .file   "test.c"
        .text
.globl main
        .type   main, @function
main:
        leal    4(%esp), %ecx
        andl    $-16, %esp
        pushl   -4(%ecx)
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %ecx
        subl    $16, %esp
        movl    $0, -8(%ebp)
        movl    $0, -8(%ebp)
        jmp     .L2
.L3:
        addl    $1, -8(%ebp)
        addl    $1, -8(%ebp)
.L2:
        cmpl    $899999999, -8(%ebp)
        jle     .L3
        movl    $0, %eax
        addl    $16, %esp
        popl    %ecx
        popl    %ebp
        leal    -4(%ecx), %esp
        ret
        .size   main, .-main
        .ident  "GCC: (GNU) 4.1.2 (Ubuntu 4.1.2-0ubuntu4)"
        .section        .note.GNU-stack,"",@progbits

Par défaut, il exécute bien la boucle...
(bon avec ma boucle on fait 2 fois i++, mais c'était histoire de mettre qqch dans le corps du for)

Là où tu as raison, c'est si tu compiles avec gcc -Ox avec x > 0. Là il remplace bien directement l'affectation.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
$ more test.s
        .file   "test.c"
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "%d"
        .text
        .p2align 4,,15
.globl main
        .type   main, @function
main:
        leal    4(%esp), %ecx
        andl    $-16, %esp
        pushl   -4(%ecx)
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %ecx
        subl    $20, %esp
        movl    $900000000, 4(%esp)
        movl    $.LC0, (%esp)
        call    printf
        addl    $20, %esp
        xorl    %eax, %eax
        popl    %ecx
        popl    %ebp
        leal    -4(%ecx), %esp
        ret
        .size   main, .-main
        .ident  "GCC: (GNU) 4.1.2 (Ubuntu 4.1.2-0ubuntu4)"
        .section        .note.GNU-stack,"",@progbits

Mais j'ai fait ce code en java:

Code:

1
2
3
4
5
6
7
8
9
public class Test {
    public static void main(String... args) {
	int i;
    	for(i = 0; i < 900000000; i++) {
	    i++;
    	}
   	System.out.println(i);
    }
}

Et il s'exécute plus vite que le code C compilé avec gcc sans -Ox...
(il est quand même un peu plus lent que le code C compilé avec -O3, mais il faut compter en java le temps de JIT au chargement)
Donc le JIT a optimisé le code...