Быстрее вложенных кортежей для списка и обратно

Question

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

Любая помощь очень ценится.

Вот что я до сих пор ...

def listify(self, seq, was, toBe): 
    temp = [] 
    a = temp.append 
    for g in seq: 
    if type(g) == was: 
     a(self.listify(g, was, toBe)) 
    else: 
     a(g) 
    return toBe(temp) 

И вызов для кортежа в список будет выглядеть следующим образом:

self.listify((...), tuple, list) 

Edit: Да, я полностью пропустил оба перечислите (из старой реализации) и забыли ввести часть else.

Спасибо за помощь вам обоим. Я, вероятно, поеду с сопрограммами.

Answer 1

В последнее время я много работал с сопрограммами. Преимущество состоит в том, что вы уменьшаете накладные расходы на вызовы метода. Отправка нового значения в сопрограмму выполняется быстрее, чем вызов функции. В то время как вы не можете сделать рекурсивную сопрограмму, она выкинет ValueError: generator already executing, но вы можете создать пул работников-сопродюсеров - вам нужен один рабочий для каждого уровня дерева. Я сделал некоторый тестовый код, который работает, но еще не рассмотрел вопросы синхронизации.

def coroutine(func): 
    """ A helper function decorator from Beazley""" 
    def start(*args, **kwargs): 
     g = func(*args, **kwargs) 
     g.next() 
     return g 
    return start 

@coroutine 
def cotuple2list(): 
    """This does the work""" 
    result = None 
    while True: 
     (tup, co_pool) = (yield result) 
     result = list(tup) 
     # I don't like using append. So I am changing the data in place. 
     for (i,x) in enumerate(result): 
      # consider using "if hasattr(x,'__iter__')" 
      if isinstance(x,tuple): 
       result[i] = co_pool[0].send((x, co_pool[1:])) 


@coroutine 
def colist2tuple(): 
    """This does the work""" 
    result = None 
    while True: 
     (lst, co_pool) = (yield result) 
     # I don't like using append so I am changing the data in place... 
     for (i,x) in enumerate(lst): 
      # consider using "if hasattr(x,'__iter__')" 
      if isinstance(x,list): 
       lst[i] = co_pool[0].send((x, co_pool[1:])) 
     result = tuple(lst) 

Pure питон альтернатива от должности HYRY в:

def list2tuple(a): 
    return tuple((list2tuple(x) if isinstance(x, list) else x for x in a)) 
def tuple2list(a): 
    return list((tuple2list(x) if isinstance(x, tuple) else x for x in a)) 

Сделайте пул сопрограммам - это хак из бассейна, но это работает:

# Make Coroutine Pools 
colist2tuple_pool = [colist2tuple() for i in xrange(20) ] 
cotuple2list_pool = [cotuple2list() for i in xrange(20) ] 

Теперь сделать некоторые сроки - по сравнению с:

def make_test(m, n): 
    # Test data function taken from HYRY's post! 
    return [[range(m), make_test(m, n-1)] for i in range(n)] 
import timeit 
t = make_test(20, 8) 
%timeit list2tuple(t) 
%timeit colist2tuple_pool[0].send((t, colist2tuple_pool[1:])) 

Результаты - обратите внимание на «и» рядом с «S» во второй строке :-)

1 loops, best of 3: 1.32 s per loop 
1 loops, best of 3: 4.05 us per loop 

Действительно, кажется, слишком быстро, чтобы поверить. Кто-нибудь знает, работает ли timeit с сопрограммами? Вот старинке:

tic = time.time() 
t1 = colist2tuple_pool[0].send((t, colist2tuple_pool[1:])) 
toc = time.time() 
print toc - tic 

результат:

0.000446081161499 

Новые версии IPython и% TIMIT дают предупреждение:

Самый медленный бег взял 9,04 раза длиннее быстрый. Это может
означает, что промежуточный результат в кэше петли, 1000000 лучше из 3: 317 нс на петле

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

Я написал все это с большим количеством дополнительных деталей за последние talk.

Надеюсь, это поможет кому-то, кто хочет играть с генераторами.

Answer 2

Определить две функции отдельно:

def list2tuple(a): 
    return tuple((list2tuple(x) if isinstance(x, list) else x for x in a)) 

def tuple2list(a): 
    return list((tuple2list(x) if isinstance(x, tuple) else x for x in a)) 

некоторые испытания:

t = [1, 2, [3, 4], [5, [7, 8]], 9] 
t2 = list2tuple(t) 
t3 = tuple2list(t2) 
print t2 
print t3 

Результаты:

(1, 2, (3, 4), (5, (7, 8)), 9) 
[1, 2, [3, 4], [5, [7, 8]], 9] 

Edit: для быстрой версии:

def list2tuple2(a, tuple=tuple, type=type, list=list): 
    return tuple([list2tuple2(x) if type(x)==list else x for x in a]) 

def tuple2list2(a, tuple=tuple, type=type): 
    return [tuple2list2(x) if type(x)==tuple else x for x in a] 

Для сравнения я также включают Cython версию:

%%cython 

def list2tuple3(a): 
    return tuple([list2tuple3(x) if type(x)==list else x for x in a]) 

def tuple2list3(a): 
    return [tuple2list3(x) if type(x)==tuple else x for x in a] 

Создайте несколько вложенного списка:

def make_test(m, n): 
    return [[range(m), make_test(m, n-1)] for i in range(n)] 

t = make_test(20, 8) 
t2 = list2tuple2(t) 

Затем сравните скорость:

%timeit listify(t, list, tuple) 
%timeit listify(t2, tuple, list) 
%timeit list2tuple(t) 
%timeit tuple2list(t2) 
%timeit list2tuple2(t) 
%timeit tuple2list2(t2) 
%timeit list2tuple3(t) 
%timeit tuple2list3(t2) 

Результат является:

listify 
1 loops, best of 3: 828 ms per loop 
1 loops, best of 3: 912 ms per loop 

list2tuple generator expression version 
1 loops, best of 3: 1.49 s per loop 
1 loops, best of 3: 1.67 s per loop 

list2tuple2 list comprehension with local cache 
1 loops, best of 3: 623 ms per loop 
1 loops, best of 3: 566 ms per loop 

list2tuple3 cython 
1 loops, best of 3: 212 ms per loop 
10 loops, best of 3: 232 ms per loop 

Answer 3

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

def tuple2list(data): 
    if isinstance(data, dict): 
     return { 
      key: tuple2list(value) 
      for key, value in data.items() 
     } 
    elif isinstance(data, (list, tuple)): 
     return [ 
      tuple2list(item) 
      for item in data 
     ] 
    return data 

def list2tuple(data): 
    if isinstance(data, dict): 
     return { 
      key: list2tuple(value) 
      for key, value in data.items() 
     } 
    elif isinstance(data, (list, tuple)): 
     return tuple(
      list2tuple(item) 
      for item in data 
     ) 
    return data