Передача итераторов в любой для выполнения для скорости и почему?

Question

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

1. Это вообще хорошая идея?(Это , а не ниже)
2. Интересно, добавляет ли карта улучшения скорости?Почему?
3. Почему в мире передача итераторов в любой сделает мой код быстрее?
4. Почему мой объект Counter сработал и моя функция print_true провалилась?
5. Существует ли эквивалент itertools.imap , который будет просто вызывать функцию снова и снова, и, возможно, определенное количество раз?
6. Где моя морковь?!?

---

Я только что посмотрел PyCon 2011: как Dropbox сделал это и как Python помог (по общему признанию, я пропустил большинство частей), но, наконец, действительно интересныйВсе началось примерно в 22: 23.

Докладчик выступил за создание ваших внутренних циклов в C, и эти вещи «запускаются один раз» не требуют особой оптимизации (имеет смысл) ... затем он переходит к состоянию... перефразируя:

Передайте композицию итераторов в any для значительного улучшения скорости.

Вот код (надеюсь, он идентичен):

import itertools, hashlib, time   
_md5 = hashlib.md5()  
def run():
    for i in itertools.repeat("foo", 10000000):
        _md5.update(i)
a = time.time();  run(); time.time() - a  
Out[118]: 9.44077205657959

_md5 = hashlib.md5() 
def run():
    any(itertools.imap(_md5.update, itertools.repeat("foo", 10000000)))    
a = time.time();  run(); time.time() - a
Out[121]: 6.547091007232666

Хм, похоже, для еще большего улучшения скорости я могу просто получить более быстрый компьютер!(Судя по его слайду.)

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

Я уже знал об итераторах изответ на питонический способ сделать что-то N раз без индексной переменной? благодаря Алексу Мартелли.

Тогда я подумал: интересно, действительно ли карта добавляет улучшения скорости?Моя последняя мысль была WTF ???переход на любой ?ДЕЙСТВИТЕЛЬНО???Конечно, это не может быть правдой, так как документация определяет any как:

def any(iterable):
    for element in iterable:
        if element:
            return True
    return False

Почему в мире передача итераторов любому делает мой код быстрее?

Iзатем проверил его, используя следующие (среди многих других тестов), но это то, что меня заводит:

def print_true(x):
    print 'True'
    return 'Awesome'

def test_for_loop_over_iter_map_over_iter_repeat():
    for result in itertools.imap(print_true, itertools.repeat("foo", 5)):
        pass

def run_any_over_iter_map_over_iter_repeat():
    any(itertools.imap(print_true, itertools.repeat("foo", 5)))

And the runs:

    In [67]: test_for_loop_over_iter_map_over_iter_repeat()
    True
    True
    True
    True
    True

    In [74]: run_any_over_iter_map_over_iter_repeat()
    True

Стыдно.Я объявил, что этот парень полон его. Еретик !Но я успокоился и продолжил тестирование. Если бы это было правдой, как, черт возьми, мог работать Dropbox!?!?

И при дальнейшем тестировании это сработало ... Сначала я просто использовал простой объект-счетчик, и он сосчиталвплоть до 10000000 в обоих случаях.

Итак, вопрос в том, почему мой объект Counter сработал и моя функция print_true потерпела неудачу?

class Counter(object):
    count = 0
    def count_one(self, none):
        self.count += 1

def run_any_counter():
    counter = Counter()
    any(itertools.imap(counter.count_one, itertools.repeat("foo", 10000000)))
    print counter.count

def run_for_counter():
    counter = Counter()
    for result in itertools.imap(counter.count_one, itertools.repeat("foo", 10000000)):
        pass
    print counter.count

output:

%time run_for_counter()
10000000
CPU times: user 5.54 s, sys: 0.03 s, total: 5.57 s
Wall time: 5.68 s

%time run_any_counter()
10000000
CPU times: user 5.28 s, sys: 0.02 s, total: 5.30 s
Wall time: 5.40 s

Еще больший WTF даже после удаления ненужного аргумента и написания наиболее разумного кода для моего объекта Counter, он все еще медленнее, чем версия any-map.Где моя морковь?!?:

class CounterNoArg(object):
    count = 0
    def count_one(self):
        self.count += 1

def straight_count():
    counter = CounterNoArg()
    for _ in itertools.repeat(None, 10000000):
        counter.count_one()
    print counter.count

Ouput:

In [111]: %time straight_count()
10000000
CPU times: user 5.44 s, sys: 0.02 s, total: 5.46 s
Wall time: 5.60 s

Я спрашиваю, потому что я думаю, что Pythonistas или Pythoneers нужна морковь, поэтому мы не начинаем передавать вещи любой или все для повышения производительности, или он уже существует?Возможно, эквивалентно itertools.imap , который будет просто вызывать функцию снова и снова, и, возможно, определенное количество раз.

Лучшее, что мне удалось - это (использование списка даетинтересные результаты):

def super_run():
    counter = CounterNoArg()
    for _ in (call() for call in itertools.repeat(counter.count_one, 10000000)):
        pass
    print counter.count

def super_counter_run():
    counter = CounterNoArg()
    [call() for call in itertools.repeat(counter.count_one, 10000000)]
    print counter.count

def run_any_counter():
    counter = Counter()
    any(itertools.imap(counter.count_one, itertools.repeat("foo", 10000000)))
    print counter.count

%time super_run()
10000000
CPU times: user 5.23 s, sys: 0.03 s, total: 5.26 s
Wall time: 5.43 s

%time super_counter_run()
10000000
CPU times: user 4.75 s, sys: 0.18 s, total: 4.94 s
Wall time: 5.80 s

%time run_any_counter()
10000000
CPU times: user 5.15 s, sys: 0.06 s, total: 5.21 s
Wall time: 5.30 s

def run_any_like_presentation():
    any(itertools.imap(_md5.update, itertools.repeat("foo", 10000000)))

def super_run_like_presentation():
    [do_work for do_work in itertools.imap(_md5.update, itertools.repeat("foo", 10000000))]

def super_run_like_presentation_2():
    [_md5.update(foo) for foo in itertools.repeat("foo", 10000000)]


%time run_any_like_presentation()
CPU times: user 5.28 s, sys: 0.02 s, total: 5.29 s
Wall time: 5.47 s

%time super_run_like_presentation()
CPU times: user 6.14 s, sys: 0.18 s, total: 6.33 s
Wall time: 7.56 s

%time super_run_like_presentation_2()
CPU times: user 8.44 s, sys: 0.22 s, total: 8.66 s
Wall time: 9.59 s

Тьфу ...

Примечание. Я рекомендую вам самим проводить тесты.

Answer 1

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

import itertools, hashlib, timeit
_md5 = hashlib.md5()

def run1():
    for i in itertools.repeat("foo", 10000000):
        _md5.update(i)

def run2():
    u = _md5.update
    for i in itertools.repeat("foo", 10000000):
        u(i)

def run3():
    any(itertools.imap(_md5.update, itertools.repeat("foo", 10000000)))

>>> timeit.timeit('run1()', 'from __main__ import run1', number=1)
6.081272840499878
>>> timeit.timeit('run2()', 'from __main__ import run2', number=1)
4.660238981246948
>>> timeit.timeit('run3()', 'from __main__ import run3', number=1)
4.062871932983398

Документация itertools имеет лучший рецепт для использования итератора (и отбрасывания всех его значений): см. Функцию consume. Использование any для выполнения этой работы зависит от того факта, что _md5.update всегда возвращает None, поэтому этот подход в целом не работает. Кроме того, рецепт немного быстрее: [см. Комментарии]

import collections

def consume(it):
    "Consume iterator completely (discarding its values)."
    collections.deque(it, maxlen=0)

def run4():
    consume(itertools.imap(_md5.update, itertools.repeat("foo", 10000000)))

>>> timeit.timeit('run4()', 'from __main__ import run4', number=1)
3.969902992248535

Отредактировано, чтобы добавить: кажется, что рецепт consume не так хорошо известен, как следовало бы: если вы посмотрите на детали реализации CPython, вы увидите, что когда collections.deque вызывается с maxlen=0 затем вызывается функция consume_iterator в _collectionsmodule.c, которая выглядит следующим образом:

static PyObject*
consume_iterator(PyObject *it)
{
    PyObject *item;
    while ((item = PyIter_Next(it)) != NULL) {
        Py_DECREF(item);
    }
    Py_DECREF(it);
    if (PyErr_Occurred())
        return NULL;
    Py_RETURN_NONE;
}

Answer 2

Чтобы ответить на первый вопрос об оптимизации, перейдя к любому. Нет, я считаю, что это не очень хорошая идея, потому что это не ее цель. Конечно, это легко реализовать, но обслуживание может стать кошмаром. Таким образом, в вашу кодовую базу вводится новая ошибка. Если функция когда-либо возвращает false, то итератор не будет полностью использован, вызывая странное поведение и ошибки, которые трудно отследить. Кроме того, существуют более быстрые (или, по крайней мере, почти такие же быстрые) альтернативы использованию встроенного любого.

Конечно, вы можете сделать исключение, потому что кажется, что любой действительно может выполнить deque, но использование любого из них, безусловно, является крайним и чаще всего ненужным. Фактически, если что-то и происходит, вы можете вводить оптимизации, которые могут перестать быть «оптимальными» после обновления базы кода Python (см. 2.7 против 3.2).

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

Что касается оптимизации собственного кода, давайте начнем с того, с чем мы столкнулись: обратитесь к run_any_like_presentation. Это довольно быстро:)

Начальная реализация может выглядеть примерно так:

import itertools, hashlib
_md5 = hashlib.md5()
def run():
    for _ in xrange(100000000):
        _md5.update("foo")

Первый шаг - использовать itertools.repeat, чтобы сделать что-то N раз.

def run_just_repeat():
    for foo in itertools.repeat("foo", 100000000):
        _md5.update(foo)

Вторая вторая оптимизация заключается в использовании itertools.imap, чтобы получить увеличение скорости от необходимости передавать ссылку foo в коде Python. Сейчас в С.

def run_imap_and_repeat():
    for do_work in itertools.imap(_md5.update, itertools.repeat("foo", 10000000)):
        pass

Третья оптимизация - полностью переместить цикл for в код C.

import collections
def run_deque_imap_and_repeat():
    collections.deque(itertools.imap(_md5.update, itertools.repeat("foo", 10000000)))

Окончательная оптимизация состоит в том, чтобы переместить все потенциальные поиски в пространство имен функции запуска:

Эта идея взята с самого конца http://docs.python.org/library/itertools.html?highlight=itertools

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

Лично я имел смешанный успех с этим показом улучшений. то есть. Небольшие улучшения при определенных условиях, благодаря импорту модуля xxx, также демонстрирующему повышение производительности, не передавая его. Кроме того, иногда, если я передаю некоторые переменные, а не другие, я также вижу небольшие различия. Дело в том, что я чувствую, что вам нужно проверить себя, чтобы увидеть, работает ли это для вас.

def run_deque_imap_and_repeat_all_local(deque = collections.deque, 
        imap = itertools.imap, _md5 = _md5, repeat = itertools.repeat, 
        md5 = hashlib.md5):
    update = _md5.update
    deque(imap(_md5.update, repeat("foo", 100000000)), maxlen = 0)

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

def run_any_like_presentation_all_local(any = any, deque = collections.deque, 
        imap = itertools.imap, _md5 = _md5, repeat = itertools.repeat, 
        md5 = hashlib.md5):
    any(imap(_md5.update, repeat("foo", 100000000)))

Хорошо, теперь давайте запустим несколько тестов (Python 2.7.2 OS X Snow Leopard 64-bit):

• run_reference - 123,913 секунд

• run_deque_imap_and_repeat_all_local - 51.201 секунд

• run_deque_local_imap_and_repeat - 53,013 секунды

• run_deque_imap_and_repeat - 48,913 секунд

• run_any_like_presentation - 49,833 секунды

• run_any_like_presentation_all_local - 47,780 секунд

И только для ударов в Python3 (Python 3.2 OS X Snow Leopard 64-bit):

• run_reference - 94,273 секунды (вызовы функций 100000004!)

• run_deque_imap_and_repeat_all_local - 23,929 секунды

• run_deque_local_imap_and_repeat - 23,298 секунд

• run_deque_imap_and_repeat - 24.201 секунд

• run_any_like_presentation - 24,026 секунд

• run_any_like_presentation_all_local - 25,316 секунд

Вот мой источник для тестов:

import itertools, hashlib, collections
_md5 = hashlib.md5()

def run_reference():
    for _ in xrange(100000000):
        _md5.update("foo")

def run_deque_imap_and_repeat_all_local(deque = collections.deque,
        imap = itertools.imap, _md5 = _md5, repeat = itertools.repeat,
        md5 = hashlib.md5):
    deque(imap(_md5.update, repeat("foo", 100000000)), maxlen = 0)

def run_deque_local_imap_and_repeat(deque = collections.deque,
        imap = itertools.imap, _md5 = _md5, repeat = itertools.repeat,
        md5 = hashlib.md5):
    deque(imap(_md5.update, repeat("foo", 100000000)), maxlen = 0)

def run_deque_imap_and_repeat():
    collections.deque(itertools.imap(_md5.update, itertools.repeat("foo", 100000000)),
            maxlen = 0)

def run_any_like_presentation():
    any(itertools.imap(_md5.update, itertools.repeat("foo", 100000000)))

def run_any_like_presentation_all_local(any = any, deque = collections.deque,
        imap = itertools.imap, _md5 = _md5, repeat = itertools.repeat,
        md5 = hashlib.md5):
    any(imap(_md5.update, repeat("foo", 100000000)))

import cProfile
import pstats

def performance_test(a_func):
    cProfile.run(a_func, 'stats')
    p = pstats.Stats('stats')
    p.sort_stats('time').print_stats(10)

performance_test('run_reference()')
performance_test('run_deque_imap_and_repeat_all_local()')
performance_test('run_deque_local_imap_and_repeat()')
performance_test('run_deque_imap_and_repeat()')
performance_test('run_any_like_presentation()')
performance_test('run_any_like_presentation_all_local()')

и Python3

import itertools, hashlib, collections
_md5 = hashlib.md5()

def run_reference(foo = "foo".encode('utf-8')):
    for _ in range(100000000):
        _md5.update(foo)

def run_deque_imap_and_repeat_all_local(deque = collections.deque,
        imap = map, _md5 = _md5, repeat = itertools.repeat,
        md5 = hashlib.md5):
    deque(imap(_md5.update, repeat("foo".encode('utf-8'), 100000000)), maxlen = 0)

def run_deque_local_imap_and_repeat(deque = collections.deque,
        imap = map, _md5 = _md5, repeat = itertools.repeat,
        md5 = hashlib.md5):
    deque(imap(_md5.update, repeat("foo".encode('utf-8'), 100000000)), maxlen = 0)

def run_deque_imap_and_repeat():
    collections.deque(map(_md5.update, itertools.repeat("foo".encode('utf-8'), 100000000)),
            maxlen = 0)

def run_any_like_presentation():
    any(map(_md5.update, itertools.repeat("foo".encode('utf-8'), 100000000)))

def run_any_like_presentation_all_local(any = any, deque = collections.deque,
        imap = map, _md5 = _md5, repeat = itertools.repeat):
    any(imap(_md5.update, repeat("foo".encode('utf-8'), 100000000)))

import cProfile
import pstats

def performance_test(a_func):
    cProfile.run(a_func, 'stats')
    p = pstats.Stats('stats')
    p.sort_stats('time').print_stats(10)

performance_test('run_reference()')
performance_test('run_deque_imap_and_repeat_all_local()')
performance_test('run_deque_local_imap_and_repeat()')
performance_test('run_deque_imap_and_repeat()')
performance_test('run_any_like_presentation()')
performance_test('run_any_like_presentation_all_local()')

Другое дело, не делайте этого в реальном проекте, если нет узкого места в производительности, подлежащего сертификации.

И, наконец, если нам действительно нужна морковь (кроме написания кода, который имеет смысл, и не подвержен ошибкам) ​​в те трудные времена, когда любой из них фактически выполняет deque, ваш более разумный код будет лучшеВы можете воспользоваться преимуществами улучшений в более новых версиях Python без необходимости изменения вашей кодовой базы.

http://www.python.org/doc/essays/list2str/ - хорошее чтение о том, как подходить к оптимизации Python.(т. е. в идеале написание C-расширения - это НЕ первое, чего вы достигнете).

Я также хотел бы указать на ответ Гарета, поскольку он может понять, почему любой может выполнить deque.

Answer 3

Функция run_any_counter не имеет явного возвращаемого значения и, таким образом, возвращает None, что равно False в логическом контексте, и, следовательно, any потребляет всю итерацию.

Более общий способ использования итераций приведен в разделе recipes для itertools .Он не полагается на ложное возвращаемое значение.

Сравнение run_any_like_presentation и т. Д .: imap(f, seq) выполняет поиск f только один раз, тогда как понимание списка [f(x) for x in seq] делает это для каждого элемента seq,[x for x in imap(f, seq)] - забавный способ написания list(imap(f, x)), но оба создают ненужный список.

Наконец, цикл for присваивается переменной цикла, даже если она не используется.Так что это немного медленнее.

Answer 4

Затем он машет рукой, не вдаваясь в подробности о том, почему.

Поскольку фактический цикл выполняется непосредственно вместо интерпретации байт-кода Python.1006 *

Почему мой объект Counter сработал и моя функция print_true провалилась?

any останавливается, как только он находит возвращаемое значение true-ish, потому что он знает, что выполняется условие "any" (оценка короткого замыкания).1014 * возвращает "awesome", что соответствует действительности.counter.count_one не имеет явного return, поэтому возвращает None, что неверно.