Python'da sıralanmış dizileri birleştirme

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

Python'da sıralanmış dizileri birleştirmeye çalışıyorum. Bunu nasıl iyileştirebilirim? Dürüst olmak gerekirse, bunu Python'da değil C'de yazmışım gibi görünüyor

Answer 1

çeşitli

• merge_len kullanılmamış
• basit kontrollerin etrafındaki fazladan parantezler gereksizdir
• l1_ptr <= len_list1-1 olarak daha net hale getirilebilir l1_ptr < len_list1
• l1_ptrbirkaç karakter kaydetmek için değişken adını kullanmak, adından ne yaptığını tahmin etmeyi zorlaştırırken işe yaramaz

Doğrudan endekslerle çalışmak gerçekten Pythonic değildir. Bunu iterve kullanarak daha genel hale getirebilir nextve tüm yinelenebilirler için çalışabilirsiniz.

yazıyor

yazarak bilgi ekleyin:

import typing

T = typing.TypeVar("T")


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

Bu, bu işlevin (ve onun IDE'sinin) kullanıcısı için ek açıklamadır.

belge dizisi

Yöntemin ne yaptığı, arayandan ne beklediği ve geri döndüğü hakkında biraz açıklama ekleyin.

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 `<=`).
    ...
    """

yineleyici

Bunun yerine kullanabileceğiniz indeksi takibi için iterve next. Öğeleri bir listeye eklemenize bile gerek yok, yieldonları yapabilirsiniz , böylece yöntemi çağıran kişi bunu ne şekilde kullanmak istediğine karar verebilir.

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)

O zaman yapılması gereken tek şey bitmemiş yineleyiciye devam etmektir.

    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

test yapmak

En basit durumlardan başlayarak davranışı test edebilirsiniz:

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"]))

Azalan

Bu testi yaptıktan sonra, azalan yinelemeleri de almak için davranışı kolayca genişletebilirsiniz:

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

ascendingKarışıklığı önlemek ve geriye dönük uyumluluğu korumak için anahtar kelimeyi yalnızca anahtar kelime bağımsız değişkeni olarak ekledim

Testlerinden biri:

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

4 boşluklu girinti kullanın .

Aynı değişmeyen değerden tekrar tekrar 1 çıkarmayın.

Koşullu karşılaştırmayı basitleştirin: sadece else.

Yararlanın list.extend () .

Toplama şartlarını bırakın: aslında gerekli değiller. Gibi kod , liste sınırlarını aşsa zs.extend(xs[xi:])bile iyi çalışır xi.

Kod ağırlığını hafifletmek ve okunabilirliği artırmak için değişken adlarını kısaltın. Burada bir anlam kaybı yok, çünkü tüm kısa isimler oldukça gelenekseldir ve bunun gibi genel bir işlevde anlamlıdır.

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

Dün gece yineleyici tabanlı bir çözüm yazdım ama bir şekilde next()bunun kullanışlı bir defaultargümanı desteklediğini unuttum : kod garipti ve Maarten Fabré daha güzel bir uygulama yaptı. Ancak more_itertools.peekable() kullanmaya istekliyseniz , basit, okunabilir bir uygulama elde edebilirsiniz. Yorumlarda daha da basitleştirmeme yardımcı olan bir fikir için süper yağmur sayesinde .

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)