Optymalizacja dyskretna skrypty

getalldata.sh

#!/bin/bash
#Aby przenieść do schowka: <skrypt> | xclip
if [ "$#" -ne 2 ]; then
    echo "USAGE: <python script> <folder with results' folder>"
    exit -1
fi

SCRIPT=$1
RESULTS=$2

for result in "$RESULTS"/*
do
  #echo "$result"
RESULTNAME=${result##*/}
echo ""
echo "\\subsection{$RESULTNAME}"

./"$SCRIPT" "$result"

done

getdata.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
import os
import re

number_of_algorythms = 3

# Nazwy binarek
algorytmy = [
    "dijkstra",
    "dial",
    "radixheap",
    #   "radixheap2",
]

usa = [
    "USA",
    "CTR",
    "W",
    "E",
    "LKS",
    "CAL",
    "NE",
    "NW",
    "FLA",
    "COL",
    "BAY",
    "NY"
]

graphInfoRegex = "g (\d+) (\d+) (\d+) (\d+)"


def nonNone(arr):
    return next(item for item in arr if item is not None)


def graphInfoFromFile(file):
    string = open(file, 'r').read()
    # print(string)
    match = re.search(r'g (\d+) (\d+) (\d+) (\d+)', string)
    if match is not None:
        #    Zjebałem liczenie wierzchołków i musiałem sobie coś takiego dodać
        #    return (str(int(match.group(1)) - 1), match.group(2),
        #            match.group(3), match.group(4))
        return (match.group(1), match.group(2), match.group(3), match.group(4))


def NFromFileName(file):

    if "USA" in os.path.basename(file):
        return file.rsplit(".", 3)[1]
    else:
        t = file.rsplit(".", 4)
        N = t[1] + "." + t[2]
        return N


def latexInfs(string):
    if string == u"\u221E":
        return "$\infty$"
    else:
        return string


def printTriple(tuple_):
    print(("{:s} & {:s} & {:s} & {:s} & " +
           "{:s} & {:s} & {:s} & {:s} \\\\ \\hline").format(
        tuple_[1][0], tuple_[0][0], tuple_[0][1], tuple_[0][2],
        tuple_[0][3], tuple_[1][1][0], tuple_[1][1][1], tuple_[1][1][2]))


def timeFromFile(file):
    f = open(file, 'r')
    data = f.read()
    return data.rsplit("t", 1)[-1].strip()


def getStateFromPath(path):
    return path.rsplit(".", 3)[1]


def usasort(path):
    return usa.index(getStateFromPath(path))


def natural_key(string_):
    """See http://www.codinghorror.com/blog/archives/001018.html"""
    return [int(s) if s.isdigit() else s for s in re.split(r'(\d+)', string_)]


def main():
    if len(sys.argv) != 2:
        print("USAGE: <result folder>")
        exit(-1)
    resultsLocation = os.path.abspath(sys.argv[1])
    resultFiles = os.listdir(resultsLocation)
    resultFiles = list(map(lambda x: os.path.join(resultsLocation, x),
                           resultFiles))

#    print(os.path.basename(resultsLocation))

    if "USA" in os.path.basename(resultsLocation):
        resultFiles.sort()
        resultFiles.sort(key=usasort, reverse=True)
    else:
        resultFiles.sort(key=natural_key)

#    print(resultFiles)

#    tuples = [(l[i], l[i + 1], l[i + 2]) for i in range(0, len(l), 3)]

    # tuples = list(map(addNToTuple, tuples))

#    print(tuples)

    Ns = list(map(NFromFileName, resultFiles))
    Ns = [Ns[i] for i in range(0, len(Ns), 3)]

    graphInfo = list(map(graphInfoFromFile, resultFiles))
    l = graphInfo
    graphInfo = [nonNone([l[i], l[i + 1], l[i + 2]])
                 for i in range(0, len(l), 3)]

    # print(graphInfo)

    times = list(map(timeFromFile, resultFiles))

    times = list(map(latexInfs, times))
    l = times

    tuples = [(l[i], l[i + 1], l[i + 2]) for i in range(0, len(l), 3)]

    tuples = zip(Ns, tuples)
    tuples = zip(graphInfo, tuples)

    print("\\begin{center}")
    print("\\begin{tabular}")
    print("{| r | r | r | r | r || r | r | r |} \\hline")
    print("N & n & m & min & max & Dial & Dijkstra & Radixheap \\\\ \\hline")

    for tuple_ in tuples:
        printTriple(tuple_)

    print("\\end{tabular}")
    print("\\end{center}")

if __name__ == '__main__':
    main()

test.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
import os
import multiprocessing
import itertools
from subprocess import check_call, TimeoutExpired, CalledProcessError
import time
import threading
from functools import reduce

# USTAWIENIA START

# Nazwy binarek
algorytmy = [
    "dijkstra",
    "dial",
    "radixheap",
    #   "radixheap2",
]

inputs = [
    "Long-C",
    "Long-n",
    "Random4-C",
    "Random4-n",
    "Square-C",
    "Square-n",
    "USA-road-d",
    "USA-road-t",
]

# Będziemy powtarzać tylko te przykłady które zakończyły się błędem (mają
# "t ---" w ss.res)
onlyFailed = False

# Będziemy wykonywać tylko te dla których brakuje pliku wynikowego
onlyMissing = False

# USTAWIENIA END

FNULL = open(os.devnull, 'w')

threadLock = threading.Lock()


def createFolderForFile(file):
    threadLock.acquire()
    os.makedirs(os.path.dirname(file), exist_ok=True)
    threadLock.release()


def didItFail(resultFile):
    if os.path.isfile(resultFile):
        data = open(resultFile, "r")
        return "t ---" in data.read()


def fileMissing(file):
    return not os.path.isfile(file)


def log(text):
    currentH = time.strftime("%H:%M")
    print("[" + currentH + "] " + text)
    sys.stdout.flush()


def spawnCommand(command):
    fileName = os.path.basename(command[1])
    algorythm = os.path.basename(command[0])
    createFolderForFile(command[3])
    log("Start " + algorythm + " for " + fileName)
    cmd = [command[0], "-d", command[1],
           "-ss", command[2], "-oss", command[3]]
    try:
        # 30 minute timeout
        check_call(cmd, timeout=30 * 60, stdout=FNULL)
        log("Succeed " + algorythm + " for " + fileName)
    except (CalledProcessError) as e:
        log("Failed " + algorythm + " for " +
            fileName + " because " + str(e.returncode))
        f = open(command[3], 'w')
        f.write('t ---\n')
        f.close()
    except TimeoutExpired:
        log("Failed " + algorythm + " for " + fileName + " because timeout")
        f = open(command[3], 'w')
        f.write('t ' + u"\u221E" + '\n')
        f.close()

    sys.stdout.flush()
    return 1


def grToCommand(grFile, execLocation, resultLocation):
    pre, _ = os.path.splitext(grFile)
    grType = os.path.basename(pre).split('.', 1)[0]

    ssFile = pre + ".ss"

    for algorytm in algorytmy:
        resultFile = os.path.join(
            resultLocation, grType, os.path.basename(pre) +
            "." + algorytm + ".result")

        yield (os.path.join(execLocation, algorytm),
               grFile, ssFile, resultFile)


def ssExists(grFile):
    pre, _ = os.path.splitext(grFile)
    return os.path.exists(pre + ".ss")


def main():
    if len(sys.argv) != 4:
        print("USAGE: <execs' folder> <inputs folder> <result folder>")
        exit(-1)
    execLocation = os.path.abspath(sys.argv[1])
    inputsLocation = os.path.abspath(sys.argv[2])
    resultLocation = os.path.abspath(sys.argv[3])

    if not os.path.exists(resultLocation):
        os.makedirs(resultLocation)

    cpuCores = multiprocessing.cpu_count()

    inputFileList = list()

#    for _, subdirs, _ in os.walk(inputsLocation):
#        for subdir in subdirs:
#            subdirLocation = os.path.join(inputsLocation, subdir)
#            for _, _, inputFiles in os.walk(subdirLocation):
#                for inputFile in inputFiles:
#                    _, extension = os.path.splitext(inputFile)
#                #    print(extension)
#                    if extension == ".gr":
#                        inputFileList.append(os.path.join(
#                            inputsLocation, subdir, inputFile))

    for inputType in inputs:
        inputLocation = os.path.join(inputsLocation, inputType)
        for _, _, inputFiles in os.walk(inputLocation):
            for inputFile in inputFiles:
                _, extension = os.path.splitext(inputFile)
            #    print(extension)
                if extension == ".gr":
                    inputFileList.append(os.path.join(
                        inputLocation, inputFile))

    # inputFileList będzie teraz zawierać listę wszystkich plików .gr.
    # Dobra, teraz sprawdzamy, czy istnieje plik .ss razem z .gr.

    inputFileList = sorted(filter(ssExists, inputFileList))

    pool = multiprocessing.Pool(int(cpuCores * 3 / 4))

    testList = [grToCommand(x, execLocation, resultLocation)
                for x in inputFileList]

    # for inputFile in inputFileList:
    #    print()

    testGen = reduce(lambda x, y: itertools.chain(x, y), testList)

    if (onlyFailed):
        testGen = filter(lambda x: didItFail(x[3]), testGen)

    if (onlyMissing):
        testGen = filter(lambda x: fileMissing(x[3]), testGen)

    pool.map(spawnCommand, testGen)

    # print(testGen)

    for test in testGen:
        print(test)

#    for x in testGen:
#        print(x)

    # print(testGen)
    exit(0)

if __name__ == '__main__':
    main()

usa.patch

diff -ruN ../ch9-1.1_vanilla/ch9-1.1/scripts/genUSA-road-d.gr.pl scripts/genUSA-road-d.gr.pl
--- ../ch9-1.1_vanilla/ch9-1.1/scripts/genUSA-road-d.gr.pl	2006-02-21 22:45:33.000000000 +0100
+++ scripts/genUSA-road-d.gr.pl	2016-05-09 23:46:35.773240470 +0200
@@ -26,7 +26,7 @@
 
 # header:
 print "\n* 9th DIMACS Implementation Challenge: Shortest Paths\n";
-print   "* http://www.dis.uniroma1.it/~challenge9\n";
+print   "* http://www.dis.uniroma1.it/challenge9\n";
 print   "* Installer for the USA-road-d family\n";
 
 # creates directory (if does not exist)
@@ -35,7 +35,7 @@
 # instance download routine
 sub DOGEN {
     $EXT = $_[0]; # graph instance (e.g., CTR, BAY, etc.)
-    system "cd $DIR; echo bye | ftp $URL.$EXT.gr.gz";
+    system "cd $DIR; wget $URL.$EXT.gr.gz";
 #   system "cd $DIR; echo bye | ftp $URL.$EXT.co.gz";
     system "gunzip $DIR/*.$EXT.gr.gz";
 }
diff -ruN ../ch9-1.1_vanilla/ch9-1.1/scripts/genUSA-road-t.gr.pl scripts/genUSA-road-t.gr.pl
--- ../ch9-1.1_vanilla/ch9-1.1/scripts/genUSA-road-t.gr.pl	2006-02-21 22:45:33.000000000 +0100
+++ scripts/genUSA-road-t.gr.pl	2016-05-09 23:47:49.465241445 +0200
@@ -26,7 +26,7 @@
 
 # header:
 print "\n* 9th DIMACS Implementation Challenge: Shortest Paths\n";
-print   "* http://www.dis.uniroma1.it/~challenge9\n";
+print   "* http://www.dis.uniroma1.it/challenge9\n";
 print   "* Installer for the USA-road-t family\n";
 
 # creates directory (if does not exist)
@@ -35,7 +35,7 @@
 # instance download routine
 sub DOGEN {
     $EXT = $_[0]; # graph instance (e.g., CTR, BAY, etc.)
-    system "cd $DIR; echo bye | ftp $URL.$EXT.gr.gz";
+    system "cd $DIR; wget $URL.$EXT.gr.gz";
 #   system "cd $DIR; echo bye | ftp $URL.$EXT.co.gz";
     system "gunzip $DIR/*.$EXT.gr.gz";
 }