Злоупотребление выходом, чтобы избежать условия в цикле

Question

Мне нужно искать первое, последнее, любое или все вхождение чего-то в другом месте.Чтобы не повторяться ( DRY ), я предложил следующее решение:

Интерес представляют методы search_revisions() и collect_one_occurence() обоих Searcher классов.

В SearcherYield Я создаю генератор в search_revisions() только для того, чтобы отказаться от генератора в collect_one_occurence() после сбора первого результата.В SearcherCondition я поместил условие в цикл.Это условие нужно будет проверять для каждой итерации цикла.

Я не могу решить, является ли мое (ab) использование yield и последующего отказа от генератора ударом гения или отвратительным взломом.Как вы думаете?У вас есть другие идеи для такой ситуации?

#!/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()

Некоторый контекст: ревизии - это в основном текстовые файлы.Вы можете думать о них как о ревизиях вики-страницы.Обычно есть сотни ревизий, иногда тысячи.Каждая ревизия содержит до тысячи строк текста.Также есть случаи, когда есть только несколько ревизий с несколькими строками в каждой.

Поиск в ревизии будет искать образец в тексте и возвращать совпадающие строки.Иногда есть тысячи результатов, иногда нет результатов.

Иногда мне просто нужно знать, есть ли какие-либо результаты в какой-либо ревизии (поиск любой).Иногда мне приходится собирать все результаты для дальнейшей обработки (поиск по всем).Иногда мне просто нужна первая ревизия с соответствием, иногда просто последняя ревизия (поиск первой и последней).

Answer 1

Я сделал тест.Вот результаты:

$ ./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

Выход и решение для условий показывают очень похожие времена.Я думаю, это потому, что генератор (yield) содержит цикл с условием (если оно не пустое или что-то в этом роде).Я думал, что избежал условия в цикле, но я просто переместил его из поля зрения.

В любом случае, цифры показывают, что производительность в основном одинакова, поэтому код должен оцениваться по читабельности.Я буду придерживаться условия в цикле.Мне нравится явное.

Вот код теста:

#!/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()

Некоторая информация о моей системе:

$ 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

Лично я за выход в пользу читабельности, но это близкий звонок. У меня действительно нет особой причины, почему я считаю, что это отличная конструкция кода и она применяется во многих ситуациях.

Вы, вероятно, уже знаете это, но для кода понадобятся совпадающие ревизии, возвращаемые вызывающей стороне. Способ исправления с наименьшим количеством изменений - это возвращать ссылку на Revision, когда результаты возвращаются методом поиска Revision.

Вероятно, вы можете уменьшить свой код, используя модуль python itertools вместе с yield. Читаемость, возможно, идет в дерьмо, но это так потрясающе гладко:

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)]))

Очевидно, что вы можете расширить код, чтобы сделать его более читабельным, но я оставил его свернутым для целей тестирования ... интересно, насколько это улучшает ваши текущие результаты?

Answer 3

Это решит вашу проблему, если lookup_item является неизменным, а Collec - это любая упорядоченная коллекция:

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

Он практически вернет все позиции, где lookup_item встречается в коллекции.