Fusionner des tableaux triés en 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

J'essaie de fusionner des tableaux triés en python. Comment puis-je améliorer cela ? Honnêtement, on dirait que j'ai écrit ceci en C et non en Python

Answer 1

divers

• merge_lenn'est pas utilisé
• les parenthèses supplémentaires autour des simples vérifications sont inutiles
• l1_ptr <= len_list1-1peut être rendu plus clair commel1_ptr < len_list1
• utiliser le nom de la variable l1_ptrpour enregistrer quelques caractères tout en rendant plus difficile de deviner à partir du nom ce qu'il fait n'est pas utile

Travailler directement avec les indices n'est en effet pas vraiment pythonique. Vous pouvez rendre cela plus générique, en utilisant iteret next, et travailler pour tous les itérables.

dactylographie

ajouter des informations de frappe :

import typing

T = typing.TypeVar("T")


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

C'est une explication supplémentaire pour l'utilisateur de cette fonction (et son IDE).

chaîne de documentation

Ajoutez quelques explications sur ce que la méthode fait, attend de l'appelant et renvoie.

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

itérateur

Au lieu de suivre l'index, vous pouvez utiliser iteret next. Vous n'avez même pas besoin d'ajouter les éléments à une liste, vous pouvez yieldles ajouter, ainsi l'appelant de la méthode peut décider de quelle manière il veut l'utiliser.

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)

Ensuite, il ne reste plus qu'à continuer l'itérateur qui n'est pas terminé

    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

essai

Vous pouvez tester le comportement en commençant par les cas les plus simples :

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

descendant

Une fois ces tests en place, vous pouvez facilement étendre le comportement pour prendre également des itérables descendants :

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

J'ai ajouté le mot- ascendingclé en tant qu'argument mot-clé uniquement pour éviter toute confusion et conserver la rétrocompatibilité

Un de ses tests :

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

Utilisez un retrait de 4 espaces .

Ne soustrayez pas à plusieurs reprises 1 de la même valeur inchangée.

Simplifiez la comparaison conditionnelle : utilisez simplement else.

Profitez de list.extend() .

Laissez tomber les conditionnels de conclusion : ils ne sont pas vraiment nécessaires. Le code comme zs.extend(xs[xi:])fonctionnera bien même s'il xidépasse les limites de la liste.

Raccourcissez les noms des variables pour alléger le poids du code et augmenter la lisibilité. Il n'y a pas de perte de sens ici, car tous les noms abrégés sont assez conventionnels et ont un sens dans une fonction générique comme celle-ci.

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

Hier soir, j'ai écrit une solution basée sur un itérateur, mais j'ai oublié que cela next()prend en charge un defaultargument pratique : le code était maladroit et Maarten Fabré a fait une implémentation plus agréable. Mais si vous souhaitez utiliser more_itertools.peekable() , vous pouvez obtenir une implémentation simple et lisible. Merci à superb-rain pour une idée dans les commentaires qui m'a aidé à simplifier davantage.

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)