RedBlackPy - Série rapide et évolutive pour la recherche scientifique et quantitative en Python

Nous voulons présenter notre toute nouvelle bibliothèque open source RedBlackPy. Il est maintenant disponible pour Python 3.6+ sur MacOS et Linux (Windows prochainement).
Il est distribué sous licence Apache 2.0. Vous pouvez facilement l'installer via pip:

>>> pip installer redblackpy

Structure de l'article:

  • Points forts. Qu'est-ce que RedBlackPy?
  • Pourquoi des arbres rouge-noir? Explication simple de l'équilibrage des arbres rouge-noir.
  • Series et SeriesIterator. Caractéristiques, exemples de code et points de repère.

Points forts

RedBlackPy est une bibliothèque Python avec des structures de données basées sur des arbres rouge-noir. Dans un certain sens, il peut être considéré comme une bibliothèque supplémentaire pour les pandas. Les conteneurs Pandas visent un travail efficace avec des données statiques, c’est-à-dire qu’une fois chargés, vous n’ajoutez plus d’éléments et ne les supprimez pas à cause des coûts de calcul. RedBlackPy, au contraire, a été conçu pour un travail efficace avec des données dynamiques et ordonnées. Nous incluons des points de repère pour les opérations principales. L'autre avantage important de RedBlackPy est sa bonne évolutivité. La première version est présentée par deux classes: Series et SeriesIterator. Pour les utilisateurs de Cython, nous avons inclus les fichiers de définitions pxd pour ces classes.

Série est une structure de données de mappage permettant de conserver des données à 1 jour, qui:

  • Maintient les données en ordre, triées par clés.
  • Fournit des opérations rapides pour travailler avec des données dynamiques: insertion, suppression, obtenir élément par clé, définir élément par clé.
  • Fournit tous les types de données numériques de base avec un nombre de bits spécifique (type analogique de numpy): entiers non signés, entiers signés,
    points flottants. Vous pouvez certainement conserver tous les objets Python dans ce conteneur.
  • Fournit une interface utilisateur conviviale pour travailler avec des séries chronologiques ou des évaluations scientifiques: accès par n'importe quelle clé en utilisant une interpolation. L'interpolation est intégrée à l'opérateur getitem et n'utilise pas de mémoire supplémentaire. Opérations arithmétiques comme pour les vecteurs, décalage des données sur l'index.

SeriesIterator est un générateur d'itérateur permettant une itération efficace sur plusieurs objets Series. Par exemple, si un ensemble d’objets Series vous est attribué et que vous devez construire une union ordonnée de clés de ces séries, il vous suffit d’initialiser un SeriesIterator. Cet itérateur n'utilise pas de mémoire supplémentaire pour concaténer des clés, il génère la valeur suivante de l'union in-situ.

Dans notre équipe, nous utilisons ces structures de données pour traiter les problèmes de modélisation prédictive et pour les tâches d'analyse financière de séries chronologiques.

Pourquoi des arbres rouge-noir?

Figure 1. Exemple d'arbre rouge-noir de wikipedia.org. Les feuilles sont notées NIL.

L'arbre rouge-noir est une structure de données bien connue (par exemple, la mappe et le jeu C ++ STL sont basés sur des arbres rouge-noir). Il y a beaucoup d'informations sur les arbres rouge-noir, nous ne reviendrions donc pas sur tous les détails ici. Nous allons simplement présenter les idées principales du concept afin que le public non familiarisé avec cette structure ait l’idée de la logique d’auto-équilibrage. Nous supposons ici que notre lecteur est familiarisé avec les bases des arbres de recherche binaires. Les déclarations et les preuves de cette section ne sont pas nécessaires pour comprendre les sections suivantes.

Définition 1. L'arbre rouge-noir est un arbre de recherche binaire à auto-équilibrage qui remplit les conditions suivantes:

  1. Chaque nœud est rouge ou noir.
  2. La racine est noire.
  3. Toutes les feuilles sont noires.
  4. Si un nœud est rouge, ses deux enfants sont noirs.
  5. Chaque chemin simple, de la racine à l’un des nœuds feuilles (NIL sur la Figure 1), contient le même nombre de nœuds noirs.

Un auto-équilibrage signifie que les opérations d'insertion et de suppression incluent certaines modifications pour maintenir l'équilibre de l'arbre. Mais qu'est-ce qui signifie exactement qu'un arbre est équilibré?

Définition 2. Un arbre de recherche binaire est dit équilibré d'ordre 𝑛 si
la différence de longueur entre le chemin simple le plus long et le chemin le plus court (chaque chemin va de la racine aux feuilles) est égale à.

Peut-on colorier un arbre de recherche binaire en respectant les conditions de la définition 1? La proposition suivante donne la réponse à cette question.

Proposition 1. Soit T un arbre rouge-noir. Alors T est équilibré d'ordre m,
où m ≤ hauteur (T) / 2.
Preuve. Considérons un chemin simple arbitraire 𝜸 de longueur hauteur (T) dans T. Aussi, considérons un autre chemin simple de la racine au noeud de départ arbitraire. Selon les conditions 2–4 (Définition 1), un nombre minimal possible de nœuds noirs dans est égal à ⎡height (T) / 2⎤. Dans le même temps, le nombre maximum possible de nœuds noirs dans le chemin 𝜼 est égal à longueur (). Selon la condition 5, nous obtenons l'assertion requise. ︎

Nous savons maintenant que les longueurs de deux chemins simples allant de la racine aux feuilles des nœuds dans l’arbre rouge-noir ne diffèrent pas plus de deux fois. Comme la hauteur d'un arbre de recherche binaire définit la complexité d'une opération de recherche, la question suivante apparaît. Que pouvons-nous dire de la hauteur d'un arbre rouge-noir arbitraire?

Proposition 2. Soit T un arbre rouge-noir à n nœuds. Ensuite, ce qui suit est valable:
height (T) ≤ 2 log (n +1), où log est le logarithme binaire.
Preuve. Selon la proposition 1, tout chemin simple allant de la racine aux feuilles en T n'a pas une longueur inférieure à la hauteur (T) / 2. Par conséquent, n n’est pas inférieur au nombre de nœuds du premier niveau (T) / 2 niveaux (le premier niveau correspond à la racine, le deuxième aux enfants de la racine, etc.).
Ainsi, nous obtenons une limite inférieure évidente pour n et cela implique la déclaration suivante:

Selon la proposition 2, la recherche dans les arbres rouge-noir a une complexité logarithmique en taille. Il s'avère qu'il existe un algorithme efficace (complexité logarithmique) pour insérer ou supprimer un nœud. Cet algorithme inclut des modifications (appelées rotations) pour que l’arborescence reste conforme à la définition 1.

Notre choix de la structure de données centrale a été défini à l’origine par les problèmes rencontrés en recherche quantitative. Nous avions défini les objectifs à travers le prisme du traitement des séries financières, mais la solution résultante pouvait être appliquée à un tas d’autres problèmes de manière évidente. Par exemple, si vous travaillez avec des données de marché boursier, vous avez plusieurs séries chronologiques et leurs clés ne coïncident pas nécessairement. Mais nous savons que l'état du stock actuel (commandes actives) équivaut à l'état de la dernière modification (changement de prix). Cela signifie que nous devons traiter des signaux constants par morceaux et que nous arrivons naturellement à une interpolation au sol (voir la figure 2). De l'autre côté, si nous travaillons avec un carnet de commandes, par exemple, nous avons une structure qui change très fréquemment et il est donc nécessaire de réaliser rapidement les opérations d'insertion et de suppression. On pourrait définir brièvement les objectifs suivants:

  • Garder les données triées (pour interpolation)
  • Évolutivité pour traiter jusqu'à des millions d'articles
  • Opérations de modification rapide
  • Accès rapide aux articles, itération rapide
  • Des méthodes d'interpolation pratiques, optimisées et non contraintes, pour construire des valeurs in-situ. Nous incluons plusieurs interpolations: sol, plafond, linéaire, touches uniquement (voir documentation).
  • Convinient itérant sur plusieurs séries temporelles asynchrones
  • Opérations arithmétiques vectorielles

L'utilisation de tableaux et de tables de hachage en tant que structures de données de base est très coûteuse dans ce cas en raison de la réaffectation fréquente de la mémoire, de la redistribution, du décalage des données lorsque vous insérez ou supprimez un élément. Pour éviter ces effets, nous avons décidé d'utiliser des arbres binaires à auto-équilibrage.

Series et SeriesIterator

Remarque. Dans cette section, nous présentons quelques points de repère. Tous les tests ont été réalisés sur un MacBook Pro (Retina, 13 pouces, début 2015) Intel Core i5 à 2,7 GHz.

Considérons maintenant quelques cas d'utilisation simples et des points de repère pour les opérations principales. Nous aimerions mentionner que nous ne faisons pas concurrence à Pandas Series et qu'il ne serait pas correct de comparer RedBlackPy Series et Pandas Series en termes de concurrence, car leurs structures de données de base sont différentes. En présentant des résultats de référence, nous voudrions montrer que le choix judicieux d’une structure de données pour un problème spécifique est une étape importante du processus de R & D.

Interpolation

L'interpolation est intégrée à l'opérateur getitem. Vous pouvez initialiser Series avec le type d'interpolation spécifique, vous pouvez également le modifier après l'initialisation. L'interpolation ne crée pas de nouvel élément, elle utilise des voisins pour calculer une valeur en place (voir la figure 2). L'exemple de code ci-dessous montre comment fonctionne l'interpolation. :

La figure ci-dessous décrit schématiquement la logique d'interpolation. Supposons que nous ayons un signal discret avec 5 points. En effectuant une requête pour une valeur de clé, nous obtenons des résultats différents en fonction du type d'interpolation.

Figure 2. Exemples d'interpolation. Les données initiales sont présentées par un signal discret à 5 points.

SeriesIterator

La classe SeriesIterator fournit une itération efficace sur une union triée de clés de plusieurs objets Series. Cette classe est également basée sur le concept d’arbre rouge-noir. L'arbre rouge-noir est utilisé en tant que min-tas en cas d'itérateur direct et en tant que max-tas en cas d'itérateur inversé. Ce segment utilise k cellules de mémoire, où k est le nombre d'objets Series. La figure ci-dessous décrit schématiquement le travail de SeriesIterator.

Créons maintenant dix objets Series avec des données aléatoires et évaluons le temps d'exécution d'une boucle d'itération. Dans l'extrait de code ci-dessous, nous créons SeriesIterator à partir de la liste Series, chaque objet Series contient 100 000 éléments. Après l’initialisation, nous parcourons l’union triée des clés de ces objets Series en avant et en arrière.

Pour dix objets Series contenant chacun 100 000 éléments, les boucles aller et retour prenaient respectivement 0,95 seconde et 0,92 seconde. Ce temps a été obtenu sur MacBook Pro (Retina, 13 pouces, début 2015).

Points de repère des opérations de base

Nous fournirons des résultats de test pour quelques extraits de code simples afin de montrer la principale différence entre deux structures de données, en particulier entre Pandas.Series et RedBlackPy.Series.

Chaque fonction est testée sur des conteneurs de tailles suivantes: 10³, 10⁴, 10⁵, 10⁶.
Pour tracer les résultats, nous avons utilisé l’échelle logarithmique de l’axe des temps.

Comme nous pouvons le voir dans les résultats ci-dessous, RedBlackPy surpasse les Pandas dans les opérations d'insertion, de suppression et de recherche (get item). Par exemple, parcourir une liste d'un million de clés et appeler l'opérateur getitem prenait 11,8 secondes pour Pandas.Series et 2,7 secondes pour RedBlackPy.Series en cas de liste aléatoire de clés. Mais les Pandas surpassent RedBlackPy en itérant sur Series en raison de l’allocation continue de la mémoire. Pour les mêmes raisons, les opérateurs arithmétiques travaillent dans RedBlackPy plus lentement que dans les pandas. Les processeurs modernes prennent en charge les instructions de vecteurs (SSE, AVX) et l'utilisation de mémoire allouée alignée et continue permet d'optimiser les opérateurs arithmétiques des vecteurs.

Figure 3. Points de repère des séries RedBlackPy et Pandas

Si vous parcourez une liste de clés triée et appelez l’opérateur getitem, il est judicieux d’utiliser ce qu’on appelle le «mode d’utilisation» de RedBlackPy Series. Pour une série comportant plusieurs millions d'éléments, l'extrait de code ci-dessous a pris 0,5 seconde. Appelez simplement une méthode et obtenez une bonne accélération (dans ce cas environ 20 fois plus vite que les pandas).

Voici le référentiel open source RedBlackPy. Nous serons reconnaissants pour tout commentaire sur le projet. Je vous remercie!