Упрощение/оптимизация цепочки for-loops

Ответ 1

Прежде всего, это общий процесс, который вы делаете на своих строках. Вы берете несколько строк и каждый из них применяете определенные функции. Затем вы очищаете список. Позвольте сказать некоторое время, что все функции, которые вы применяете к строкам, работают в постоянное время (это неправда, но пока это не имеет значения). В вашем решении вы перебираете список узлов, используя одну функцию (это O (N)). Затем вы выполняете следующую функцию и снова итерации (другое O (N)) и т.д. Таким образом, очевидный способ ускорения - уменьшить количество циклов. Это не так сложно.

Следующее, что нужно сделать, это попытаться оптимизировать ваши функции. Например. вы используете regexp, чтобы проверить, есть ли строка заглавными буквами, но есть str.islower (Возвращаем true, если все обведенные символы в строке строчные, и есть хотя бы один обведенный символ, в противном случае - false).

Итак, это первая попытка упростить и ускорить ваш код:

vocab = ['dog', 'lazy', 'the', 'fly'] # Imagine it a longer list.

# note that first two functions can be combined in one
def no_caps_and_length(s):
    return s if s.islower() and len(s)<=5 else None

# this one is more complicated and cannot be merged with first two
# (not really, but as you say, some functions are rather complicated)
def check_in_vocab_plus_x(s,x):
    # s and x are both str.
    return None if s not in vocab else s+x

# now let introduce a function that would pipe a string through all functions you need
def pipe_through_funcs(s):
    # yeah, here we have only two, but could be more
    funcs = [no_caps_and_length, check_in_vocab_plus_x]
    for func in funcs:
        if s == None: return s
        s = func(s)
    return s

slist = ['the', 'dog', 'jumps', 'over', 'the', 'fly']
# final step:
slist = filter(lambda a: a!=None, map(pipe_through_funcs, slist))

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

vocab = ['dog', 'lazy', 'the', 'fly'] # Imagine it a longer list.

# make a function that does all the checks for filtering
# you can make a big expression and return its result,
# or a sequence of ifs, or anything in-between,
# it won't affect performance,
# but make sure you put cheaper checks first
def my_filter(s):
    if len(s)>5: return False
    if not s.islower(): return False
    if s not in vocab: return False
    # maybe more checks here
    return True

# now we need modifying function
# there is a concern: if you need indices as they were in original list
# you might need to think of some way to pass them here
# as you iterate through filtered out list
def modify(s,x):
    s += x
    # maybe more actions
    return s

slist = ['the', 'dog', 'jumps', 'over', 'the', 'fly']
# final step:
slist = map(modify, filter(my_filter, slist))

Заметим также, что в некоторых случаях генераторы, карты и вещи могут быть быстрее, но это не всегда так. Я полагаю, что если количество элементов, которые вы отфильтровываете, является существенным, возможно, быстрее использовать for-loop с добавлением. Я не стал бы ручаться, что это будет быстрее, но вы можете просто попробовать что-то вроде этого:

initial_list = ['the', 'dog', 'jumps', 'over', 'the', 'fly']
new_list = []
for s in initial_list:
    processed = pipe_through_funcs(s)
    if processed != None: new_list.append(processed)

Ответ 2

Если вы делаете свои функции преобразования унифицированными, вы можете сделать что-то вроде этого:

import random
slist = []
for i in range(0,100):
    slist.append(random.randint(0,1000))

# Unified functions which have the same function description
# x is the value
# i is the counter from enumerate
def add(x, i):
    return x + 2

def replace(x, i):
    return int(str(x).replace('2', str(i)))

# Specifying your pipelines as a list of tuples 
# Where tuple is (filter function, transformer function)
_pipeline = [
    (lambda s: True, add),
    (lambda s: s % 2 == 0, replace),
]

# Execute your pipeline
for _filter, _fn in _pipeline:
    slist = map(lambda item: _fn(*item), enumerate(filter(_filter, slist)))

Код работает как на python 2, так и на python 3. Разница в том, что в Python3 все возвращает генератор, чтобы он не выполнялся до тех пор, пока он не будет. Так эффективно, что у вас будет одна итерация по вашему списку.

print(slist)
<map object at 0x7f92b8315fd0>

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

Например, то, что @Rawing упоминает, что vocab как набор вместо списка будет иметь большое значение, особенно с большим количеством элементов.

Ответ 3

У вас есть куча проверок, с помощью которых вы можете сделать итерацию:

def check1(s):
    if s.islower():
        return s

def check2(s):
    if len(s) < 5:
        return s

checks = [check1, check2]

И итерабельность строк:

l = ['dog', 'Cat', 'house', 'foo']

Таким образом, один вопрос заключается в том, следует ли сначала перебирать сначала проверки или строки.

def checks_first(l, checks):
    for check in checks:
        l = filter(None, map(check, l))

    return list(l)


def strings_first(l, checks):
    res = []

    for item in l:
        for check in checks:
            item = check(item)
            if item is None:
                break
        else:
            res.append(item)

    return res

Вы можете использовать эти два подхода с помощью timeit module. Обратите внимание: вам, возможно, придется использовать подмножество строк для своевременного получения этих результатов.

import timeit

print(timeit.timeit('checks_first(l, checks)', setup='from __main__ import checks_first, checks, l', number=10))
print(timeit.timeit('strings_first(l, checks)', setup='from __main__ import strings_first, checks, l', number=10))

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

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

import functools

def time_func(func, timer_dict):

    @functools.wraps(func)
    def inner(*args, **kwargs):
        t0 = time.time()
        res = func(*args, **kwargs)
        timer_dict[func.__name__] += time.time() - t0
        return res

    return inner

Чтобы применить это к проверкам:

from collections import defaultdict

timer_dict = defaultdict(lambda: 0)
checks = [time_func(check, timer_dict) for check in checks]

Затем вызовите функцию (ы), которая применяет проверки и просмотр timer_dict для информации о времени.

checks_first(l, checks)
strings_first(l, checks)

print(dict(timer_dict))

# {'check1': 0.41464924812316895, 'check2': 0.2684309482574463}

Затем определить узкие места в дорогостоящих проверках либо путем проверки, либо профилирования. Последнее можно выполнить с помощью строковых схем кода с помощью time module или используя профилировщик строк, например это.

Оптимизируйте свои альгосы и структуры данных, чтобы избавиться от этих узких мест. Вы можете взглянуть на Cython для кода, который вам нужно довести до (близкой) скорости C.

Ответ 4

Прежде всего: я думаю, что ваш примерный код не делает то, что вы думаете. Результат ['the0', 'dog1', None, None, 'the4', 'fly5'], но я считаю, что вам не нужны значения None.

Единственный разумный ответ на этот вопрос - измерить вашу производительность и определить узкие места, которые, вероятно, будут в ваших функциях проверки, а не во внешнем цикле.

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

Единственный способ узнать - это профайл вашего кода. Вы должны использовать cProfile вместе с RunSnakeRun и работать над вашими узкими местами, иначе вы в конечном итоге optmizing неправильный материал.

Чтобы профилировать ваш script, вы можете запустить его следующим образом: python -m cProfile <script-name>

Ответ 5

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

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

Если "vocab" имеет слова длиной более пяти букв или слов с прописными буквами, вы должны убрать их из "vocab" , поскольку все слова в "slist" , которые имеют прописные или более пяти букв, для удаления из ваших чеков перед тем, как перейти к vocab.

Последняя оптимизация заключается в том, что определение того, находится ли слово в "slist" в "vocab" , совпадает с тем, как найти их пересечение. Для этого существует множество относительно быстрых алгоритмов, для которых не требуется цикл for. Вот несколько примеров:

Эффективный алгоритм пересечения списков

Вычисление пересечения множества в линейном времени?

Таким образом, вы можете удалить два цикла и уменьшить временную сложность сравнения "vocab" - "slist" для цикла.

Ответ 6

Оптимизации сильно зависят от конкретного кода. Не зная, какие реальные манипуляции выполняются на строках и характер данных, существует низкий шанс для эффективного результата. Более того, ОП конкретно описывает струнные манипуляции как "более сложные". Это уменьшает часть внешних циклов при общей производительности.

Два важных и простых совета, которые я могу добавить к другим ответам здесь, - это использование встроенных вызовов функций и генераторов для оптимизации:

• Встроенные функции повышают производительность при сохранении большей работы в собственном коде. Когда вы используете их для вызова лямбда или других вызовов python, они теряют большую часть производительности. Используйте их, когда задача может быть выполнена с использованием только встроенных встроенных функций. itertools, operator и functools могут помочь в этом.
• Генераторы в основном помогают оптимизации памяти, когда вы не хотите одновременно хранить все значения в памяти. Если вы можете делать все на одной итерации, не используя их, это лучше и экономит накладные расходы генератора.

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

vocab = ['dog', 'lazy', 'the', 'fly'] # Imagine it a longer list.

def check_no_caps(s):
    for char in s:
        if 'A' <= char <= 'Z':
            return None
    return s

def check_nomorethan_five(s):
    return s if len(s) <= 5 else None

def check_in_vocab_plus_x(s, x):
    # s and x are both str.
    return None if s not in vocab else s + str(x)

slist = ['the', 'dog', 'jumps', 'over', 'the', 'fly']

result = [check_in_vocab_plus_x(check_nomorethan_five(check_no_caps(string)), i) for i, string in enumerate(slist)]