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

从 packages/python/plotly/plotly/basedatatypes.py 第 5310 行附近和 packages/python/plotly/_plotly_utils/basevalidators.py 第 2553 行附近开始，然后运行提供的 lines.py 复现程序。检查在重复调用 add_shape() 时值是如何增长的。当绘制许多线不再显示每条线耗时线性增加，并按预期在几毫秒内完成时，即表示完成。

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.

• In https://github.com/plotly/plotly.py/blob/master/packages/python/plotly/plotly/basedatatypes.py#L5310, curr_val increases in length with each call to add_shape().
• In https://github.com/plotly/plotly.py/blob/master/packages/python/plotly/_plotly_utils/basevalidators.py#L2553, v increases in length with each call.