Unione di array ordinati in 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

Sto cercando di unire gli array ordinati in Python. Come posso migliorare questo? Onestamente sembra che l'abbia scritto in C e non in Python

Answer 1

vari

• merge_lenè inutilizzato
• le parentesi extra attorno ai semplici controlli non sono necessarie
• l1_ptr <= len_list1-1può essere reso più chiaro comel1_ptr < len_list1
• usare il nome della variabile l1_ptrper salvare alcuni caratteri rendendo più difficile indovinare dal nome cosa fa non è utile

Lavorare direttamente con gli indici non è davvero pitone. Puoi renderlo più generico, usando itere next, e funziona per tutti gli iterabili.

digitando

aggiungi informazioni sulla digitazione:

import typing

T = typing.TypeVar("T")


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

Questa è una spiegazione aggiuntiva per l'utente di questa funzione (e del suo IDE).

docstring

Aggiungi alcune spiegazioni su ciò che il metodo fa, si aspetta dal chiamante e restituisce.

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

iteratore

Invece di tenere traccia dell'indice, puoi usare itere next. Non hai nemmeno bisogno di aggiungere gli elementi a un elenco, puoi yieldfarlo, quindi il chiamante del metodo può decidere in che modo vuole usarlo.

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)

Quindi tutto ciò che deve essere fatto è continuare l'iteratore che non è finito

    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

Puoi testare il comportamento, partendo dai casi più semplici:

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

discendente

Una volta che hai questi test in atto, puoi facilmente espandere il comportamento per prendere anche iterabili discendenti:

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

Ho aggiunto la ascendingparola chiave come argomento di sola parola chiave per evitare confusione e mantenere la compatibilità con le versioni precedenti

Uno dei suoi test:

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

Usa un rientro di 4 spazi .

Non sottrarre ripetutamente 1 dallo stesso valore immutabile.

Semplifica il condizionale di confronto: usa semplicemente else.

Approfitta di list.extend() .

Elimina i condizionali di riepilogo: in realtà non sono necessari. Il codice simile zs.extend(xs[xi:])funzionerà bene anche se xisupera i limiti dell'elenco.

Accorciare i nomi delle variabili per alleggerire il peso del codice e aumentare la leggibilità. Non c'è perdita di significato qui, perché tutti i nomi brevi sono abbastanza convenzionali e hanno senso in una funzione generica come questa.

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

Ieri sera ho scritto una soluzione basata su iteratore ma in qualche modo ho dimenticato che next()supporta un defaultargomento utile: il codice era imbarazzante e Maarten Fabré ha fatto un'implementazione migliore. Ma se sei disposto a usare more_itertools.peekable() puoi ottenere un'implementazione semplice e leggibile. Grazie a superb-rain per un'idea nei commenti che mi ha aiutato a semplificare ulteriormente.

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)