question du jour 2 - le retour

[gruik]

Bon comme persone s'est décidé à le faire, je le fais.

je l'ai fait dans la nuit, pas totalement fini donc j'ai pas posté les résultats :p mais merci à toi
du coup j'apporte juste quelques précisions :

- le code d'atlas, ben oui à chaque fois il fait le même coup en fait il livre un code java pas directement compilable, je sais pas pourquoi... je rajoute son code pour ceux que ça intéressera :

Code JAVA :

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class atlas {
        public static void main(String[] args) {
                File input = new File("fichier");
                try {
                        InputStream ips = new FileInputStream(input);
                        InputStreamReader inputStreamReader = new InputStreamReader(ips);
                        BufferedReader br = new BufferedReader(inputStreamReader);

                        String line;
                        String output;
                        ArrayList<Integer> list = new ArrayList<>();

                        do {
                                line = br.readLine();
                                if(line==null || line.equals("")) {
                                        Collections.sort(list);
                                        for(int i=0;i<list.size();i++) {
                                                System.out.println(list.get(i));
                                        }
                                        System.out.println("");
                                        list.clear();
                                } else {
                                        list.add(Integer.valueOf(line));
                                }
                        } while (line!=null);
                } catch (FileNotFoundException e) {
                        e.printStackTrace();
                } catch (IOException e) {
                        e.printStackTrace();
                }
        }
}

- mon oneliner Perl n'est pas valide, il ne fait pas ce qu'il est censé faire, mais ça n'influe pas des masses sur le temps de traitement au final, le code valide est le suivant :

Code PERL :

perl -ne 'if (/^\d+$/) {push(@tab, $_)} else {print join("", sort { $a <=> $b } @tab); print; undef @tab}' fichier

- les oneliners Python (le miens et celui de eax64) vautrent lamentablement :

Code :

Traceback (most recent call last):
  File "<string>", line 1, in <module>
ValueError: invalid literal for int() with base 10: ''

- le code de Dobry (Ruby) m'a défoncé la RAM (4G) en moins de 3s, dommage

- je me suis amusé à faire une implé en C, évidement spécifique et très adaptée au fichier d'entrée pour le coup, mais bon...

Code C :

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define FICNAME "fichier"
#define BUFSIZE 16
#define TABSIZE 512

int f (const void *a, const void *b) { return (*(int*)a - *(int*)b); }

int main (int argc, char **argv) {
        FILE *fichier;
        char buff[BUFSIZE] = {0};
        int num = 0, i = 0, j = 0, tab[TABSIZE] = {0};

        if ((fichier = fopen(argv[1], "r")) == NULL) {
                fprintf (stderr, "erreur fopen.\n");
                return -1;
        }

        while (1) {
                if (((fgets(buff, BUFSIZE, fichier)) != NULL) && ((sscanf(buff, "%d\n", &num)) == 1)) { // si y'a de quoi lire et qu'y a un nombre sur la ligne
                        tab[i++] = num; // on le stocke dans le tableau
                } else { // sinon c'est qu'on est fin de paragraphe ou fin de fichier, il est temps de trier + afficher
                        qsort(tab, i, sizeof(int), f);
                        for (j = 0; j < i; j++) printf ("%d\n", tab[j]);
                        printf ("\n");
                        memset (tab, 0, TABSIZE * sizeof(int));
                        i = 0;
                        if (feof(fichier)) break; // si on est fin de fichier on reste pas plus longtemps on se casse
                }
                memset (buff, 0, BUFSIZE * sizeof(char));
        }

        fclose(fichier);
        return 0;
}

j'ai effectué les mesures sur un fichier de 57M contenant un très grand nombre de paragraphes chaque paragraphe contenant un petit nombre de lignes, donc en clair ce n'est pas tant la qualité de l'algorithme de tri qui est mesuré ici (même si ça contribuera forcément) c'est la qualité de l'algorithme de parcours du fichier, la mesure est réalisée avec une ligne du genre :

Code :

$ for i in 1 2 3; do /usr/bin/time -f "%es, %MKo, %C" -- <code ici> >/dev/null; done

on ne retient à chaque fois que la meilleure mesure, en vrac et pour ceux que ça interesse :

Code :

2.38s, 2352Ko, ./code_c_gruik fichier
7.89s, 8192Ko, perl -ne 'if (/^\d+$/) {push(@tab, $_)} else {print join("", sort { $a <=> $b } @tab); print; undef @tab}' fichier
206.97s, 14720Ko, ./code_haskell_b0fh < fichier
7.97s, 1965648Ko, ./code_python_Skii.py
9.56s, 229744Ko, java atlas
6.43s, 5024Ko, awk 'BEGIN{RS=""}{number=split($0,TAB," ");print " ";asort(TAB);for (i=1; i <= number; i++) print TAB[i];}' fichier
7.91s, 683616Ko, ./code_python_fr0g.py fichier

on remaque que Perl et Python sont dans un mouchoir de poche finalement ici, légèrement devancés par le awk de Notfound et suivis de près par l'implémentation en Java
le code C quant à lui bat évidement tous les records puisqu'il est tourné spécifiquement pour cette problématique et ce fichier de tests précis (notez néanmoins qu'on pourrait le rendre plus générique à moindre cout en jouant du realloc plutot que d'avoir un tableau d'entiers fixe, ou même quitte à allouer 8K pour le tableau c'est pas un souci)
en fait la grande surprise vient du code Haskell, y'a eu une méprise quelque part, son code aurait été échangé par mégarde dans la soute, je vois que ça...