#python #алгоритм #list #список
Отвечая на данный вопрос, я заинтересовался более универсальным решением...
Есть список произвольной вложенности, например:
['1','2', ['1',['2','4',['5','6']]],'7','8']
Необходимо применить функцию ко всем элементам списка (включая все вложенные), сохранив
при этом его структуру.
Например преобразовать все элементы в числа и возвести их в квадрат, чтобы получилось:
[1, 4, [1, [4, 16, [25, 36]]], 49, 64]
Я опубликовал свой вариант решения, но мне было бы интересно увидеть альтернативные
(более интересные) решения.
Ответы
Ответ 1
Чтобы поместу изменить, не создавая новые списки (поиск в глубину—depth-first search (DFS)): def apply_nested(func, lst, isatom=lambda item: not isinstance(item, list)): for i, item in enumerate(lst): if isatom(item): lst[i] = func(item) else: apply_nested(func, item, isatom) Здесь isatom() предикат определяет, что является неразрывным элементом (атомом) для заданного алгоритма: apply_nested(func, lst) вызывает func функцию для каждого атома в (глубоковложенном) списке lst. Похожее решение: flatten_gen(). Легко создать нерекурсивный вариант (поиск в ширину—breadth-first search (BFS), если использовать deque.popleft()): def apply_nested(func, lst, isatom=lambda item: not isinstance(item, list)): stack = [lst] while stack: lst = stack.pop() for i, item in enumerate(lst): if isatom(item): lst[i] = func(item) else: stack.append(item) Пример: >>> nested = ['1','2', ['1',['2','4',['5','6']]],'7','8'] >>> apply_nested(lambda atom: int(atom)**2, nested) >>> nested [1, 4, [1, [4, 16, [25, 36]]], 49, 64] Аналогично, можно определить функции, которые возвращают новые значения, не изменяя ввода (DFS): def map_nested(func, lst, isatom=lambda item: not isinstance(item, list)): return [func(item) if isatom(item) else map_nested(func, item, isatom) for item in lst] Нерекурсивный вариант: def map_nested(func, lst, isatom=lambda item: not isinstance(item, list)): result = [] stack = [(lst, result)] while stack: lst, new_lst = stack.pop() for item in lst: if isatom(item): new_lst.append(func(item)) else: # item is a sublist (collection) sublist = [] new_lst.append(sublist) stack.append((item, sublist)) return result Пример: >>> map_nested(lambda atom: int(atom)**2, nested)) [1, 4, [1, [4, 16, [25, 36]]], 49, 64]Ответ 2
Решение: def map_nested(lst, func=lambda x: x): assert isinstance(lst, list), '"lst" parameter is NOT a list' return [map_nested(lst[i], func) if isinstance(lst[i], list) else func(lst[i]) for i in range(len(lst))] Тест: In [154]: lst = ['1', '2', ['1', ['2', '4', ['5', '6']]], '7', '8'] In [155]: map_nested(lst, lambda x: int(x)**2) Out[155]: [1, 4, [1, [4, 16, [25, 36]]], 49, 64]Ответ 3
Сложно что-то выдумать - в вашем решении уже вроде все есть. Однако, можно попробовать внести пару (ненужных?) изменений + функция в одну строку. Большую функцию тоже можно при желании разместить в 1 строку, однако это уже будет чересчур: import timeit def map_nested(lst, func=lambda x: x, forbidden_types=(str, int)): container_type = type(lst) if hasattr(lst, '__iter__') and type(lst) not in forbidden_types: return container_type(map_nested(item, func) for item in lst) else: try: return func(lst) except: return lst def map_nested_1line(lst, func=lambda x: x): return [map_nested_1line(item, func) for item in lst] if type(lst) is list else func(lst) UPDATE: Утро вечера мудренее и подумав я родил нерекурсивный вариант этой функции. Нерекурсивный хорош тем, что не упадет на длинных и сильно вложенных списках на ОС с ограничением на длину рекурсии. Плох тем, что очень медленный. Суть нерекурсивного решения в том, что в специальный массив заносится порядок входа и выхода во вложенные списки. Находим вложенный массив - заносим указатель на него + индекс в спец. хранилище. Выходим из него - указатель и индекс извлекаем. # Also non-recursive. Yay! def map_nested_inplace(lst, func=lambda x: x, forbidden_types=(str, int)): # forbidden_types не используется processed_elements = 0 # assert type(lst) is list # blah-blah current_container = lst containers_repo = [[current_container, 0]] # До тех пор, пока не были обработаны все списки и под-списки while len(containers_repo) != 0: while True: try: # Следующий элемент в текущем списке. # Может быть как числом, так и новым под-списком next_one = current_container[containers_repo[-1][1]] break # Исключение означает, что под-список кончился. # Т.к. он кончился, то убираем его из хранилища # и пробуем извлечь следующий элемент except IndexError: containers_repo.pop() if len(containers_repo) == 0: break current_container = containers_repo[-1][0] if len(containers_repo) != 0: if type(next_one) is list: # Это под-список, а не число. # Заносим под-список в хранилище и # на следующей итерации открываем уже его containers_repo[-1][1] += 1 current_container = next_one containers_repo.append([current_container, 0]) else: current_container[containers_repo[-1][1]] = func(current_container[containers_repo[-1][1]]) containers_repo[-1][1] += 1 # ради небольшой проверки processed_elements += 1 # set также работает, но непохоже, чтобы он сохранял порядок lst = ['1', 'an error', ('1', ['2', '4', (5, '6')]), '7', 8] lst_simple = ['1', '2', ['1', ['2', '4', ['5', '6']]], '7', '8'] lst_another_simple = ['1', '2', ['1', ['2', '4', ['5', '6']], ['6', '6', '6'], ['8', '8']], '7', ['11'], '8'] print(map_nested(lst, lambda x: int(x)**2)) print(map_nested_1line(lst_simple, lambda x: int(x)**2)) print(map_nested_1line([], lambda x: int(x)**2)) map_nested_inplace(lst_another_simple, lambda x: int(x)**2) print(lst_another_simple) Также немного тестирования: import random test_array = [] container_tree = [test_array] current_container = container_tree[-1] TOTAL_AMOUNT = 10000 NEW_LEVEL_PROBABILITY = 0.5 for i in range(TOTAL_AMOUNT): if random.random() >= NEW_LEVEL_PROBABILITY: current_container.append([]) container_tree.append(current_container[-1]) current_container = current_container[-1] elif len(container_tree) > 1: current_container = container_tree[-2] current_container.append(str(random.randint(0, 20))) # Для работоспособности рекурсивных методов # Впрочем, без старта новго потока с threading.stack_size() все равно не будет работать :( import sys if sys.getrecursionlimit() < len(container_tree) * 2: sys.setrecursionlimit(len(container_tree) * 2) setup_statement = """from __main__ import test_array, """ # Не используется lambda x**2, потому что # в inplace квадраты будут накатываться до тех пор, # пока хватит памяти - список для каждого прохода должен генерироваться заново print(timeit.timeit("map_nested_inplace(test_array)", setup=setup_statement + "map_nested_inplace", number=100)) print(timeit.timeit("map_nested_1line(test_array)", setup=setup_statement + "map_nested_1line", number=100)) print(timeit.timeit("map_nested(test_array)", setup=setup_statement + "map_nested", number=100)) >>> 1.8096923486838081 # Без рекурсии >>> 0.9477624593712808 # Однострочник >>> 1.827232542223693 # Большая функцияОтвет 4
В голову сразу пришло такое решение def anon(l, func=lambda x: int(x) ** 2): for n, i in enumerate(l): if type(i) != list: l[n] = func(i) else: anon(i) return l lst = ['1', '2', ['1', ['2', '4', ['5', '6']]], '7', '8'] print(anon(lst)) >>> [1, 4, [1, [4, 16, [25, 36]]], 49, 64]
Комментариев нет:
Отправить комментарий