Comment puis-je m'éloigner de l'école de pensée «for-loop»?

79

C'est une question plutôt conceptuelle, mais j'espérais pouvoir obtenir de bons conseils à ce sujet. Une grande partie de la programmation que je fais se fait avec des tableaux ( NumPy ); Je dois souvent faire correspondre des éléments de deux ou plusieurs tableaux de tailles différentes et la première chose à laquelle je veux en venir est une boucle for, ou pire, une boucle for imbriquée. Je veux éviter les boucles forées autant que possible, car elles sont lentes (au moins en Python).

Je sais que pour beaucoup de choses avec NumPy, il y a des commandes prédéfinies que je dois juste étudier, mais avez-vous (en tant que programmeurs plus expérimentés) un processus de pensée générale qui vous vient à l'esprit lorsque vous devez répéter quelque chose?

J'ai souvent quelque chose comme ça, qui est affreux et que je veux éviter:

small_array = np.array(["one", "two"])
big_array = np.array(["one", "two", "three", "one"])

for i in range(len(small_array)):
    for p in range(len(big_array)):
        if small_array[i] == big_array[p]:
            print "This item is matched: ", small_array[i]

Je sais qu'il existe de nombreuses manières différentes d'y parvenir, mais je m'intéresse à une méthode de réflexion générale, si elle existe.

navet
la source
10
Vous recherchez une programmation fonctionnelle : expressions lambda, fonctions supérieures, génération d'expressions, etc. Google.
Kilian Foth
42
I want to avoid for-loops as much as possible because they are slow (at least in Python).On dirait que vous résolvez le mauvais problème ici. Si vous avez besoin d'itérer sur quelque chose, vous devez itérer sur quelque chose; vous obtiendrez une performance similaire quelle que soit la construction Python que vous utilisez. Si votre code est lent, ce n'est pas parce que vous avez des forboucles; c'est parce que vous faites un travail inutile ou que vous travaillez du côté Python, ce qui pourrait être fait du côté C. Dans votre exemple, vous faites un travail supplémentaire. vous auriez pu le faire avec une boucle au lieu de deux.
Doval
24
@Doval Malheureusement pas - en NumPy . Un ajout Python en boucle exécutant élément par élément peut facilement être plusieurs fois plus lent (!) Que l'opérateur NumPy vectorisé (non seulement écrit en C mais utilisant les instructions SSE et d'autres astuces) pour des tailles de tableau réalistes.
46
Certains des commentaires ci-dessus semblent mal comprendre la question. Lors de la programmation dans NumPy, vous obtiendrez de meilleurs résultats si vous pouvez vectoriser votre calcul , c'est-à-dire remplacer les boucles explicites en Python par des opérations de tableau complet dans NumPy. Ce concept est très différent de la programmation ordinaire en Python et prend du temps à apprendre. Je pense donc qu'il est raisonnable que le PO demande conseil pour savoir comment s'y prendre.
Gareth Rees
3
@PieterB: Oui, c'est vrai. La "vectorisation" n'est pas la même chose que "choisir le meilleur algorithme". Ce sont deux sources distinctes de difficultés pour mettre en œuvre des implémentations efficaces et il est donc préférable d’y réfléchir un à la fois.
Gareth Rees

Réponses:

89

Il s'agit d'une difficulté conceptuelle courante pour apprendre à utiliser NumPy efficacement. Normalement, le traitement des données en Python s’exprime mieux en termes d’ itérateurs , pour limiter l’utilisation de la mémoire, pour maximiser les possibilités de parallélisme avec le système d’E / S et pour permettre la réutilisation et la combinaison de parties d’algorithmes.

Mais NumPy renverse tout cela: la meilleure approche consiste à exprimer l'algorithme sous la forme d'une séquence d' opérations sur un tableau entier , afin de minimiser le temps passé dans l'interpréteur Python lent et d'optimiser le temps passé en routines NumPy compilées rapidement.

Voici l'approche générale que je prends:

  1. Conservez la version d'origine de la fonction (ce qui, vous en êtes sûr, est correcte) afin de pouvoir la tester par rapport aux versions améliorées, à la fois pour l'exactitude et la rapidité.

  2. Travaillez de l'intérieur: commencez par la boucle la plus intérieure et voyez si vous pouvez la vectoriser. puis, quand vous avez fait cela, sortez d’un niveau et continuez.

  3. Passez beaucoup de temps à lire la documentation NumPy . Il y a beaucoup de fonctions et d'opérations là-dedans et elles ne portent pas toujours un nom brillant. Il est donc intéressant de les connaître. En particulier, si vous pensez "si seulement il y avait une fonction qui faisait telle ou telle chose", alors ça vaut la peine de passer dix minutes à la chercher. C'est habituellement quelque part là-bas.

Il n'y a pas de substitut à la pratique, je vais donc vous donner quelques exemples de problèmes. Le but de chaque problème est de réécrire la fonction afin qu'elle soit entièrement vectorisée : autrement dit, elle consiste en une séquence d'opérations NumPy sur des tableaux entiers, sans boucles Python natives (no forou whileinstructions, pas d'itérateurs ou de compréhensions).

Problème 1

def sumproducts(x, y):
    """Return the sum of x[i] * y[j] for all pairs of indices i, j.

    >>> sumproducts(np.arange(3000), np.arange(3000))
    20236502250000

    """
    result = 0
    for i in range(len(x)):
        for j in range(len(y)):
            result += x[i] * y[j]
    return result

Problème 2

def countlower(x, y):
    """Return the number of pairs i, j such that x[i] < y[j].

    >>> countlower(np.arange(0, 200, 2), np.arange(40, 140))
    4500

    """
    result = 0
    for i in range(len(x)):
        for j in range(len(y)):
            if x[i] < y[j]:
                result += 1
    return result

Problème 3

def cleanup(x, missing=-1, value=0):
    """Return an array that's the same as x, except that where x ==
    missing, it has value instead.

    >>> cleanup(np.arange(-3, 3), value=10)
    ... # doctest: +NORMALIZE_WHITESPACE
    array([-3, -2, 10, 0, 1, 2])

    """
    result = []
    for i in range(len(x)):
        if x[i] == missing:
            result.append(value)
        else:
            result.append(x[i])
    return np.array(result)

Spoilers ci-dessous. Vous obtiendrez beaucoup de meilleurs résultats si vous essayez vous-même avant de regarder mes solutions!

Réponse 1

np.sum (x) * np.sum (y)

Réponse 2

np.sum (np.searchsorted (np.sort (x), y))

Réponse 3

np.where (x == manquant, valeur, x)

Gareth Rees
la source
Attendez, y a-t-il une faute de frappe dans la dernière réponse ou NumPy modifie-t-il la façon dont Python interprète le code?
Izkata
1
@Izkata Il ne modifie rien en soi, mais les opérations logiques appliquées aux tableaux sont définies pour renvoyer des tableaux booléens.
sapi
@sapi Ah, j'ai raté ce qui se passe dans les doctests, je pensais que c'était simplelist
Izkata
Peut-être qu'il devrait y avoir un moyen d'intégrer APL?
J'aime comment tu donnes des devoirs.
Koray Tugay
8

Pour accélérer les choses, vous devez lire vos structures de données et utiliser celles qui conviennent.

Pour les tailles non triviales de petits tableaux et de grands tableaux (disons petits = 100 éléments et grands = 10 000 éléments), une façon de le faire est de trier le petit tableau, puis de le parcourir sur un grand tableau et d'utiliser une recherche binaire pour trouver les éléments correspondants. dans le petit tableau.

Cela rendrait la complexité temporelle maximale, O (N log N) (et pour les petites et petites baies et les très grandes baies, il est plus proche de O (N)) où votre solution de boucle imbriquée est O (N ^ 2)

Pourtant. quelles structures de données sont les plus efficaces dépend fortement du problème réel.

Pieter B
la source
-3

Vous pouvez utiliser un dictionnaire pour optimiser les performances de manière significative

Ceci est un autre exemple:

locations = {}
for i in range(len(airports)):
    locations[airports["abb"][i][1:-1]] = (airports["height"][i], airports["width"][i])

for i in range(len(uniqueData)):
    h, w = locations[uniqueData["dept_apt"][i]]
    uniqueData["dept_apt_height"][i] = h
    uniqueData["dept_apt_width"][i] = w
Jakub Bares
la source
2
C’est tout à fait clairement en train d’utiliser l’école de pensée "à la boucle".
8bittree