Scalanie posortowanych tablic w Pythonie

Question

def merge_arrays(list1, list2):
  len_list1 = len(list1); len_list2 = len(list2)
  merge_len = len_list1 + len_list2
  merge_list = []

  l1_ptr = 0
  l2_ptr = 0
  # import pdb; pdb.set_trace()
  while(l1_ptr <= len_list1-1 and l2_ptr <= len_list2-1):

    if (list1[l1_ptr] <= list2[l2_ptr]):
      merge_list.append(list1[l1_ptr])
      l1_ptr += 1
    
    elif (list1[l1_ptr] > list2[l2_ptr]):
      merge_list.append(list2[l2_ptr])
      l2_ptr += 1
      
  if l1_ptr > len_list1-1: #list1 exhausted
    for item in list2[l2_ptr:]:
      merge_list.append(item)
  else:
    for item in list1[l1_ptr:]:
      merge_list.append(item)

  return merge_list

Próbuję scalić posortowane tablice w Pythonie. Jak mogę to poprawić? Szczerze, wygląda na to, że napisałem to w C, a nie w Pythonie

Answer 1

różny

• merge_lenjest nieużywany
• dodatkowe nawiasy wokół prostych sprawdzeń są niepotrzebne
• l1_ptr <= len_list1-1może być jaśniejsze, ponieważl1_ptr < len_list1
• użycie nazwy zmiennej l1_ptrdo zapisania kilku znaków, jednocześnie utrudniając odgadnięcie z nazwy, co ona robi, nie jest przydatne

Bezpośrednia praca z indeksami nie jest tak naprawdę pythoniczna. Możesz uczynić to bardziej ogólnym, używając iteri next, i działać dla wszystkich iterowalnych.

pisanie na maszynie

dodaj informacje dotyczące pisania:

import typing

T = typing.TypeVar("T")


def merge_sorted_iterables(
    iterable1: typing.Iterable[T], iterable2: typing.Iterable[T]
) -> typing.Iterable[T]:

To jest dodatkowe wyjaśnienie dla użytkownika tej funkcji (i jego IDE).

dokumentacja

Dodaj wyjaśnienie, co robi metoda, czego oczekuje od wywołującego i zwraca.

def merge_sorted_iterables(
    iterable1: typing.Iterable[T], iterable2: typing.Iterable[T]
) -> typing.Iterable[T]:
    """Merge 2 sorted iterables.
    
    The items in the iterables need to be comparable (and support `<=`).
    ...
    """

iterator

Zamiast śledzić indeks, możesz użyć iteri next. Nie musisz nawet dodawać elementów do listy, możesz yieldje, aby osoba wywołująca metodę mogła zdecydować, w jaki sposób chce tego użyć.

done = object()

iterator1 = iter(iterable1)
iterator2 = iter(iterable2)

item1 = next(iterator1, done)
item2 = next(iterator2, done)
while item1 is not done and item2 is not done:
    if item1 <= item2:
        yield item1
        item1 = next(iterator1, done)
    else:
        yield item2
        item2 = next(iterator2, done)

Następnie wystarczy tylko kontynuować iterator, który nie jest skończony

    if item1 is not done:
        yield item1
        yield from iterator1
    if item2 is not done:
        yield item2
        yield from iterator2

---

import typing

T = typing.TypeVar("T")


def merge_sorted_iterables(
    iterable1: typing.Iterable[T], iterable2: typing.Iterable[T]
) -> typing.Iterable[T]:
    """Merge 2 sorted iterables.
    
    The items in the iterables need to be comparable (and support `<=`).
    ...
    """
    done = object()
    
    iterator1 = iter(iterable1)
    iterator2 = iter(iterable2)
    
    item1 = next(iterator1, done)
    item2 = next(iterator2, done)
    
    while item1 is not done and item2 is not done:
        if item1 <= item2:
            yield item1
            item1 = next(iterator1, done)
        else:
            yield item2
            item2 = next(iterator2, done)

    if item1 is not done:
        yield item1
        yield from iterator1
    if item2 is not done:
        yield item2
        yield from iterator2

testowanie

Możesz przetestować zachowanie, zaczynając od najprostszych przypadków:

import pytest

def test_empty():
    expected = []
    result = list(merge_sorted_iterables([], []))
    assert result == expected

def test_single():
    expected = [0, 1, 2]
    result = list(merge_sorted_iterables([], range(3)))
    assert expected == result
    result = list(merge_sorted_iterables(range(3), [],))
    assert expected == result

def test_simple():
    expected = [0, 1, 2, 3, 4, 5]
    result = list(merge_sorted_iterables([0, 1, 2], [3, 4, 5]))
    assert result == expected
    result = list(merge_sorted_iterables([0, 2, 4], [1, 3, 5]))
    assert result == expected
    result = list(merge_sorted_iterables([3, 4, 5], [0, 1, 2],))
    assert result == expected

def test_string():
    expected = list("abcdef")

    result = list(merge_sorted_iterables("abc", "def"))
    assert result == expected
    result = list(merge_sorted_iterables("ace", "bdf"))
    assert result == expected
    result = list(merge_sorted_iterables("def", "abc",))
    assert result == expected

def test_iterable():
    
    expected = [0, 1, 2, 3, 4, 5]
    result = list(merge_sorted_iterables(iter([0, 1, 2]), iter([3, 4, 5])))
    assert result == expected
    result = list(merge_sorted_iterables(iter([0, 2, 4]), iter([1, 3, 5])))
    assert result == expected
    result = list(merge_sorted_iterables(iter([3, 4, 5]), iter([0, 1, 2]),))
    assert result == expected

def test_comparable():
    with pytest.raises(TypeError, match="not supported between instances of"):
        list(merge_sorted_iterables([0, 1, 2], ["a", "b", "c"]))

malejąco

Gdy już masz ten test, możesz łatwo rozszerzyć zachowanie, aby również wziąć malejące iterowalne:

import operator

def merge_sorted_iterables(
    iterable1: typing.Iterable[T],
    iterable2: typing.Iterable[T],
    *,
    ascending: bool = True,
) -> typing.Iterable[T]:
    """Merge 2 sorted iterables.
    
    The items in the iterables need to be comparable.
    ...
    """
    done = object()

    iterator1 = iter(iterable1)
    iterator2 = iter(iterable2)

    item1 = next(iterator1, done)
    item2 = next(iterator2, done)

    comparison = operator.le if ascending else operator.ge

    while item1 is not done and item2 is not done:
        if comparison(item1, item2):
            yield item1
            item1 = next(iterator1, done)
        else:
            yield item2
            item2 = next(iterator2, done)

    if item1 is not done:
        yield item1
        yield from iterator1
    if item2 is not done:
        yield item2
        yield from iterator2

Dodałem ascendingsłowo kluczowe jako argument zawierający tylko słowo kluczowe, aby uniknąć pomyłek i zachować zgodność wsteczną

Jeden z jego testów:

def test_descending():
    expected = [5, 4, 3, 2, 1, 0]
    result = list(
        merge_sorted_iterables([2, 1, 0], [5, 4, 3], ascending=False)
    )
    assert result == expected
    result = list(
        merge_sorted_iterables([4, 2, 0], [5, 3, 1], ascending=False)
    )
    assert result == expected
    result = list(
        merge_sorted_iterables([5, 4, 3], [2, 1, 0], ascending=False)
    )
    assert result == expected

Answer 2

Użyj wcięcia z 4 spacjami .

Nie odejmij wielokrotnie 1 od tej samej niezmiennej wartości.

Uprość warunek porównania: po prostu użyj else.

Skorzystaj z list.extend() .

Odrzuć warunki końcowe: w rzeczywistości nie są potrzebne. Kod podobny zs.extend(xs[xi:])do działa dobrze, nawet jeśli xiprzekracza granice listy.

Skróć nazwy zmiennych, aby zmniejszyć wagę kodu i zwiększyć czytelność. Nie ma tutaj utraty znaczenia, ponieważ wszystkie krótkie nazwy są dość konwencjonalne i mają sens w funkcji ogólnej, takiej jak ta.

def merge_arrays(xs, ys):
    # Setup.
    xmax = len(xs) - 1
    ymax = len(ys) - 1
    xi = 0
    yi = 0
    zs = []

    # Compare and merge.
    while xi <= xmax and yi <= ymax:
        if xs[xi] <= ys[yi]:
            zs.append(xs[xi])
            xi += 1
        else:
            zs.append(ys[yi])
            yi += 1

    # Merge any remainders and return.
    zs.extend(ys[yi:])
    zs.extend(xs[xi:])
    return zs

Zeszłej nocy napisałem rozwiązanie oparte na iteratorach, ale jakoś zapomniałem, że next()obsługuje on przydatny defaultargument: kod był niewygodny, a Maarten Fabré zrobił ładniejszą implementację. Ale jeśli chcesz użyć more_itertools.peekable() , możesz osiągnąć prostą, czytelną implementację. Dzięki super-deszczowi za pomysł w komentarzach, który pomógł mi jeszcze bardziej uprościć.

from more_itertools import peekable

def merge(xs, ys):
    xit = peekable(xs)
    yit = peekable(ys)
    while xit and yit:
        it = xit if xit.peek() <= yit.peek() else yit
        yield next(it)
    yield from (xit or yit)