Algorithme de bruteforce

Bonjour,
Après plusieurs test, je continue d'avoir un soucis,
le script prend beaucoup trop de ram et je ne sais pas comment la libérer.
Moi je voulais faire un tableau d'une longueur donnée et de faire varier les éléments dans se tableau, apparemment python ne le vois pas comme ca :aie:

Edit://
Le screenshoot montre l'utilisation intempestive de la ram, qui va chercher du secours auprès du swap (accès disque donc) et de l'activité réseaux qui s'arrête (car les mots de passe généré ne suive plus)

Il est évident que la RAM en prend un coup vu le nombre de possibilités.

Un peu de lecture où l'on parle de bruteforce.

Pour vider la mémoire je ne vois pas comment faire.

T'as essayé la soluce avec que des generators ? Pas forcément celle que j'avais faite, mais je reste d'avis que les generators restent la solution la plus adaptée (parce que la plus économique en ram).

J'utiliserais itertools

Code:

---

1 2 3 4 5 6 7 8

from itertools import combinations import string   def combi(n): #n est le nombre de lettres dans le mot return combinations(string.ascii_letters, n)   for element in combi(3): # ou print [element for element in combi(3)] print element

---

Bon ça vaut ce que ça vaut...

combinations n'est malheureusement pas du tout adapté à la problématique :

Citation:

---

Envoyé par Python.org

...
Equivalent to

Code:

---

1 2 3 4 5

def combinations(iterable, r): # combinations('ABCD', 2) --> AB AC AD BC BD CD # combinations(range(4), 3) --> 012 013 023 123 ...

---

...

---

il me semble que itertools.permutations est plus adapté:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class permutations(__builtin__.object) | permutations(iterable[, r]) --> permutations object | | Return successive r-length permutations of elements in the iterable. | | permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)     class combinations(__builtin__.object) | combinations(iterable[, r]) --> combinations object | | Return successive r-length combinations of elements in the iterable. | | combinations(range(4), 3) --> (0,1,2), (0,1,3), (0,2,3), (1,2,3)

---

Déjà un peu plus en effet, mais cela ne couvre pas les solutions où il y a plus d'une fois un membre (genre (0,0,1), (0,1,0))... et puis faudrait voir les sources pour savoir si c'est basée sur des manipulation de listes comme product, ce qui dans le contexte de sloshy, n'est pas profitable vu le nombre de possibilités (et donc la taille que pourraient atteindre ces listes (et donc la place occupée dans la ram))

Bonjour,
Je vous mets ma source, histoire que vous disposé de plus d'information.
Je n'utilise presque jamais le python (et j'ai jamais fait de l'OO avant ce projet) donc mon code est peut être pas le plus lisible ni le plus optimisé qui soit, je reste ouvert à toutes explications :ccool:

EDIT://
Je précise que c'est pour mon stage qui porte sur la sécurité des web application, si le code gène, je le retire :mouarf:

EDIT://
Code retiré :ccool:

Sans tableau intermédiaire, sans consommation de mémoire. Pas testé jusqu'au bout, j'ai fais ça sur le coin de la table ;)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

def combine (alphabet, nb, base = ''): for c in alphabet: if nb == 1: yield base + c else: for c1 in combine(alphabet, nb-1, base + c): yield c1   rep = 4 dic = 'abcde'   for i in combine(dic, rep): print i

---

merci c'est juste nikel,
mais tu pourrais commenter stp, j'avoue je comprend pas le script :aie:

C'est un générateur basé sur du récursif.

Par contre le code de sopsag sur la page précédente, ne consomme pas plus de mémoire, mais doit être globalement plus rapide, vu qu'il n'est pas récursif. Il est juste moins pythonique ;)

whouhou ! Des mois après, je découvre cette soluce, bravo DelphiManiac ! La classe !

Salut
Puisque j'ai un peu de temps pour 'critiquer' :P

Code:

---

1 2 3 4 5 6

def combine (alphabet, depth): for c in alphabet: if depth > 1: for x in combine(alphabet, depth-1): yield c + x else: yield c

---

Pas besoin de mémoriser 'directement' avec yield (usage de base='')
Par contre, avec base, on peut faire un truc intéressant i.e remplacer yield par un callback ou un visitor:

Code:

---

1 2 3 4 5 6 7 8 9 10 11

def combine (alphabet, depth, visit, base = '' ): for c in alphabet: if depth == 1: visit (base + c) else: combine(alphabet, depth-1, visit, base + c)   def V(s): print s   combine('abcd', 2, V)

---

Grosso modo on ne remonte que les 'feuilles'. C'est un peu plus classique côté POO, mais cà marche aussi.
- W

Citation:

---

Personnellement, j'aime bien Python car il regroupe agréablement des techniques de programmation anciennes.

---

Moi aussi, j'apprécie cet aspect des choses, on ne le signale pas assez souvent.

Citation:

---

J'ai été et suis encore un grand amateur de Lisp (je me suis même écrit un interpréteur minimaliste) mais je n'ai jamais rencontré quelque chose qui ressemble au yield du python dans ce langage...

---

On peut tout simplement utiliser la property-list de l'atome (disons 'compte') dont on définit la f-value par defun.
A l'entrée on teste l'existence de la propriété X dans la plist. Si elle n'existe pas on la crée avec valeur 0. Sinon on modifie la propriété X par incrémentation. Puis on retourne la valeur de la propriété. Ainsi on obtient une fonction de comptage, la propriété X agit comme une variable statique en C, et on peut en créer tant qu'on veut. Les variables ainsi crées 'appartiennent' à 'compte' et sont protégées.
Cela dit pour émuler une p-liste en python et donc un générateur à supposer qu'on ne dispose pas de cette douceur syntaxique, il suffit d'utiliser le paradigme objet:

Code:

---

1 2 3 4 5 6 7 8 9 10

class compteur(): def __init__(self): self.X=-1 def __call__(self): self.X+=1 return self.X if __name__ == "__main__": C=compteur() for i in xrange(0,10): print C()

---

Code:

---

1 2 3 4 5 6 7

def combine(alphabet, depth): if depth == 0: yield '' else: for x in combine(alphabet, depth-1): for c in alphabet: yield x + c

---

Modifications:

• Simplification: Aller jusque depth==0 au lieu de 1. C'est plus cohérent aussi si la fonction est apellée avec depth=0
• Optimisation: Inverser les deux boucles, pour éviter des appels répétés à combine. Cela oblige a renvoyer "x+c", qui est potentiellement un peu plus lent
  à calculer que "c+x", si on veut générer les résultats dans le même ordre, mais c'est négligeable par rapport à ce qu'on a gagné.

En une ligne:

Code:

---

combine=lambda A,D:(x+c for x in combine(A, D-1) for c in A) if D else ('',)

---

Il me semble que la beauté du yield (ou des generator expressions) c'est que cela permet de créer un itérateur de façon très légère, alors que dans un autre langage on passerait par un callback car un itérateur serait plus lourd à construire. Mais il est tard je dis peut-être des bétises :roll:

:ccool: je vois que mon code t'inspire.

Citation:

---

Il me semble que la beauté du yield (ou des generator expressions) c'est que cela permet de créer un itérateur de façon très légère, alors que dans un autre langage on passerait par un callback car un itérateur serait plus lourd à construire. Mais il est tard je dis peut-être des bétises

---

Iterator est un pattern GOF qui s'écrit assez facilement dans tous les langagues 'sans' callback: Wiki

yield s'utilise comme un iterator mais n'est pas de la même nature qu'un iterator.
- W

Citation:

---

Envoyé par wiztricks

Iterator est un pattern GOF qui s'écrit assez facilement dans tous les langagues 'sans' callback: Wiki

yield s'utilise comme un iterator mais n'est pas de la même nature qu'un iterator.
- W

---

Ce que je voulais dire c'est que yield (et les generator expressions) peuvent servir à implémenter un itérateur de façon très simple et naturelle. Et par itérateur j'entends un objet qui implémente l'iterator protocol de Python. Sans cela la lourdeur d'implémentation de l'itérateur s'opposerait à la simplicité du callback.
Sans utiliser yield ni générateurs, j'arrive à ceci pour implémenter l'itérateur:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Combine: def __init__(self, alphabet, depth): self.alphabet = alphabet self.depth = depth self.done = False self.pos = 0 if depth > 0: self.rest = Combine(alphabet, depth-1) self.current = self.rest.next()   def __iter__(self): return self   def next(self): if self.done: raise StopIteration() if self.depth == 0: self.done = True return '' if self.pos >= len(self.alphabet): self.current = self.rest.next() self.pos = 0 self.pos += 1 return self.current + self.alphabet[self.pos-1]

---

Il y a peut-être moyen de faire plus simple, mais ça restera toujours plus complexe qu'en utilisant yield ou un callback, à mon avis.

Salut

Le protocole iterator de Python uniformise le pattern iterator "normal".
Et le pattern iterator normal coute plus de lignes (mais ce n'est pas "complexe") que callback ou yield.

Pour chaque item retourné, le contexte de la fonction appelée est dépilé/détruit: il faut le sauvegarder et le restaurer "à la main".

callback et yield préservant le contexte d'exécution: toujours çà de moins à écrire... Après c'est une question de style yield est mieux intégré à la logique de programmation Python et à des ouvertures que ne permet pas 'callback'... callback est utilisable dans à peu près tout les langages.

- W