Извлеките два ближайших числа, которые умножаются, чтобы получить заданное число
Я создал трассировщик лучей на базе процессора в PyGame, который использует плитку для каждого потока для рендеринга каждого раздела экрана. В настоящее время я разделяю экран между строками по вертикали, это не дает мне наилучшего распределения: я хочу разделить потоки на равные прямоугольники, охватывающие как направления X, так и Y. Например: если мое разрешение x = 640, y = 320 и у меня 4 потока, мне нужен список из 4 полей, представляющих границы тайлов в форме (x_min, y_min, x_max, y_max), в данном случае результатом будет [(0, 0, 320, 160), (320, 0, 640, 160), (0, 160, 320, 320), (320, 160, 640, 320)].
Проблема в том, что я не понимаю, как автоматически разделить количество потоков на двумерную сетку: я хочу извлечь два ближайших целых числа, которые умножаются, чтобы соответствовать настройке потока. Если это число нельзя разделить поровну, перейдите к ближайшему из них, которое может... например, никакие два целых числа не могут умножиться, чтобы получить 7, вместо этого используйте 6 или 8. Я пробовал math.sqrt, но это работает только для идеально делящихся чисел, например 16, даже при округлении оно не дает точных результатов для таких значений, как 32. Какое самое простое решение?
Примеры: 4 = 2 * 2, 6 = 2 * 3, 8 = 2 * 4, 9 = 3 * 3, 16 = 4 * 4, 24 = 4 * 6, 32 = 4 * 8, 64 = 8 * 8.
Ответы 3
Сначала вам нужно будет найти делители nThreads примерно так:
divisors = [i for i in range(2,floor(nThreads/2)+1) if nThreads%i==0]
В итоге вы получите список с увеличивающимися числами (я не разработчик Python, но для вас это не проблема).
Если его длина больше 2:
- если это странно, вы выбираете центральное значение, как в
16 -> [2,4,8]: в итоге вы получаете16=4*4. - если оно четное, вы выбираете два центральных значения, как в
24 -> [2,3,4,6,8,12]: в итоге вы получаете24=4*6.
в противном случае вы выбираете меньшее количество ниток.
Полный код может быть примерно таким:
from math import *
nThreads=16;
divisors = [i for i in range(2,floor(nThreads/2)+1) if nThreads%i==0]
print(divisors)
if len(divisors)%2 ==1 : # if odd
keptValues = [divisors[floor(len(divisors)/2)], divisors[floor(len(divisors)/2)]]
else: # if even
keptValues = [divisors[floor(len(divisors)/2)-1], divisors[floor(len(divisors)/2)]]
print(keptValues)
ПРИМЕЧАНИЕ. Опять же, код может не соответствовать лучшим практикам Python, поэтому не стесняйтесь редактировать :)
Ну, это правильно, но это можно выполнить один раз вначале и сохранить. А про производительность никто ничего не сказал :)
Спасибо, могу подтвердить, что это работает так, как задумано. Действительно, производительность не является проблемой, поскольку этот сегмент должен запускаться только один раз при запуске, к счастью, мне не нужно выполнять его для каждого кадра.
Если я вас правильно понял, вы ищете следующее:
Учитывая число x > 0, найдите пару факторов (z, h), у которых абсолютная разница (z, h) равна минимуму.
x — это количество доступных потоков, а (z, h) — это количество мозаик, которые у вас будут (vertically, horizontally).
Если количество пикселей не делится идеально на количество мозаик, вы можете добавить остаток к последней мозаике.
Самый эффективный алгоритм, который я могу придумать, выглядит следующим образом:
- начните с x, числа, которое мы хотим факторизовать.
- вычислите sqrt(x) и округлите его до ближайшего целого числа. Назовите это с.
- меньший делитель, который мы ищем, будет наибольшим делителем x, который меньше или равен s.
В коде Python это будет выглядеть примерно так:
import math
def closest_factors(x):
s = int(math.sqrt(x))
for z in range(s, 0, -1):
if x % z == 0:
return z, x // z
x = 60
factor1, factor2 = closest_factors(x)
print(f"The factors of {x} with the least difference are: {factor1} and {factor2}")
print(f"Their difference is: {abs(factor1 - factor2)}")
Возможно, для этого существует математическая формула, ускоряющая этот процесс, но я с ней не знаком.
Обновлено по предложению @MirceaKitsune в комментариях.
Спасибо, работает отлично и так, как задумано! Мне нравится, что, если число не делится, оно все равно даст вам x = 1, y = num без изменения счета, что гарантирует, что число не нужно будет изменять, и в конечном итоге все будет работать.
Заметил, что проверка def f(y): return x // y - y, похоже, не нужна: кажется, что и без нее все работает идеально. Есть ли причина, которую я пропустил? Просто решил перепроверить, чтобы быть в большей безопасности.
См. en.wikipedia.org/wiki/Fermat%27s_factorization_method, чтобы узнать о математическом трюке, который может ускорить этот процесс. Хотя с числами в десятки тысяч O(sqrt(x)) вполне нормально.
@MirceaKitsune вы правы, в этой части нет необходимости, поскольку число никогда не станет отрицательным (самое позднее любое число, разделенное на единицу минус один, будет равно нулю, и второе условное выражение также будет истинным). Я не внимательно просмотрел код. Буду обновлять!
Моя последняя функция адаптирована из решения пользователя 1984 и для простоты сокращена до нескольких строк: протестировано с несколькими значениями и всегда работает так, как задумано. В качестве бонуса, если unit не делится, он вернет unit, 1, поэтому сетка будет работать независимо от количества.
def grid(unit: int):
for i in range(math.isqrt(unit), 0, -1):
if not unit % i:
return unit // i, i
Вместо math.isqrt(unit) можно использовать math.trunc(math.sqrt(unit)).
Спасибо за упоминание этой части, отредактировал и исправил ее в своем коде.
Проверять все числа на предмет того, являются ли они делителями, для не малых чисел достаточно затратно.