question du jour 2 - le retour

[gruik]

une réédition d'un problème classique, juste histoire de...

j'ai un fichier qui contient plusieurs paragraphes, chaque paragraphe étant composé de plusieurs lignes avec sur chacune un nombre

Code :

456
2
78

483
7

438
73
94
7837
34

387
43874
387
3738738
3738

le but est de trier numériquement les lignes de chaque paragraphe indépendamment des autres :

Code :

2
78
456

7
483

34
73
94
438
7837

387
387
3738
43874
3738738

c'est vite torché, à vos éditeurs !

[notfound]

Voici ma solution :

Code AWK :


>>> awk 'BEGIN{RS=""}{number=split($0,TAB," ");print " ";asort(TAB);for (i=1; i <= number; i++) print TAB[i];}' /tmp/gruik
 
2
78
456
 
7
483
 
34
73
94
438
7837
 
387
387
3738
43874
3738738

 

Voilou

[eax64]

Salut,

Code :

python -c 'print((lambda f:"\n\n".join((["\n".join(sorted(d.split("\n"), key=int)) for d in open(f).read().split("\n\n")])))("file_data"))'

bonne journée !

[fr0g]

Je ne la joue pas optim :p

Code PYTHON :


import sys
try:
    with open(sys.argv[1], "r") as f:
        for elem in f.read().split("\n\n"):
            elem = elem.split("\n")
            res = [int(x) for x in elem]
            res.sort()
            for item in res : print item
            print ""
except:
    print "error "
 

[Dobry]

Bon pour changer un peu (je doute que ce soit optimisé)

Code RUBY :


require 'set'
file = IO.readlines(ARGV[0])
arr = SortedSet.new
file.each_with_index do |line, i|
        arr << line.to_i if line.length != 1
        if line.length == 1 || i == file.length-1
                if arr.length != 0
                        arr.each do |e| puts e end
                        puts
                end
                arr = SortedSet.new
        end

end
 

[gruik]

Code :

python -c 'print((lambda f:"\n\n".join((["\n".join(sorted(d.split("\n"), key=int)) for d in open(f).read().split("\n\n")])))("file_data"))'

yep, j'avais quasiment la même :

Code PYTHON :

print '\n\n'.join(['\n'.join(sorted(i.split('\n'), key=int)) for i in open('fichier').read().split('\n\n') if i != ''])

sinon en awk, un peu plus tricky :

Code AWK :

awk '/^$/ {close("sort -n"); print; next} {print | "sort -n"}' fichier

Edit:

Code PERL :

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

[b0fh]

Code HASKELL :


import Data.List
import Data.List.Split
import Data.Ord

main = interact $ unlines . concat . intersperse [""] . (map . sortBy . comparing) (read :: String -> Int) . splitWhen null . lines
 

[octarin]

Je propose deux solutions:

Voici la solution en python:

Code PYTHON :


#remplacer ici fichier par le nom du fichier qui contient le texte
print('\n\n'.join(['\n'.join(sorted(i.split('\n'), key=lambda x: int(x))) for i in open(fichier).read().split('\n\n')]))
 

Et celle en bash:

Code BASH :


while read i; do
    BUF="$BUF $i"
    if [[ $i = '' ]]; then
        echo $BUF \
        | tr ' ' '\n' \
        | sort -n
        echo
        BUF=""
    fi
done < fichier
 

[skii]

Code :

croissant = []

fichier = open('toto.txt', 'r')

lire = fichier.readlines()
for line in lire:
    if line == "\n":
        croissant.sort()
        print  '\n'.join(['%s' % i for i in croissant]) + '\n'
        croissant = []
    else:
        croissant.append(int(line))
fichier.close()

Python pour ma pars, merci gruik et aryas pour l'aide !

[Atlas]

Ma version en java :

Code JAVA :


    public static void main(String[] args)
    {
        File input = new File("input.txt");
        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();
        }
       
    }

 

[notfound]

Bon comme persone s'est décidé à le faire, je le fais.
Et on va jouer un peu avec la mise en cache du fichier pour voir comment chaque programme se démerde. (Désolé b0fh mais j'ai pas ghc et l'install des 388 Mo me donne pas envie :p, et atlas mais ma version de java n'aime pas [javac 1.6.0_26] )

Code BASH :


>>> wc -l fat_gruik
44977 fat_gruik
#A chaque fois, j'utiliserai la manipulation suivante : Vider le cache, executer le programme, regarde si le programme a tout mis en cache. Tout mettre en cache et relancer
>>> f="/tmp/fat_gruik"
>>> ./drop-from-pagecache $f #On demande au système de le drop
>>> ./is-in-pagecache $f #On vérifie et ok, le système l'a bien drop
Pagesize is: 4096 bytes.
'/tmp/fat_gruik': 0 pages out of 45 appear to be in pagecache
>>> cat fat_gruik > /dev/null
>>> ./is-in-pagecache $f  #Le fichier est mis en cache totalement
Pagesize is: 4096 bytes.
'/tmp/fat_gruik': 45 pages out of 45 appear to be in pagecache
 

Bon c'est parti :

Code BASH :


#Notfound
>>> time awk 'BEGIN{RS=""}{number=split($0,TAB," ");print " ";asort(TAB);for (i=1; i <= number; i++) print TAB[i];}' fat_gruik > /dev/null   #sans cache
real    0m0.106s

>>> time awk 'BEGIN{RS=""}{number=split($0,TAB," ");print " ";asort(TAB);for (i=1; i <= number; i++) print TAB[i];}' fat_gruik > /dev/null #avec cache
real    0m0.057s
 

Code BASH :


#fr0g
>>> time python frog.py fat_gruik > /dev/null #sans cache
real    0m0.180s

>>> time python frog.py fat_gruik > /dev/null #avec cache
real    0m0.116s
 

Code BASH :


#ex0ns
>>> time ruby1.9.1 exons.rb fat_gruik > /dev/null #sans cache
real    0m0.307s

>>> time ruby1.9.1 exons.rb fat_gruik > /dev/null #avec cache
real    0m0.264s
 

Code BASH :


#gruik
>>> time awk '/^$/ {close("sort -n"); print; next} {print | "sort -n"}' fat_gruik > /dev/null #sans cache
real    0m27.971s

>>> time awk '/^$/ {close("sort -n"); print; next} {print | "sort -n"}' fat_gruik > /dev/null #avec cache
real    0m28.460s

# PS : la solution en perl est fucked up, elle reprend a chaque fois la paragraphe du haut et l'ajoute au reste
 

Code BASH :


#octarin
>>> time bash octarin > /dev/null #sans cache
real    0m23.968s

>>> time bash octarin > /dev/null #avec cache
real    0m22.238s
 

Code BASH :


#skii
>>> time python ski.py >/dev/null #sans cache
real    0m0.199s

>>> time python ski.py >/dev/null #avec cache
real    0m0.118s
 

J'ai eu quelques soucis avec les codes py, je mettrais à jour.
De plus, tous les programmes testés mettent en cache tout le fichier. A voir avec haskell qui visiblement ne le fait pas.

[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...

[Booster2ooo]

Aller, pour le fun,

C#

Code CSHARP :


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace NPNQDJ
{
    class Program
    {
        static void Main()
        {
            string fileName = "inputFile.txt";
            string fullPath = AppDomain.CurrentDomain.BaseDirectory + fileName;
            if (File.Exists(fullPath))
            {
                var fileContent = File.ReadAllText(fullPath, Encoding.ASCII);
                List<String> result = new List<String>();
                fileContent.Split(new string[] { System.Environment.NewLine + System.Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries).ToList().ForEach(
                    f => result.AddRange(
                            f.Split(new string[] { System.Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries).OrderBy(o => int.Parse(o)).ToList().Concat(new string[] { "\r" })
                        )
                );
                result.ForEach(f => Console.WriteLine(f));
            }
            //Console.ReadLine();
        }
    }
}
 

[eax64]

- 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: ''

Ha ouais mais faut pas mettre de \n la fin du fichier de data, sinon ça casse tout.

Suffit de rajouter un filter(None, ..)

Pour le miens:

Code PYTHON :

print((lambda f:"\n\n".join((["\n".join(sorted(filter(None, d.split("\n")), key=int)) for d in open(f).read().split("\n\n")])))("data"))

Qui avait un lambda inutile d'ailleur:

Code PYTHON :

print("\n\n".join((["\n".join(sorted(filter(None, d.split("\n")), key=int)) for d in open("data").read().split("\n\n")])))

Et pour celui de gruik:

Code PYTHON :

print '\n\n'.join(['\n'.join(sorted(filter(None, i.split('\n')), key=int)) for i in open('data').read().split('\n\n') if i != ''])

Quelques ressemblances entres les deux codes.

[gruik]

ah ben voilà, bien vu le filter(None, ...), du coup au résultat on est mieux :

Code :

5.40s, 886368Ko, python -c print("\n\n".join((["\n".join(sorted(filter(None, d.split("\n")), key=int)) for d in open("fichier").read().split("\n\n")])))

mais celui qui remporte la palme, pour peu qu'on commente le Console.ReadLine(); à la fin, c'est le code C# de Booster2000 :

Code :

1.16s, 1077472Ko, mono booster2000.exe

même meilleur que le code C, ça prend aussi plus de mémoire

Edit: c'est un tri alphabétique en fait, ça ne fait pas le job comme attendu :>
re-Edit: après modif les résultats pour le code C# sont ceux là :

Code :

10.75s, 3987872Ko, mono booster2000.exe