Drawing lines / `add_shape()` is very slow, possible quadratic Schlemiel the Painter algorithm

Ouverte
#3,620 2 commentaires 6 réactions 0 personnes assignées Voir sur GitHub

Personne n'a encore pris cette issue.

Évaluation

Difficulté
4/5
Temps estimé
3-5 jours
Accessibilité débutants
45/100
Type d'issue
Bug
Clarté
Plutôt claire
Activité
À l'abandon
Stack technique
python
Domaine
data-visualization, performance

Piste de recherche

Commencez par packages/python/plotly/plotly/basedatatypes.py vers la ligne 5310 et packages/python/plotly/_plotly_utils/basevalidators.py vers la ligne 2553, puis exécutez la reproduction lines.py fournie. Vérifiez comment les valeurs augmentent au fil d’appels répétés à add_shape(). C’est terminé lorsque le tracé de nombreuses lignes ne présente plus un temps par ligne qui augmente linéairement et s’achève en quelques millisecondes, comme prévu.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

P2 performance

To reproduce: Create lines.py as follows:

import plotly.graph_objects as go
import plotly.express as px

import time
import random

N = [50, 100, 200, 400, 800]

def plot_random_lines(n):
    fig = go.Figure()
    for i in range(n):
        c = [random.random() for _ in [0, 1, 2, 3]]
        fig.add_shape(type='line', x0=c[0], y0=c[1], x1=c[2], y1=c[3])
    # We don't show the figure to avoid any possible influence from the
    # graphics driver.

def timings():
    t_cum = []
    for n in N:
        t0 = time.process_time_ns()
        plot_random_lines(n)
        t_cum.append((time.process_time_ns() - t0) / 1e6)

    t_per_line = [t/n for (t, n) in zip(t_cum, N)]

    fig1 = px.scatter(x=N, y=t_cum, labels={'x': 'Number of lines', 'y': 'Cumulative time [ms]'})
    fig1.show()
    fig2 = px.scatter(x=N, y=t_per_line, labels={'x': 'Number of lines', 'y': 'Time per line [ms]'})
    fig2.show()

timings()

Install plotly and run the above example.

  • Expected: Draws the lines in a few milliseconds
  • Actual: It takes more than half a minute on a modern MacBook

Notice that the time per line increases linearly with the number of lines drawn.

This looks like a classic example of a Schlemiel the painter algorithm, candidate for
Joel Spolsky's collection.

Observations

I suspect that the following code locations are related to the bug.

Langage dominant
Python
Étoiles
18.8k
Forks
2.8k
Merge moyen
16 h 26 min
PR mergées (30 j)
21

Guide de contribution

Ouvrir le guide de contribution

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de plotly/plotly.py

Toutes les issues de plotly/plotly.py

Issues similaires

Plus d'issues Python

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.