Python에서 정렬 된 배열 병합

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

파이썬에서 정렬 된 배열을 병합하려고합니다. 어떻게 개선 할 수 있습니까? 솔직히 파이썬이 아닌 C로 쓴 것 같습니다.

Answer 1

여러

• merge_len 미사용
• 간단한 검사를 둘러싼 추가 괄호는 필요하지 않습니다.
• l1_ptr <= len_list1-1 더 명확하게 만들 수 있습니다. l1_ptr < len_list1
• 변수 이름 l1_ptr을 사용하여 몇 개의 문자를 저장하면서 이름에서 무엇을하는지 추측하기 어렵게 만드는 것은 유용하지 않습니다.

인덱스로 직접 작업하는 것은 실제로 비단뱀 적이 지 않습니다. 당신이 더 많은 일반 사용 할 수 있습니다 iter및 next모든 반복 가능 객체에 대한, 작업.

타자

입력 정보 추가 :

import typing

T = typing.TypeVar("T")


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

이것은이 함수 (및 그의 IDE) 사용자를위한 추가 설명입니다.

독 스트링

메서드가 무엇을하고, 호출자로부터 기대하고, 반환하는지에 대한 설명을 추가합니다.

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

반복자

색인을 추적하는 대신 iter및 을 사용할 수 있습니다 next. 목록에 항목을 추가 할 필요도 없습니다. 항목을 추가 할 수 yield있으므로 메서드 호출자가이 항목을 사용할 방법을 결정할 수 있습니다.

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

---

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

테스트

가장 간단한 경우부터 시작하여 동작을 테스트 할 수 있습니다.

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

내림차순

이러한 테스트가 준비되면 내림차순 반복 가능 항목도 사용하도록 동작을 쉽게 확장 할 수 있습니다.

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

ascending혼동을 피하고 이전 버전과의 호환성을 유지하기 위해 키워드를 키워드 전용 인수로 추가했습니다.

테스트 중 하나 :

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 칸 들여 쓰기를 사용합니다 .

동일한 변하지 않는 값에서 반복적으로 1을 빼지 마십시오.

조건부 비교를 단순화하십시오 else..

list.extend ()를 활용하십시오 .

요약 조건문을 삭제합니다. 실제로 필요하지 않습니다. 목록 경계를 초과 zs.extend(xs[xi:])하더라도 같은 코드 는 잘 작동합니다 xi.

변수 이름을 줄여 코드 무게를 줄이고 가독성을 높입니다. 모든 짧은 이름은 매우 일반적이고 이와 같은 일반적인 기능에서 의미가 있기 때문에 여기서 의미를 잃지 않습니다.

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

어젯밤 나는 반복자 기반 솔루션을 작성했지만 next()편리한 default주장 을 지원하는 것을 잊었습니다 . 코드는 어색했고 Maarten Fabré 는 더 멋진 구현을했습니다. 그러나 more_itertools.peekable () 을 사용하려는 경우 간단하고 읽기 쉬운 구현을 얻을 수 있습니다. 내가 더 단순화하는 데 도움이 된 의견에 대한 아이디어에 대한 훌륭한 비 덕분 입니다.

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)