@josmiley : Ouaip, on fait tous pareil (je pars de la fin, et toi du début).
Mais, j'ai une condition de plus dans la boucle qui me permet d'en sortir parfois plus vite. (si la quantité à trouver est plus grande que ce qui reste -> perdu ; je pars de la fin comme ça j'ai pas besoin de faire de soustraction pour savoir ça : n>=m et c'est tout)

Après, est-ce que quelqu'un sait si find(1 char) est plus rapide qu'une simple boucle ? Je sais pas du tout ; j'ai deux arguments contraires en tête.

---

C'est dommage qu'il n'y ait pas les bench à l'issue des soumission prologin, on pourrait mieux arranger nos algos.
Il doit y avoir une raison objective à ça, quelqu'un sait ?

Citation : josmiley

[...] en moins jolie quand même

Les goûts et les couleurs, aussi...

Mais au niveau des perfs ? Étant donné que tu utilises le slicing pour couper la chaîne, je suis sûr de battre ton code !

Plutôt que des hypothèses, faites des benchs ;), parfois on peut être surpris (cf un ancien topic de Candide où on mesurait le nombre d'espaces au début de chaque ligne du chaîne si mes souvenirs sont bons).

C'est amusant de se battre sur des performances alors qu'on fait du python.

Amusant, oui c'est le mot juste.

D'ailleurs, jouons !

#!/usr/bin/env python3
# -*- coding: utf8 -*-

from __future__ import absolute_import, print_function, unicode_literals

# Les scripts des participants :

# def pseudo(s, t):
#     ...


# -*- -*- BENCHMARK -*- -*- #
if __name__ == "__main__":
    from timeit import Timer

    try:
        input = raw_input
    except NameError:
        pass

    s = input("- Message de Scooby-Naire : ")
    t = input("- Chaîne à tester : ")

    for _ in range(5):
        try:
            repeat = int(input("- Nombre de répétition par script : "))
            break
        except ValueError:
            print("Veuillez entrer un nombre entier !")
    else:
        repeat = 10000

    players = [
        # Liste des participants (pseudo, imports spécifiques) :
        #     ex: ("PsycoPy", ''),
        #     ou: ("cerium50", "re"),
    ]

    tpl = ("{}(s, t)", "from __main__ import s, t, {} {}")

    podium = []
    for name, imp in players:
        print(name, ':', end=' ')
        time = Timer(tpl[0].format(name),
                     tpl[1].format(name, ', ' + imp if imp else imp))
        time = time.timeit(repeat)
        print(time, "s.")
        podium.append((time, name))

    podium.sort()
    for time, name in podium:
        print(name.ljust(25), ':', time, "s.")

EDIT : grillé pour le bench
J'ai fait un bench sur une chaîne d'un million de char, incluant une sous-chaîne de 2500 char.
Je fait 0.25s contre 2.6s à josmiley.
Mais sur de petites chaînes, je perd de peu.

C'est du Python3.

import time
def chrono(n=3):
  def mon_decorateur(f):
    def mon_wrapper(*args, **kwargs):
      t=time.time()
      for _ in range(n):
        st=time.time()
        res=f(*args, **kwargs)
        st=time.time()-st
        t=min(t, st)
      print(res, t)
    return mon_wrapper
  return mon_decorateur

@chrono()
def f_hache(n, s, m, t):
  n -= 1
  m -= 1
  while n>=m>-1:
    if s[n]==t[m]: m-=1
    n-=1
  return int(m==-1)

@chrono()
def f_var(n, s, m, t):
  i = 0
  for c in t:
      i = s[i:].find(c)+1
      if not i: return 0
  return 1


import random
def genSTR_OK(x, y):
  s=t=''
  for _ in range(x):
    a=chr(random.randint(97, 123))
    t=t+a
    s=s+a
    for plus in range(random.randint(0, y)**2):
      s=s+chr(random.randint(97, 122))
  return len(s), s, len(t), t

n, s, m, t = genSTR_OK(250000, 3)

print(n)
print(m)

f_hache(n, s, m, t)
f_var(n, s, m, t)

EDIT : n = 250000 m = 1000000, je fais 0.3s, et l'autre 5 min.

C'est normal que le code de josmiley soit très lent. À chaque tour de boucle, une nouvelle liste est créée à cause du slicing.

PS: Au fond, ton bench est plus ingénieux que le mien. (jalousie)
PSbis: Eh ? T'as testé avec mon code ? (fierté) et en plus, il est plus jolie que le sien

Citation : PsycoPy

C'est normal que le code de josmiley soit très lent. À chaque tour de boucle, une nouvelle liste est créée à cause du slicing.

PS: Au fond, ton bench est plus ingénieux que le mien. (jalousie)
PSbis: Eh ? T'as testé avec mon code ? (fierté) et en plus, il est plus jolie que le sien

Je me fais torché : toi 76ms, contre 290ms pour moi. (250000 inclus dans un million)
Bravo à vous deux, car en modifiant sa ligne en i = s.find(c, i)+1, josmiley gagne avec 75ms. (meilleur de 5 runs).

J'ai ma réponse à une question précédente : les primitives find ou index sont plus rapides qu'une boucle qui fait la même chose !!!

Ben, c'était prévisible... C'est quasiment toujours le cas, parce qu'elles sont compilées, elles. Conséquence : le code le plus ingénieux algorithmiquement n'est pas toujours le plus rapide (et l'est même assez rarement), c'est plutôt le code de celui qui a casé un maximum de fonctions standards dedans.

Bonsoir,

Puisque ce topic parle déjà des divers exercices de la demi finale 2011, j'en profite pour donner mon point de vue (après avoir essayé quelques uns) :

• Acte de grâce parait sympa (pas encore fait).
• Epiphanie (déjà traité sur un autre topic) est assez intéressant.
• Labyrinthe est relativement simple, mais amusant.
• Rectangle me parait être un bon défi... Je suis en train d'y réfléchir, mon premier algo n'a meme pas passé la moitié des tests (trop lent).

Citation : la Hache

Pour carré, c'est pas trivial, j'en ai posé déjà deux qui étaient trop lent, il a un intérêt. (en tout cas pour moi)
EDIT : j'ai tenté un troisième coup, il est assez rapide, mais je fais péter la mémoire à la fin !!! Presque bon !
EDIT : Ayé, j'ai bon, c'est vrai que c'était un peu classique en fait.

Une vraie malédiction ! Sans ajouter une once de mémoire dans ma fonction (j'utilise le tableau passé en argument pour le calcul), la mémoire a sauté au dernier test. J'ai transcrit mon algo en C, et c'est passé sans problèmes...

acte de grâce : je fais encore péter la mémoire en Python, je tente une nouvelle approche bientôt. C'est pas trivial du tout cette cochonnerie.

Rectangle me tente carrément, mais j'ai peur de faire péter la mémoire même en faisant de beaux découpage comme il faut (je verrais ça après acte de grâce).

Pousse-pousse pas encore fait. J'y crois.

Après ?

Je reste fidèle à Python, même si ça oblige à fignoler. Pour carré, j'ai un algo qui prend au final peu de mémoire : O(n), et non O(n²) comme avant.

Citation : la Hache

acte de grâce : je fais encore péter la mémoire en Python, je tente une nouvelle approche bientôt. C'est pas trivial du tout cette cochonnerie.

Oui, à première vue, ce n'est pas si trivial. Enfin bon, je crois savoir ou chercher de la doc, si je ne trouve pas tout seul...

Citation : la Hache

Rectangle me tente carrément, mais j'ai peur de faire péter la mémoire même en faisant de beaux découpage comme il faut (je verrais ça après acte de grâce).

Je pense aussi aux découpages, après avoir essayé d'y échapper avec quelques essais foirés.

Citation : la Hache

Pousse-pousse pas encore fait. J'y crois.

J'ai failli gerber en lisant l'énoncé... Très peu pour moi.

Citation : la Hache

Après ?

Laine à vendre : à faire, si tu n'as pas encore fait. Sinon, je n'ai pas encore vu les deux derniers (le meilleur pour la fin).

Citation : la Hache

Je reste fidèle à Python, même si ça oblige à fignoler. Pour carré, j'ai un algo qui prend au final peu de mémoire : O(n), et non O(n²) comme avant.

Mon algo est en O(0) au niveau mémoire, il me semble (j'utilise le tableau existant et ne crée absolument rien), et ça a sauté tout de même. Bizarre, non ?

Laine à vendre : fait, tranquillou.

Si tu gardes le carré, alors tu es en O(n²),
il ne faut pas le garder, tu lis ligne par ligne, et tu gères à la volée. Il ne faut donc pas lire l'entrée standard telle que proposée.
(En fait, je constate que c'est passé en gardant le tableau, mais j'aurais pas dû !!! Honte à moi.)
Je l'avais gardé, pour répondre 0 si c'est bouché au coins NO ou SE, c'est nul !

Citation : la Hache

Si tu gardes le carré, alors tu es en O(n²),
il ne faut pas le garder, tu lis ligne par ligne, et tu gères à la volée. Il ne faut donc pas lire l'entrée standard telle que proposée.

Ouais, mais alors c'est un peu gros que leur code lui même pète tout. Quoique ça n'a pas sauté chez toi, je me demande bien comment, puisque ça devrait sauter avant même de commencer l'algo. Peut-être qu'une liste remplie de 0 et 1 prends moins de place en Python qu'une liste remplie de gros chiffres...

Sinon, je viens de lire une peu de doc sur le principe derrière l'exo "acte de grâce", c'est absolument pas trivial pour des instances sérieuses (NP-complet). Il doit y avoir un truc grâce à la taille des instances... Au pire, je tenterais (désespérément ?) un branch-and-bound...

T'as compris : le carré rempli de 1 ou 0, ça pète pas.
Mais si tu mets du gros dedans : boum !
Conseil : laisse le carré intact et travaille un tableau en O(n) (je reste vague exprès). Je fait un petit mod10⁶ une fois sur 5, inutile à chaque étape ; trop lent. Et à la fin bien sûr.

Je retenterai en travaillant ligne lue après ligne lue, pour avoir un vrai O(n). Bon courage.

Citation : la Hache

Conseil : laisse le carré intact et travaille un tableau en O(n) (je reste vague exprès). Je fait un petit mod10⁶ une fois sur 5, inutile à chaque étape ; trop lent. Et à la fin bien sûr.

Ouais, je sais, c'est pas bien dur, enfin bon je n'ai pas aimé cette histoire. J'imagine d'ailleurs que mon code passera nickel tel quel si j'utilise array (pas de surprises de taille), enfin bon ce point est fort peu intéressant pour moi.

Sinon, l'histoire de faire le modulo une fois sur 5, c'est de la micro optimisation, inutile ici je pense. (en revanche, faire un modulo uniquement à la fin est mauvais, même si les calculs seront corrects avec Python, ils seront ralentis par la taille des nombres traités).

Citation : yoch

Sinon, je viens de lire une peu de doc sur le principe derrière l'exo "acte de grâce", c'est absolument pas trivial pour des instances sérieuses (NP-complet). Il doit y avoir un truc grâce à la taille des instances... Au pire, je tenterais (désespérément ?) un branch-and-bound...

Bon, je viens de tenter le branch and bound, je passe 6 tests sur 9 (limite de temps dépassée)...

Il y a un truc qui m'échappe, pourquoi cet exo est classé de niveau 3 ? Il y a une astuce ?

EDIT : 7 tests sur 9 à présent. Toujours une question de temps...

EDIT 2 : Youpi, je passe tous les tests !

Au fait, je ne pense pas que mon algo soit un véritable "branch and bound", vu que je n'exploite la technique que partiellement.

KMP c'est quand les caractères de la chaîne à chercher sont contigus dans la sur-chaîne.

Citation : VainEntetement

KMP c'est quand les caractères de la chaîne à chercher sont contigus dans la sur-chaîne.

Il suffit de faire une recherche pour chaque mot ?

Edit: autant pour moi, j'i mal lu l'énoncé.

Pour chaque lettre, tu veux dire ? Je ne vois pas trop l'intérêt de KMP dans ce cas.

Bon du coup ce sera peut-être le cas là.

Là oui.