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

Đang mở
#3,620 2 bình luận 6 reaction 0 người được giao Xem trên GitHub

Chưa có ai nhận issue này.

Đánh giá

Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức phù hợp với người mới
45/100
Loại issue
Lỗi
Độ rõ ràng
Khá rõ ràng
Mức độ hoạt động
Đình trệ
Công nghệ
python
Lĩnh vực
data-visualization, performance

Hướng nghiên cứu

Bắt đầu với packages/python/plotly/plotly/basedatatypes.py khoảng dòng 5310 và packages/python/plotly/_plotly_utils/basevalidators.py khoảng dòng 2553, sau đó chạy bản tái hiện lines.py được cung cấp. Kiểm tra cách các giá trị tăng lên qua các lần gọi add_shape() lặp lại. Hoàn tất khi việc vẽ nhiều đường không còn cho thấy thời gian trên mỗi đường tăng tuyến tính và hoàn thành trong vài mili giây như mong đợi.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

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.

Ngôn ngữ chính
Python
Star
18.8k
Fork
2.8k
Merge trung bình
16 giờ 26 phút
Pull request đã merge (30 ngày)
21

Hướng dẫn đóng góp

Mở hướng dẫn đóng góp

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của plotly/plotly.py

Tất cả issue của plotly/plotly.py

Issue tương tự

Thêm issue về Python

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.