0
\$\begingroup\$

This is a Python script I wrote to generate generalized Ulam spirals.

I call the spirals generated by my code Ulamish spirals, they are one dimensional polylines that cross all two dimensional lattice points (points where both coordinates are integers), and they grow in a counterclockwise spiral manner. And my code can generate a single spiral, two spirals that don't cross each other, and four spirals:

enter image description here

In a single spiral, the spiral starts at the origin and goes right first, then turns up, left and down, and repeat. After every two turns the length until the next turn increments by one. The spiral is composed entirely of segments and right angles, the segments are always parallel to one of the axes. I know there can be a one-to-one mapping between natural numbers and lattice points, so I numbered the lattices as such.

enter image description here

In a pair of spirals, the spirals both start at the origin, and together they cross all lattice points, while each cross exactly half of the infinite lattice points (which is still the same amount of infinity, of course), and they never intersect with each other.

The growth of the spirals is similar to the first one, one of the spirals is rotated, and every two turns the length grows by two.

I know the number of integers is equal to the number of natural numbers, and I created the second variation to map all integers to all lattices, because in the first variation I can't do so.

enter image description here

Four spirals are the maximum I can come up with that together cross all lattice points and don't intersect with each other. They are like the two spirals variation, one spiral has three rotated copies, and the spirals' length grows by two after every turn.

I wanted to label the lattice points with unique numbers, so I chose real integers and integers with only imaginary parts (lattices on the imaginary axis), again, they have the same number of elements as the lattices.

I used infinite iterators to generate the points, and I did all these without using a single if condition, my code is very efficient, though not the most efficient as shown here.

But I have implemented two generalizations that weren't covered by the answer.

Below is my code:

import matplotlib.pyplot as plt
from itertools import cycle, islice, repeat
from PIL import Image
from typing import Generator, List, Tuple


def step_x(x: int, y: int, sign: int, length: int) -> Tuple[zip, int]:
    return zip(range(x + sign, (end := x + sign * length) + sign, sign), repeat(y)), end


def step_y(x: int, y: int, sign: int, length: int) -> Tuple[zip, int]:
    return zip(repeat(x), range(y + sign, (end := y + sign * length) + sign, sign)), end


def ulamish_spiral_gen() -> Generator:
    x = y = length = 0
    yield 0, 0
    sign = cycle([1, 1, -1, -1])
    while True:
        length += 1
        arm, x = step_x(x, y, next(sign), length)
        yield from arm
        arm, y = step_y(x, y, next(sign), length)
        yield from arm


def gather(generator: Generator, n: int) -> List[Tuple[int]]:
    return list(islice(generator, n))


def ulamish_spiral(n: int) -> List[Tuple[int]]:
    return gather(ulamish_spiral_gen(), n)


def ulamish_spiral_2_gen(x: int, y: int, sign: int) -> Generator:
    length = 1
    yield 0, 0
    yield x, y
    while True:
        arm, y = step_y(x, y, next(sign), length)
        yield from arm
        length += 2
        arm, x = step_x(x, y, next(sign), length)
        yield from arm


def ulamish_spiral_2(n: int) -> List[List[Tuple[int]]]:
    return gather(ulamish_spiral_2_gen(1, 0, cycle([1, -1, -1, 1])), n), gather(
        ulamish_spiral_2_gen(-1, 0, cycle([-1, 1, 1, -1])), n
    )


def get_steps(quad: List[int]) -> cycle:
    return cycle([[step_x, step_y][q] for q in quad])


def ulamish_spiral_4_gen(x: int, y: int, sign: cycle, order: List[int]) -> Generator:
    steps = get_steps(order)
    order = cycle(order)
    stack = [x, y]
    length = 2
    yield 0, 0
    yield x, y
    while True:
        arm, stack[next(order)] = next(steps)(*stack, next(sign), length)
        yield from arm
        length += 2


def ulamish_spiral_4(n: int) -> List[List[Tuple[int]]]:
    return [
        gather(ulamish_spiral_4_gen(x, y, cycle(sign), order), n)
        for x, y, sign, order in (
            (1, 0, [1, -1, -1, 1], [1, 0, 1, 0]),
            (-1, 0, [-1, 1, 1, -1], [1, 0, 1, 0]),
            (0, 1, [-1, -1, 1, 1], [0, 1, 0, 1]),
            (0, -1, [1, 1, -1, -1], [0, 1, 0, 1]),
        )
    ]


def get_figure(length: int, x: List[int], y: List[int]) -> Tuple[plt.Axes, plt.Figure]:
    length /= 100
    fig, ax = plt.subplots(figsize=(length, length), dpi=100, facecolor="black")
    ax.set_axis_off()
    fig.subplots_adjust(0, 0, 1, 1, 0, 0)
    plt.axis("scaled")
    ax.axis([x[0], x[1], y[0], y[1]])
    return ax, fig


def get_data(n: int, level: int) -> List[List[Tuple[int]]]:
    return [ulamish_spiral, ulamish_spiral_2, ulamish_spiral_4][level](n)


def process_level_1_data(
    data: List[Tuple[int]], length: int
) -> Tuple[Tuple[List[int]], plt.Axes, plt.Figure]:
    xs, ys = zip(*data)
    ax, fig = get_figure(length, [min(xs) - 1, max(xs) + 1], [min(ys) - 1, max(ys) + 1])
    return [(xs, ys)], ax, fig


def process_data(data: List[List[Tuple[int]]], length: int):
    xmin = ymin = 1e309
    xmax = ymax = -1e309
    coords = []
    for spiral in data:
        xs, ys = zip(*spiral)
        xmin = min(min(xs), xmin)
        ymin = min(min(ys), ymin)
        xmax = max(max(xs), xmax)
        ymax = max(max(ys), ymax)
        coords.append((xs, ys))
    ax, fig = get_figure(length, [xmin - 1, xmax + 1], [ymin - 1, ymax + 1])
    return coords, ax, fig


def get_label(n: int, vert: bool, sign: int) -> List[str]:
    return [f'{i}{"i"*vert}' for i in range(0, n * sign, sign)]


def get_image(fig: plt.Figure) -> Image:
    fig.canvas.draw()
    image = Image.frombytes(
        "RGB", fig.canvas.get_width_height(), fig.canvas.tostring_rgb()
    )
    plt.close(fig)
    return image


def plot_spiral(n: int, level: int, length: int = 1080) -> Image:
    data = get_data(n, level)
    if not level:
        coords, ax, fig = process_level_1_data(data, length)
    else:
        coords, ax, fig = process_data(data, length)
    for (xs, ys), labels in zip(
        coords,
        (
            get_label(n, 0, 1),
            get_label(n, 0, -1),
            get_label(n, 1, 1),
            get_label(n, 1, -1),
        ),
    ):
        ax.plot(xs, ys, "o-", color="cyan", lw=2)
        for x, y, label in zip(xs, ys, labels):
            ax.annotate(label, (x, y), color="white", fontsize=16)
    return get_image(fig)

How can I make it more efficient?


Update

I have considered using mathematics myself, I tried to derive a quadratic equation for it myself, but of course the shape isn't a parabola.

I thought maybe the lengths of the segments are quadratic, but the curve doesn't agree with the series of lengths fully (0, 1, 1, 2, 2, 3, 3, 4, 4...), I tried to use a software to find a curve of best fit with n terms, but no matter how many terms I throw at it, the curve is always off. Surprisingly you can't write a simple equation for the above series.

Then I came across this answer on Mathematics Stack Exchange, and to find the coordinate of a given number you have four different equations, all of them quadratic, and the conditions for which equation to use are also quadratic, and contains a term that has to be calculated using square root and if conditions...

And the computational cost for a single term is much more expensive than just a single increment. Sure, it would be faster if I were to find the coordinate for large n, I don't need to calculate all the previous coordinates, but to get all coordinates before n, the method simply is very inefficient.

\$\endgroup\$
0

2 Answers 2

1
\$\begingroup\$

Speed

As in the SO question/answer, you can trivially speed them up by combining the segments with chain.from_iterable instead of your generator. Your original:

def ulamish_spiral_gen_Original() -> Generator:
    x = y = length = 0
    yield 0, 0
    sign = cycle([1, 1, -1, -1])
    while True:
        length += 1
        arm, x = step_x(x, y, next(sign), length)
        yield from arm
        arm, y = step_y(x, y, next(sign), length)
        yield from arm

My way:

def ulamish_spiral_gen_Kelly() -> Generator:
    def segments():
        x = y = length = 0
        yield (0, 0),
        sign = cycle([1, 1, -1, -1])
        while True:
            length += 1
            arm, x = step_x(x, y, next(sign), length)
            yield arm
            arm, y = step_y(x, y, next(sign), length)
            yield arm
    return chain.from_iterable(segments())

I also use a generator, but it only yields the segments. Your generator instead has every single coordinate passed through it.

Benchmark results for ulamish_spiral(16384) (Attempt This Online!):

  1.26 ± 0.00 ms  ulamish_spiral_gen_Kelly
  1.63 ± 0.00 ms  ulamish_spiral_gen_Original

Python: 3.11.4 (main, Jun 24 2023, 10:18:04) [GCC 13.1.1 20230429]

Type hints

Also, you wrote lots of type hints but apparently didn't get them checked. For example, ulamish_spiral_2_gen has parameter sign: int but you use a cycle iterator as argument instead of an int. And there are more issues. Do use Mypy or so to actually get your type hints checked and fix the issues.

\$\endgroup\$
0
\$\begingroup\$

I strongly suspect you can get better performance by calculating the coordinates of each point algebraically, instead of relying on a stateful generator. Abstractly speaking, math tends to be fast and iteration tends to be slow. More specifically, you would be able to express the coordinate calculation in a math&array-oriented DSL (numpy obviously, if you're sticking with python). Try to use branchless-style (which isn't quite the same thing as "no ifs, but close). Then you can just ask numpy for the specific points you want, and it'll do a decent amount of parallelization for you.

Edit: uuuuuuuug i don't actually like python or numpy!

Thank you Kelly for providing some benchmarking code to work with. I've adapted it a little to fit non-generator-based solutions, and found some interesting stuff:

  • Simply converting to a stateless algebraic list comprehension doesn't improve performance, in fact for the ranges I bothered testing it was much worse.
  • Numpy is faster (and could probably be optimized further by someone who knew its guts better than I), except that at some point you'll probably want to get your values out of numpy. Converting from numpy array to list takes much longer than the calculation itself! So depending what you need all these values for, numpy may offer a substantial gain, or it might be a hinderance, or optimization of the calculation may be moot because subsequent rendering/saving/analysis will take most of the time no matter what.

This code is not slick, but I think it gets the point across. The pure-numpy version returns a numpy array, there's another version that includes the conversion back to list-of-tuples. Note the use of np.int32, I didn't experiment with that much beyond checking correctness up to 1,000,000.

For 0-16384:

  0.43 ± 0.00 ms  numpy_pure
  0.85 ± 0.01 ms  kelly
  1.09 ± 0.01 ms  original
 12.27 ± 0.06 ms  numpy_based
 27.64 ± 0.10 ms  math_loop
Python: 3.8.10 (default, May 26 2023, 14:05:08)

for 0-1,000,000:

 58.27 ± 0.21 ms  numpy_pure
 86.07 ± 0.16 ms  kelly
103.63 ± 0.58 ms  original

The code used for these tests:

from math import isqrt
from timeit import timeit
from statistics import mean, stdev
import sys
from itertools import cycle, islice, repeat, chain
from typing import Iterable, List, Tuple
import numpy as np


def step_x(x: int, y: int, sign: int, length: int) -> Tuple[zip, int]:
    return zip(range(x + sign, (end := x + sign * length) + sign, sign), repeat(y)), end


def step_y(x: int, y: int, sign: int, length: int) -> Tuple[zip, int]:
    return zip(repeat(x), range(y + sign, (end := y + sign * length) + sign, sign)), end


def ulamish_spiral_gen_Original() -> Iterable:
    x = y = length = 0
    yield 0, 0
    sign = cycle([1, 1, -1, -1])
    while True:
        length += 1
        arm, x = step_x(x, y, next(sign), length)
        yield from arm
        arm, y = step_y(x, y, next(sign), length)
        yield from arm


def ulamish_spiral_gen_Kelly() -> Iterable:
    def segments():
        x = y = length = 0
        yield (0, 0),
        sign = cycle([1, 1, -1, -1])
        while True:
            length += 1
            arm, x = step_x(x, y, next(sign), length)
            yield arm
            arm, y = step_y(x, y, next(sign), length)
            yield arm
    return chain.from_iterable(segments())


def gather(generator: Iterable, n: int) -> List[Tuple[int]]:
    return list(islice(generator, n))


def numpy_core(n):
    m = np.sqrt(n).astype(np.int32)
    k_branch = np.logical_or(m % 2,
                             n >= (m * (m + 1)))
    m2 = m // 2
    k = (k_branch * m2) + (np.logical_not(k_branch) * (m2 - 1))
    k2 = 2 * k
    threshold1 = (k2 + 1) ** 2
    threshold2 = 2 * (k + 1) * (k2 + 1)
    threshold3 = 4 * ((k + 1) ** 2)
    branch1 = n <= threshold1
    branch2 = np.logical_and(threshold1   <  n,
                             n <= threshold2)
    branch3 = np.logical_and(threshold2 < n,
                             n <= threshold3)
    branch4 = threshold3 < n
    ksq = k ** 2
    x = (     branch1 * (n - (4 * ksq) - (3 * k))
        ) + ( branch2 * (k + 1)
        ) + ( branch3 * ((4 * ksq) + (7 * k) + 3 - n)
        ) + ( branch4 * (- k - 1)
        )
    y = (     branch1 * (- k)
        ) + ( branch2 * (- (4 * ksq) - (5 * k) - 1 + n)
        ) + ( branch3 * (+ k + 1)
        ) + ( branch4 * (- n + (4 * ksq) + (9 * k) + 5)
        )
    return np.array((x, y)).T

def numpy_pure(n: int, start_at=0):
    requested_ns = np.arange(start_at, n, dtype=np.int32)  # Could use bigger if we want...
    return numpy_core(requested_ns)

def numpy_based(n: int, start_at=0):
    requested_ns = np.arange(start_at, n, dtype=np.int32)  # Could use bigger if we want...
    return list(map(tuple, numpy_core(requested_ns)))

def math_loop(ns):
    def gen(n):
        m = isqrt(n)
        k_branch = m % 2 or n >= (m * (m + 1))
        m2 = m // 2
        k = (k_branch * m2) + ((not k_branch) * (m2 - 1))
        k2 = 2 * k
        threshold1 = (k2 + 1) ** 2
        threshold2 = 2 * (k + 1) * (k2 + 1)
        threshold3 = 4 * ((k + 1) ** 2)
        branch1 = n <= threshold1
        branch2 = threshold1   <  n and   n <= threshold2
        branch3 = threshold2 < n and   n <= threshold3
        branch4 = threshold3 < n
        ksq = k ** 2
        x = (     branch1 * (n - (4 * ksq) - (3 * k))
            ) + ( branch2 * (k + 1)
            ) + ( branch3 * ((4 * ksq) + (7 * k) + 3 - n)
            ) + ( branch4 * (- k - 1)
            )
        y = (     branch1 * (- k)
            ) + ( branch2 * (- (4 * ksq) - (5 * k) - 1 + n)
            ) + ( branch3 * (+ k + 1)
            ) + ( branch4 * (- n + (4 * ksq) + (9 * k) + 5)
            )
        return (x, y)
    return [gen(n) for n in range(0, ns)]

def kelly(n):
    return gather(ulamish_spiral_gen_Kelly(), n)

def original(n):
    return gather(ulamish_spiral_gen_Original(), n)

funcs = (
        original,
        kelly,
        #numpy_based,
        numpy_pure,
        #math_loop
        )

def correctness(n=16384):
    expect = funcs[0](n)
    for f in funcs[1:]:
        result = f(n)
        assert list(map(tuple, result)) == expect

def speed(n=16384, trials=1000):
    times = {f: [] for f in funcs}
    def stats(f):
        ts = [t * 1e3 for t in sorted(times[f])[:10]]
        return f'{mean(ts):6.2f} ± {stdev(ts):4.2f} ms '
    for _ in range(trials):
        for f in funcs:
            t = timeit(lambda: f(n), number=1)
            times[f].append(t)
    for f in sorted(funcs, key=stats):
        print(stats(f), f.__name__)
    print('\nPython:', sys.version)

if __name__ == "__main__":
    correctness(1000 * 1000)
    speed(n=1000*1000, trials=100)
\$\endgroup\$
3
  • \$\begingroup\$ I strongly doubt that. Their stateful generator doesn't do much work, it just coordinates the actual work, which is actually done by zip/range/repeat. (Except they pass every coordinate through their generator, but that is easily fixed (as I showed) and doesn't have a huge impact). Please show your way and benchmark results. \$\endgroup\$ Jul 24, 2023 at 21:32
  • \$\begingroup\$ @KellyBundy; done. There's a case to be made that it's cheating to not return a list per-se; I tried to get the generators to pipe into np.arrays for apples-to-apples, but I gave up. \$\endgroup\$ Jul 27, 2023 at 2:39
  • \$\begingroup\$ NumPy arrays are more efficient containers than Python lists. They take up less space and can be manipulated more efficiently. There's no reason not to use them. \$\endgroup\$ Jul 27, 2023 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.