Abandonner le rendement pour éviter la condition dans la boucle

Question

Je dois rechercher le premier, le dernier, l'un ou l'ensemble des occurrences de quelque chose dans quelque chose d'autre. Pour éviter de me répéter (DRY) je suis venu avec la solution suivante. Il est intéressant d'utiliser les méthodes search_revisions() et collect_one_occurence() des deux classes Searcher.

Dans SearcherYield Je crée un générateur dans search_revisions() seulement pour abandonner le générateur dans collect_one_occurence() après avoir recueilli le premier résultat. Dans SearcherCondition j'ai mis une condition dans la boucle. Cette condition devra être vérifiée pour chaque itération de la boucle.

Je ne peux pas décider si mon (ab) l'utilisation du rendement et l'abandon subséquent du générateur est un coup de génie ou un hack hideux. Qu'est-ce que tu penses? Avez-vous d'autres idées pour une telle situation?

#!/usr/bin/python 

class Revision: 
    # a revision is something like a textfile. 
    # the search() method will search the textfile 
    # and return the lines which match the given pattern. 
    # for demonstration purposes this class is simplified 
    # to return predefined results 
    def __init__(self, results): 
    self.results = results 
    def search(self, pattern): 
    return self.results 

class AbstractSearcher: 
    def __init__(self, revisions): 
    self.revisions = revisions 
    def search_for_first_occurence(self, pattern): 
    keys = sorted(self.revisions.iterkeys()) 
    return self.collect_one_occurence(keys, pattern) 
    def search_for_last_occurence(self, pattern): 
    keys = sorted(self.revisions.iterkeys(), reverse = True) 
    return self.collect_one_occurence(keys, pattern) 
    def search_for_any_occurence(self, pattern): 
    keys = self.revisions.iterkeys() 
    return self.collect_one_occurence(keys, pattern) 
    def search_for_all_occurences(self, pattern): 
    keys = self.revisions.iterkeys() 
    return self.collect_all_occurences(keys, pattern) 

class SearcherYield(AbstractSearcher): 

    def search_revisions(self, keys, pattern): 
    # create generator which yields the results one by one 
    for key in keys: 
     rev = self.revisions[key] 
     result = rev.search(pattern) 
     if result: 
     yield result 

    def collect_one_occurence(self, keys, pattern): 
    # take the first result and then abandon the generator 
    for result in self.search_revisions(keys, pattern): 
     return result 
    return [] 

    def collect_all_occurences(self, keys, pattern): 
    # collect all results from generator 
    results = [] 
    for result in self.search_revisions(keys, pattern): 
     results.extend(result) 
    return results 

class SearcherCondition(AbstractSearcher): 

    def search_revisions(self, keys, pattern, just_one): 
    # collect either all results from all revisions 
    # or break the loop after first result found 
    results = [] 
    for key in keys: 
     rev = self.revisions[key] 
     result = rev.search(pattern) 
     if result: 
     results.extend(result) 
     if just_one: 
      break 
    return results 

    def collect_one_occurence(self, keys, pattern): 
    return self.search_revisions(keys, pattern, just_one = True) 

    def collect_all_occurences(self, keys, pattern): 
    return self.search_revisions(keys, pattern, just_one = False) 

def demo(searcher): 
    print searcher.__class__.__name__ 
    print 'first:', searcher.search_for_first_occurence('foo') 
    print 'last: ', searcher.search_for_last_occurence('foo') 
    print 'any: ', searcher.search_for_any_occurence('foo') 
    print 'all: ', searcher.search_for_all_occurences('foo') 

def main(): 
    revisions = { 
     1: Revision([]), 
     2: Revision(['a', 'b']), 
     3: Revision(['c']), 
     4: Revision(['d','e', 'f']), 
     5: Revision([])} 
    demo(SearcherYield(revisions)) 
    demo(SearcherCondition(revisions)) 

if __name__ == '__main__': 
    main() 

Un contexte: les révisions sont essentiellement des fichiers texte. Vous pouvez penser à eux comme les révisions d'une page wiki. Typiquement, il y a des centaines de révisions, parfois des milliers. Chaque révision contient jusqu'à des milliers de lignes de texte. Il y a aussi des cas où il y a juste quelques révisions avec quelques lignes chacune.

Une recherche dans une révision recherche un motif dans le texte et renvoie les lignes correspondantes. Parfois, il y a des milliers de résultats, parfois il n'y a pas de résultats.

Parfois, j'ai juste besoin de savoir s'il y a des résultats dans n'importe quelle révision (cherchez-en). Parfois, je dois collecter tous les résultats pour un traitement ultérieur (recherche de tous). Parfois, j'ai juste besoin de la première révision avec une correspondance, parfois juste la dernière révision (recherche du premier et du dernier).

Answer 1

J'ai fait un benchmark. Voici les résultats:

$ ./benchmark.py 
benchmark with revcount: 1000 timeitcount: 1000 
last, first, yield: 0.902059793472 
last, first, cond: 0.897155046463 
last, all, yield: 0.818709135056 
last, all, cond: 0.818334102631 
all, all, yield: 1.26602506638 
all, all, cond: 1.17208003998 
benchmark with revcount: 2000 timeitcount: 1000 
last, first, yield: 1.80768609047 
last, first, cond: 1.84234118462 
last, all, yield: 1.64661192894 
last, all, cond: 1.67588806152 
all, all, yield: 2.55621600151 
all, all, cond: 2.37582707405 
benchmark with revcount: 10000 timeitcount: 1000 
last, first, yield: 9.34304785728 
last, first, cond: 9.33725094795 
last, all, yield: 8.4673140049 
last, all, cond: 8.49153590202 
all, all, yield: 12.9636368752 
all, all, cond: 11.780673027 

Le rendement et la solution conditionnelle montrent des temps très similaires. Je pense que c'est parce que le générateur (rendement) a une boucle avec une condition dedans (si ce n'est pas vide ou quelque chose comme ça). Je pensais que j'évitais la condition dans la boucle, mais je l'ai juste déplacé hors de la vue. Quoi qu'il en soit, les chiffres montrent que les performances sont presque égales, donc le code doit être jugé par la lisibilité. Je vais rester avec la condition dans la boucle. J'aime explicite.

Voici le code de référence:

#!/usr/bin/python 

import functools 
import timeit 

class Revision: 
    # a revision is something like a textfile. 
    # the search() method will search the textfile 
    # and return the lines which match the given pattern. 
    # for demonstration purposes this class is simplified 
    # to return predefined results 
    def __init__(self, results): 
    self.results = results 
    def search(self, pattern): 
    return self.results 

class AbstractSearcher: 
    def __init__(self, revisions): 
    self.revisions = revisions 
    def search_for_first_occurence(self, pattern): 
    keys = sorted(self.revisions.iterkeys()) 
    return self.collect_one_occurence(keys, pattern) 
    def search_for_last_occurence(self, pattern): 
    keys = sorted(self.revisions.iterkeys(), reverse = True) 
    return self.collect_one_occurence(keys, pattern) 
    def search_for_any_occurence(self, pattern): 
    keys = self.revisions.iterkeys() 
    return self.collect_one_occurence(keys, pattern) 
    def search_for_all_occurences(self, pattern): 
    keys = self.revisions.iterkeys() 
    return self.collect_all_occurences(keys, pattern) 

class SearcherYield(AbstractSearcher): 

    def search_revisions(self, keys, pattern): 
    # create generator which yields the results one by one 
    for key in keys: 
     rev = self.revisions[key] 
     result = rev.search(pattern) 
     if result: 
     yield result 

    def collect_one_occurence(self, keys, pattern): 
    # take the first result and then abandon the generator 
    for result in self.search_revisions(keys, pattern): 
     return result 
    return [] 

    def collect_all_occurences(self, keys, pattern): 
    # collect all results from generator 
    results = [] 
    for result in self.search_revisions(keys, pattern): 
     results.extend(result) 
    return results 

class SearcherCondition(AbstractSearcher): 

    def search_revisions(self, keys, pattern, just_one): 
    # collect either all results from all revisions 
    # or break the loop after first result found 
    results = [] 
    for key in keys: 
     rev = self.revisions[key] 
     result = rev.search(pattern) 
     if result: 
     results.extend(result) 
     if just_one: 
      break 
    return results 

    def collect_one_occurence(self, keys, pattern): 
    return self.search_revisions(keys, pattern, just_one = True) 

    def collect_all_occurences(self, keys, pattern): 
    return self.search_revisions(keys, pattern, just_one = False) 

def benchmark(revcount, timeitcount): 

    lastrev = {} 
    for i in range(revcount): 
    lastrev[i] = Revision([]) 
    lastrev[revcount] = Revision([1]) 

    allrevs = {} 
    for i in range(revcount): 
    allrevs[i] = Revision([1]) 

    last_yield = SearcherYield(lastrev) 
    last_cond = SearcherCondition(lastrev) 
    all_yield = SearcherYield(allrevs) 
    all_cond = SearcherCondition(allrevs) 

    lfy = functools.partial(last_yield.search_for_first_occurence, 'foo') 
    lfc = functools.partial(last_cond.search_for_first_occurence, 'foo') 
    lay = functools.partial(last_yield.search_for_all_occurences, 'foo') 
    lac = functools.partial(last_cond.search_for_all_occurences, 'foo') 
    aay = functools.partial(all_yield.search_for_all_occurences, 'foo') 
    aac = functools.partial(all_cond.search_for_all_occurences, 'foo') 

    print 'benchmark with revcount: %d timeitcount: %d' % (revcount, timeitcount) 
    print 'last, first, yield:', timeit.timeit(lfy, number = timeitcount) 
    print 'last, first, cond:', timeit.timeit(lfc, number = timeitcount) 
    print 'last, all, yield:', timeit.timeit(lay, number = timeitcount) 
    print 'last, all, cond:', timeit.timeit(lac, number = timeitcount) 
    print ' all, all, yield:', timeit.timeit(aay, number = timeitcount) 
    print ' all, all, cond:', timeit.timeit(aac, number = timeitcount) 

def main(): 
    timeitcount = 1000 
    benchmark(1000, timeitcount) 
    benchmark(2000, timeitcount) 
    benchmark(10000, timeitcount) 

if __name__ == '__main__': 
    main() 

Quelques informations sur mon système:

$ lsb_release -a 
No LSB modules are available. 
Distributor ID: Ubuntu 
Description: Ubuntu 10.04.1 LTS 
Release: 10.04 
Codename: lucid 
$ uname -a 
Linux lesmana-laptop 2.6.32-26-generiC#46-Ubuntu SMP Tue Oct 26 16:46:46 UTC 2010 i686 GNU/Linux 
$ python --version 
Python 2.6.5 
$ cat /proc/cpuinfo | grep name 
model name : Intel(R) Pentium(R) M processor 1.60GHz 

Answer 2

Cela résoudra votre problème, si le lookup_item est immuable et collec est une collection ordonnée:

positions = [i for i, item in enumerate(collec) if item==lookup_item]

Il retourne pratiquement toutes les positions où lookup_item se produit dans collec.

Answer 3

Personnellement, je suis en faveur du rendement dans la mesure où la lisibilité, mais il est un appel à proximité. Je n'ai vraiment pas beaucoup de raisons pour lesquelles autre que je pense que c'est une bonne construction de code et s'applique dans de nombreuses situations.

Vous le savez probablement déjà mais le code nécessitera les révisions appariées retournées à l'appelant. La méthode permettant de modifier le code le moins possible consiste à renvoyer un lien à la révision lorsque les résultats sont renvoyés par la méthode de recherche Révision.

Vous pouvez probablement réduire votre code en utilisant le module python itertools conjointement avec le rendement. Lisibilité va sans doute de la merde, mais il est si impressionante geek élégant:

from itertools import chain,repeat,islice,ifilter 
def collect_one_occurence(self, keys, pattern): 
    return chain(ifilter(None,(rev.search(pattern) for rev in (self.revisions[key] for key in keys)),repeat([]).next() 

def collect_all_occurences(self, keys, pattern): 
    return list(chain(*[rev.search(pattern) for rev in (self.revisions[key] for key in keys)])) 

De toute évidence, vous pouvez étendre le code pour le rendre plus lisible, mais je l'ai laissé effondré à des fins d'analyse comparative .. se demander combien cela améliore vos résultats actuels ?