Spłaszczenie listy

Algorytm dotyczący spłaszczenia listy jest dla mnie szczególny, ponieważ podczas mojej pierwszej rozmowy kwalifikacyjnej otrzymałem zadanie związane właśnie z tym tematem.

Wtedy rozwiązanie tego algorytmu nie przyszło mi łatwo, ale z biegiem czasu udało mi się wypracować bardziej wyszukane rozwiązania.

Celem zadania było przekształcenie listy:

[10, [20, [25], 30], 50]

tak, by nie było w niej zagnieżdżeń:

[10, 20, 25, 30, 50]

Próba pierwsza:

results = []

def flatten(xs):
    for x in xs:
        if isinstance(x, list):
            flatten(x)
        else:
            results.append(x)
            

To była moja pierwsza próba, w której skorzystałem z globalnej results. Wadą tego podejścia jest fakt, że wynik ponownego wywołania funkcji flatten zapisywany jest w tej samej kolekcji, a zatem spłaszczając dwie odrębne listy uzyskamy jeden wspólny rezultat.

Próba druga:

def flatten(xs, results):
    for x in xs:
        if isinstance(x, list):
            flatten(x, results)
        else:
            results.append(x)

To rozwiązanie niweluje użycie globalnej zmiennej. W tym przypadku funkcja wymaga przekazania listy, która w ramach jej wywołania zostanie zmodyfikowana. W tej liście będą zachowane wyniki. To na co warto zwrócić uwagę to fakt, że funkcja ta nie zwraca wyniku, ponieważ z zasady funkcja, która modyfikuje argument, nie powinna zwracać go z użyciem instrukcji return.

Poniższy kod rozszerza to użycie:

def flatten(xs):
    results = []
    _flatten(xs, results)
    return results
    

def _flatten(xs, results):
    for x in xs:
        if isinstance(x, list):
            _flatten(x, results)
        else:
            results.append(x)

Funkcja flatten rozpoczyna wykonanie zadania poprzez stworzenie wynikowej pustej listy, by potem przekazać ją do _flatten i na sam koniec zwrócić wynik.

Próba trzecia

Poniższe rozwiązanie opiera się na instrukcji return, która zwraca pośrednie wyniki. Przykład ten idealnie obrazuje jak złożony problem zostaje podzielony na mniejsze części. Warto zauważyć, że każdorazowe użycie flatten zwraca spłaszczoną listę, która wymaga ujęcia w końcowym wyniku.

def flatten(xs):
    results = []
    for x in xs:
        if isinstance(x, list):
            results.extend(flatten(x))
        else:
            results.append(x)
    return results

Omawiany temat poruszyłem także w filmiku:

Próba czwarta

Wszystkie przedstawione wcześniej podejścia korzystają z rekurencji, która wg mnie jest najczytelniejszym sposobem rozwiązania tego problemu. Niestety poleganie na rekurencji nie zawsze jest dobrym pomysłem, ponieważ opiera się ona na stosie wywołań, który w dużym stopniu ma ograniczoną pamięć.

Poniższe rozwiązanie wykorzystuje jawny stos (w oparciu o listę).

Należy tutaj pamiętać, aby po przetworzeniu wartości zwrócić wynik w odwrotnej kolejności.

def flatten(xs):
    results = []
    stack = [xs]
    while stack:
        x = stack.pop()
        if isinstance(x, list):
            stack.extend(x)
        else:
            results.append(x)
    return results[::-1]

Zachęcam także do zapoznania się z poniższym filmikiem, który omawia ten temat.