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

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.

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)

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.

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