Оптимизировать алгоритм работы с кортежами, наборами и словарями - PullRequest
Новая
       16

Оптимизировать алгоритм работы с кортежами, наборами и словарями

2 голосов
/ 01 октября 2019

У меня есть алгоритм сглаживания списка: 

def flatten(s):
    if not s:
        return s
    if isinstance(s[0], (list, set, tuple)):
        return flatten(s[0]) + flatten(s[1:])
    return s[:1] + flatten(s[1:])

Но он не работает, если вы комбинируете два разных типа данных. Например, список внутри кортежа. Есть ли способ сделать это? Также возможны ли сглаживающие дикты? Значения, а не ключи.

Ответы [ 4 ]

3 голосов
/ 01 октября 2019

В SO есть несколько алгоритмов для выравнивания вложенных списков и кортежей, но мы будем придерживаться вашего. Первое наблюдение заключается в том, что ваш алгоритм в том виде, в котором он написан, не будет работать с set экземплярами, поскольку они не являются подписными. Так что наборы должны идти: 

def flatten(s):
    if not s:
        return s
    if isinstance(s[0], (list, tuple)):
        return list(flatten(s[0])) + list(flatten(s[1:]))
    return list(s[:1]) + list(flatten(s[1:]))

flatten([[1,2,(3,4,(5,6))]])

Отпечатки: 

[1, 2, 3, 4, 5, 6]
3 голосов
/ 01 октября 2019

Обычно рекомендуется использовать itertools -> chain или стандартные библиотеки, но для произвольно вложенных контейнеров: 

xlen = len(x)
result = []    

def flatten(x, i, xlen, result):
  if i >= xlen:
    return
  if not isinstance(x[i], (list, set, tuple)):
    result.append(x[i])
  else:
    flatten(list(x[i]), 0, len(x[i]), result)
  flatten(x, i+1, xlen, result)

вы можете добавить угловые ящики для пустых контейнеров и т. Д.

2 голосов
/ 01 октября 2019

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

Ввод: 

from datetime import datetime
from typing import Sequence


def timer(f):
    def wrapped(s):
        start = datetime.now()
        result = f(s)
        print(datetime.now() - start)
        return result
    return wrapped


@timer
def str_method(s: Sequence):
    return [int(x) for x in
            str(s).replace("(", "[").replace(")", "]")[1:-1].replace("[", "").replace("]", "")
            if x not in [",", " "]]


def flatten(s: Sequence):
    if not s:
        return s
    if isinstance(s[0], (list, tuple)):
        return list(flatten(s[0])) + list(flatten(s[1:]))
    return list(s[:1]) + list(flatten(s[1:]))

if __name__ == '__main__':
    s = [1, 2, (3, 4, (5, 6))]
    start = datetime.now()
    print(flatten(s))
    print(datetime.now() - start)
    print(str_method(s))
    print("-")
    s = [(x, ) for x in range(100)]
    start = datetime.now()
    flatten(s)
    print(datetime.now() - start)
    str_method(s)
    print("-")
    s = [(x, ) for x in range(100000)]
    start = datetime.now()
    try:
        print(flatten(s))
    except RecursionError:
        print("RecursionError")
    str_method(s)

Вывод: 

[1, 2, 3, 4, 5, 6]
0:00:00.000022 # flatten
0:00:00.000041 # str_method
[1, 2, 3, 4, 5, 6]
-
0:00:00.000369 # flatten
0:00:00.000122 # str_method
-
RecursionError # flatten
0:00:00.186894 # str_method
1 голос
/ 03 октября 2019

Все остальные ответы верны, но если вы импортируете sympy в свой код, возможно, используйте его метод flatten? Это очень быстро и соответствует вашим потребностям.

...