Wie finde ich alle Rasterpunkte, die nicht reduzierte Fraktionen auf einem Quadrat entsprechen?Python

Python-Programme
Anonymous
 Wie finde ich alle Rasterpunkte, die nicht reduzierte Fraktionen auf einem Quadrat entsprechen?

Post by Anonymous »

Bei einer positiven Ganzzahl n können wir alle Gitterpunkte im Quadrat n x n bezeichnen. Beginnend bei 1, die Gesamtzahl der Gitterpunkte ist N x n und die Gitterpunkte sind Liste (Itertools.Product (Bereich (1, n + 1), Wiederholung = 2)) . Nicht reduzierte Fraktion ist Folgendes ist eine Bruteforce-Implementierung, die garantiert korrekt ist, aber sehr ineffizient ist: < /p>

Code: Select all

import math
from itertools import product

def find_complex_points(lim: int) -> list[tuple[int, int]]:
return [
(x, y)
for x, y in product(range(1, lim + 1), repeat=2)
if math.gcd(x, y) > 1
]
< /code>
Jetzt ist die nächste Funktion etwas schlauer, aber sie erzeugt Duplikate und als Ergebnis nur merklich schneller, aber nicht viel: < /p>
def find_complex_points_1(lim: int) -> set[tuple[int, int]]:
lim += 1
return {
(x, y)
for mult in range(2, lim)
for x, y in product(range(mult, lim, mult), repeat=2)
}
< /code>
In [255]: %timeit find_complex_points(1024)
233 ms ± 4.44 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [256]: %timeit find_complex_points_1(1024)
194 ms ± 1.9 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
< /code>
Is there a better way to accomplish this?
(My goal is simple, I want to create a NumPy 2D array of uint8 type with shape (N, N), fill it with 255, and make all pixels (x, y) 0 if (x+1)/(y+1) is a non-reduced fraction)

I have devised a method that is smarter than both my previous ones by a wide margin, and also tremendously faster, but it still generates duplicates, I have opt to not to use a set
hier, damit Sie den Code so kopieren können, wie es ist, und einige Tests ausführen und die genaue Ausgabe in der Reihenfolge sehen, die sie generiert werden:

Code: Select all

def find_complex_points_2(lim: int) -> set[tuple[int, int]]:
stack = dict.fromkeys(range(lim, 1, -1))
lim += 1
points = []
while stack:
x, _ = stack.popitem()
points.append((x, x))
mults = []
for y in range(x * 2, lim, x):
stack.pop(y, None)
mults.append(y)
points.extend([(x, y), (y, x)])

for i, x in enumerate(mults):
points.append((x, x))
for y in mults[i + 1:]:
points.extend([(x, y), (y, x)])

return points
< /code>
In [292]: sorted(set(find_complex_points_2(1024))) == find_complex_points(1024)
Out[292]: True

In [293]: %timeit find_complex_points_2(1024)
58.9 ms ± 580 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [294]: %timeit find_complex_points(1024)
226 ms ± 3.24 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
< /code>

To clarify, the output of find_complex_points_2(10)
ist:

Code: Select all

In [287]: find_complex_points_2(10)
Out[287]:
[(2, 2),
(2, 4),
(4, 2),
(2, 6),
(6, 2),
(2, 8),
(8, 2),
(2, 10),
(10, 2),
(4, 4),
(4, 6),
(6, 4),
(4, 8),
(8, 4),
(4, 10),
(10, 4),
(6, 6),
(6, 8),
(8, 6),
(6, 10),
(10, 6),
(8, 8),
(8, 10),
(10, 8),
(10, 10),
(3, 3),
(3, 6),
(6, 3),
(3, 9),
(9, 3),
(6, 6),
(6, 9),
(9, 6),
(9, 9),
(5, 5),
(5, 10),
(10, 5),
(10, 10),
(7, 7)]
< /code>
As you can see, (10, 10)
wird zweimal angezeigt. Ich möchte redundante Berechnungen vermeiden. Ersetzt durch die Summe aller Zahlen zuvor, so wird n durch (n
+ n) /2 ersetzt.

Code: Select all

import numpy as np
import numba as nb

@nb.njit(cache=True)
def resize_img(img: np.ndarray, h_scale: int, w_scale: int) -> np.ndarray:
height, width = img.shape
result = np.empty((height, h_scale, width, w_scale), np.uint8)
result[...] = img[:, None, :, None]
return result.reshape((height * h_scale, width * w_scale))

def find_composite_points(lim: int) -> set[tuple[int, int]]:
stack = dict.fromkeys(range(lim, 1, -1))
lim += 1
points = set()
while stack:
x, _ = stack.popitem()
points.add((x, x))
mults = []
for y in range(x * 2, lim, x):
stack.pop(y, None)
mults.append(y)
points.update([(x, y), (y, x)])

for i, x in enumerate(mults):
points.add((x, x))
for y in mults[i + 1 :]:
points.update([(x, y), (y, x)])

return points

def natural_sum(n: int) -> int:
return (n + 1) * n // 2

def composite_image(lim: int, scale: int) -> np.ndarray:
length = natural_sum(lim)
img = np.full((length, length), 255, dtype=np.uint8)
for x, y in find_composite_points(lim):
x1, y1 = natural_sum(x - 1), natural_sum(y - 1)
img[x1 : x1 + x, y1 : y1 + y] = 0

return resize_img(img, scale, scale)
< /code>
composite_image(12, 12)

Quick Reply

Change Text Case: 
   
  • Similar Topics
    Replies
    Views
    Last post