Tests de performance

Si on dépasse à la fois la limite de temps et de mémoire sur un test de performances, est ce que le rapport d'échec stipule le double échec ou est ce qu'il n'affiche que le premier des dépassements car l'algorithme cesse d'être exécuté dès que l'une des contraintes n'est plus respectée ?

Questions subsidiaires : Est ce que quelqu'un a réussi le dernier test de performances du 4ème problème (prolego) en java ? Parce que j'ai deux versions de mon algorithme : La première dépasse la limite de mémoire et la seconde dépasse la limite de temps ! Les coefficients appliqués aux contraintes en fonction du langage utilisé sont ils fiables ? Car si les contraintes sont très serrées peut être que dans un autre langage je serais en dessous de 0,1% et que là je ne dépasse que de 0,1% ! Ou peut être que je dépasse largement car mon algorithme est mal pensé, je ne sais pas !

1. D'après mes récents tests, chaque dépassement est fatal.

2. D'après mon expérience, tu as tout intérêt à re-coder ton algo (en C++, par exemple) pour vérifier la justesse (ou non) des coefficients.

Si on dépasse à la fois la limite de temps et de mémoire sur un test de performances, je dirais que le rapport d'échec n'affiche que le premier des dépassement car l'algorithme cesse d'être exécuté dès qu'une contrainte de temps ou de mémoire n'est plus respectée (c'est beau, le copier-coller). De même, si tu échoues sur un test de vérification, tu n'auras aucune indication sur les tests suivants, me semble-t-il.

>> La première dépasse la limite de mémoire et la seconde dépasse la limite de temps !

Bien joué ; moi pareil, mais en C++.

>> Les coefficients appliqués aux contraintes en fonction du langage utilisé sont ils fiables ?

Pas toujours mais nous sommes quand même les quatre derniers jours avant la fin des inscriptions donc je pense que ça devrait aller.

>> Si les contraintes sont très serrées peut être que dans un autre langage je serais en dessous de 0,1% et que là je ne dépasse que de 0,1% !

Dans ce cas, je te conseille d'essayer de soumettre dans un autre langage. Mais me concernant, je dépasse largement car mon algorithme est mal pensé.

Après, on attend la venue de quelqu'un d'autre pour confirmer ce que j'ai dit…

D'accord, merci d'avoir apporté des réponses à mes questions !

Maintenant je suppose que l'on peut parler de ce que nous avons essayé pour l'exercice 4 ! Je suppose que l'on pouvait faire O(n\^2) vu que le nombre de briques pouvait monter jusqu'à 2000 mais personnellement j'ai pas trouvé mieux que O(n\^3) comme algorithme de recherche du plus long chemin. Quelqu'un m'éclaire ? J'ai pas envie d'attendre la correction !

http://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths ?

Perso j'ai trouvé le O(N²) mais apparemment il en existe même un de complexité O(N log N).

À priori on ne réduit pas un plus court chemin à un plus long chemin juste en composant par une fonction décroissante. C'est pas pour rien qu'ils traitent le cas acyclique à part.

Il est vrai que le problème est apparenté à une recherche de plus long chemin dans un graphe, mais encore faut-il construire le graphe pour exploiter les algos classiques existants, et c'est (trop?) coûteux. (dans certains cas, le graphe a près de n\^2/2 arêtes il me semble)

Sinon, le O(n\^2) est relativement facile à trouver je pense (on en a parlé sur http://www.siteduzero.com/forum/sujet/algo-prolego). Perso, en exploitant un peu les données de l'énoncé, et en faisant la supposition que la répartition des cubes est aléatoire (donc relativement uniforme), j'arrive encore à améliorer notablement les performances, mais je n'ai pas évalué la complexité.

@Ulfsark :
L'idée principale (ou de départ si tu veux) à retenir, c'est qu'il faut absolument mémoizer les résultats pour chaque cube, ce qui a pour effet de transformer l'arbre de recherche en DAG, et te fais échapper à l'explosion combinatoire. Dis toi bien que pour chaque cube, on ne calcule qu'une fois au final, ce qui donne donc bien O(n\^2).

D'accord, j'ai trouvé d'autres codes dans des langages plus proches de ceux que je connais et j'ai compris de quoi il retournait !

Un arbre est un DAG.

Bien vu :P
Et, si on a pris 3 sommets pour chaque brique (un pour chaque orientation), on a directement un DAG et on peut appliquer la méthode du lien wikipédia de Shloub.

Pour la complexité, c'était O(n log n) pour le tri topologique et O(n+m) pour l'algorithme de recherche du plus long chemin dans un DAG ? Sachant que m était de l'ordre de N\^2/4 (pour des valeurs aléatoires), on trouve bien une complexité quadratique.
@lgorythme, quid de cet autre algorithme en O(n log n) ?

@ Shloub : Oui, tu as raison, je me suis emmêlé les pinceaux. Ce que je veux dire, c'est que l'arbre de recherche n'est plus exponentiel pour la simple raison que les arêtes de l'arbre ne sont visitées qu'une fois.

Sinon, les algos du genre recherche du plus long chemin dans un DAG ne sont pas vraiment nécessaire ici (même si le concept est très similaire), vu que le poids de toutes les arêtes partant d'un noeud est identique.

edit : Au fait, je l'ai déjà dit, j'ai un autre algo nettement plus performant que le premier, mais ça m'étonnerait fort qu'il soit en n log(n)...

Yoch, sur le site du zéro tu dis :

La première [des choses à faire], c'est de considérer pour chaque cube l'empilement maximal que l'on peut faire au dessous (ou au dessus, peu importe), et de stocker cette information une fois calculée.

Mais, si je ne m'abuse, ça revient exactement au problème initial avec N-1 cubes.. Si tu commences par un appel récursif de ce type, je vois mal comment tu échappes à une complexité de O(n!).
Je ne vois pas en quoi le O(n\^2) était relativement simple à trouver ; sans doute suis je prisonnier depuis le début d'une mauvaise modélisation du problème.

Edit : Si on considère que n est le nombre de briques non orientables (c'est à dire 3* le nombre de briques donné). J'avais calculé que, en moyenne, il n'y a que n/4 briques empilables sur une brique prise au hasard. Mais même si l'appel récursif se fait sur du (n-1)/4, ça fait toujours une complexité de O(n!/4\^n) - environ O( [n/4e]\^n ).

Edit2 : Sauf si quand tu dis "empilement maximal" tu parles d'un empilement d'une seule brique. Mais je vois pas ce qu'on pourrait tirer de ça..

Edit3 : Ok, j'ai compris, ça marche grâce au tri topologique préalable. Ce n'est donc pas à faire en premier dans l'algorithme comme j'avais compris mais c'est la première idée dans l'élaboration de l'algorithme.

Dijkstra adapté, avec une file de priorité de type tas ? Je me suis douté à une époque que c'était un truc comme ça et j'avais pensé, l'espace d'un instant, remplacer les poids par leurs inverses mais malheureusement a+b > c+d n'implique pas nécessairement 1/a + 1/b

Edit : En fait il suffisait de trouver une fonction décroissante de E1 dans E2 telle que f(a+b) = f(a) + f(b), avec [[1 ; 10 000 000]] inclus dans E1 et E2 inclus dans R+. Mais comme ça, là, j'ai pas d'idée.

Edit 2 : En fait f(a+b) = f(a) + f(b) ce sont les fonctions linéaires.. donc aucune ne satisfait les conditions à priori. Il faudrait que je me penche plus sur cette histoire de tri topologique.

Le O(N log N) c'est un dynamique (comme le O(N\^2)) avec une optimisation dans le choix des arêtes via un arbre binaire.

Sinon, les algos du genre recherche du plus long chemin dans un DAG ne sont pas vraiment nécessaire ici (même si le concept est très similaire), vu que le poids de toutes les arêtes partant d'un noeud est identique.

Tu veux dire qu'il existe un algorithme de moindre complexité (bien que similaire) pour ce cas particulier où le poids des arrêtes partant d'un même nœud est constant ou simplement que l'on peut simplifier un peu le code car on connait déjà certaines informations au préalable ?

On peut voir ton algorithme plus performant ?

Edit : Ok Thomas. J'attendrai la correction pour avoir plus de détails.

Non, je parlais bien de l'algo que j'ai proposé sur le SdZ : si son concept et sa complexité sont similaires à un "longest path" classique, ce n'est tout de même pas exactement la même approche.

Pour mon autre algo, en gros je divise l'espace en sous espaces (avec un tableau 2d), et ainsi j'essaie de limiter au max l'espace de recherche pour chaque noeud. Pour que ça fonctionne bien, il faut que les cubes soient assez bien répartis dans mes sous espaces, c'est pour cela que j'ajoute une supposition de répartition aléatoire.

@ Thomas_94 : Je suis curieux de savoir comment tu optimise convenablement le choix des arrêtes (en d'autres termes de quel arbre binaire s'agit-il ?).

Bonjour,

J'ai écrit un nouvel algo en m'inspirant de structures adaptées pour la recherche d'éléments dans une plage 2D (cf. range tree sur wikipédia, perso j'utilise un kd-tree). Je trie les cubes par x et par y, et je recherche pour chaque cube le cube englobant immédiatement après en x et en y, ce qui me donne une fenêtre de recherche plus précise pour les cubes candidats.

En principe, ce type de recherche s'effectue en O(sqrt(N)), donc l'algo complet serait en O(N sqrt(N)), mais en pratique je ne gagne rien vis à vis de l'algo en O(N\^2), et je suis à la ramasse par rapport à mon autre algo.