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

Aberta
#3,620 2 comentários 6 reações 0 responsáveis Ver no GitHub

Ninguém assumiu esta issue ainda.

Avaliação

Dificuldade
4/5
Tempo estimado
3-5 dias
Facilidade para iniciantes
45/100
Tipo de issue
Bug
Clareza
Razoavelmente clara
Status de atividade
Estagnada
Stack de tecnologia
python
Domínio
data-visualization, performance

Direção de pesquisa

Comece por packages/python/plotly/plotly/basedatatypes.py por volta da linha 5310 e packages/python/plotly/_plotly_utils/basevalidators.py por volta da linha 2553; em seguida, execute a reprodução lines.py fornecida. Verifique como os valores crescem ao longo de chamadas repetidas a add_shape(). Está concluído quando desenhar muitas linhas não apresentar mais um tempo por linha que aumente linearmente e for concluído em milissegundos, como esperado.

Escrita pelo modelo de indexação a partir do texto da issue.

Descrição

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.

Linguagem predominante
Python
Estrelas
18.8k
Forks
2.8k
Merge médio
16h 26min
PRs com merge (30d)
21

Guia de contribuição

Abrir o guia de contribuição

Primeiros passos

  1. Leia a issue inteira e depois o guia de contribuição do projeto.
  2. Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
  3. Faça um fork do repositório e trabalhe em uma branch.
  4. Abra um pull request que referencie o número da issue.

Mais de plotly/plotly.py

Todas as issues de plotly/plotly.py

Issues semelhantes

Mais issues de Python

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.