Hợp nhất các mảng đã sắp xếp trong 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

Tôi đang cố gắng hợp nhất các mảng được sắp xếp trong python. Tôi có thể cải thiện điều này bằng cách nào? Thành thật mà nói, có vẻ như tôi đã viết điều này bằng C chứ không phải bằng Python

Answer 1

đa dạng

• merge_len không được sử dụng
• các dấu ngoặc đơn xung quanh các kiểm tra đơn giản là không cần thiết
• l1_ptr <= len_list1-1 có thể được làm rõ ràng hơn như l1_ptr < len_list1
• sử dụng tên biến l1_ptrđể lưu một vài ký tự trong khi làm cho việc đoán từ tên biến trở nên không hữu ích.

Làm việc với các chỉ số trực tiếp thực sự không thực sự khó. Bạn có thể làm cho điều này chung chung hơn, sử dụng itervà nextvà làm việc cho tất cả các tệp lặp.

đánh máy

thêm thông tin đánh máy:

import typing

T = typing.TypeVar("T")


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

Đây là giải thích bổ sung cho người dùng chức năng này (và IDE của anh ta).

docstring

Thêm một số giải thích về những gì phương thức thực hiện, mong đợi từ người gọi và trả về.

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

người lặp lại

Thay vì theo dõi chỉ mục, bạn có thể sử dụng itervà next. Bạn thậm chí không cần thêm các mục vào danh sách, bạn có thể thêm yieldchúng, vì vậy người gọi phương thức có thể quyết định cách anh ta muốn sử dụng điều nà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)

Sau đó, tất cả những gì cần làm là tiếp tục trình lặp chưa kết thúc

    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

thử nghiệm

Bạn có thể kiểm tra hành vi, bắt đầu với các trường hợp đơn giản nhất:

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

giảm dần

Khi bạn đã có sẵn các thử nghiệm này, bạn có thể dễ dàng mở rộng hành vi để cũng có các lần lặp giảm dần:

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

Tôi đã thêm ascendingtừ khóa làm đối số chỉ từ khóa để tránh nhầm lẫn và giữ khả năng tương thích ngược

Một trong những bài kiểm tra của nó:

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

Sử dụng thụt lề 4 dấu cách .

Đừng liên tục trừ 1 cho cùng một giá trị không thay đổi.

Đơn giản hóa so sánh có điều kiện: chỉ sử dụng else.

Tận dụng list.extend () .

Bỏ các điều kiện kết thúc: chúng không thực sự cần thiết. Mã like zs.extend(xs[xi:])sẽ hoạt động tốt ngay cả khi xivượt quá giới hạn danh sách.

Rút ngắn tên biến để giảm trọng lượng mã và tăng khả năng đọc. Không có gì mất đi ý nghĩa ở đây, bởi vì tất cả các tên ngắn đều khá thông thường và có ý nghĩa trong một chức năng chung như thế này.

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

Đêm qua, tôi đã viết một giải pháp cơ sở trình lặp nhưng bằng cách nào đó quên rằng nó next()hỗ trợ một defaultđối số tiện dụng : mã rất khó xử và Maarten Fabré đã thực hiện một cách tốt hơn. Nhưng nếu bạn sẵn sàng sử dụng more_itertools.peekable (), bạn có thể đạt được một triển khai đơn giản, dễ đọc. Cảm ơn tuyệt vời vì một ý tưởng trong phần bình luận đã giúp tôi đơn giản hóa hơn nữa.

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)