python - 有没有更有效的方法可以从单个数字中找到最小的 Vector3 组合?
问题描述
我试图从一个数字中找到 vector3 的最小组合,到目前为止我有工作代码,但它真的效率不高。
为了演示,假设用户输入数字n,该函数应输出 3 个数字 ( x, y, z ) 与最小和的组合,同时仍能与原始数字n相乘。
因此,如果用户输入 100 作为 n,则 x、y 和 z 应该是 4、5 和 5。(或 (5, 5, 4); (5, 4, 5))。
我正在做 3 个 for 循环来计算 x、y 和 z 的单独值。它适用于小数字,但随着n的增加,它变得难以置信的计算量。我正在寻找任何可以更改计算方法的方法,以使计算速度更快。我对近似算法持开放态度,因为这不需要 100% 准确。
我最初是用 Lua 编写的,但问题与一种语言没有直接关系。
function CalculateVector(Size)
local Vectors = {}
local Lowest = math.huge
local Index = nil
for x = 0, Size, 1 do
for y = 0, Size, 1 do
for z = 0, Size, 1 do
if Size - (x * y * z) == 0 then
table.insert(Vectors, Vector3.new(x, y, z))
end
end
end
end
table.foreachi(Vectors, function(i, v)
local Combined = v.X + v.Y + v.Z
if Combined < Lowest then
Lowest = Combined
Index = i
end
end)
return Vectors[Index]
end
Python 中的相同代码,以防有人不知道 Lua 语法。
class Vector3:
def __init__(self, x, y, z):
self.X = x
self.Y = y
self.Z = z
def CalculateVector(Size):
Vectors = []
Lowest = Size + 3
Index = None
for x in range(Size):
for y in range(Size):
for z in range(Size):
if Size - (x * y * z) == 0:
Vectors.append(Vector3(x, y, z))
for i,v in enumerate(Vectors):
Combined = v.X + v.Y + v.Z
if Combined < Lowest:
Lowest = Combined
Index = i
return Vectors[Index]
解决方案
n
将其所有主要因子的每个拆分分解并测试为 3 组
function split_number_into_factors_having_min_sum(n, factors)
assert(n > 0 and factors > 0)
local primes = {}
local degrees = {}
local terms = {}
local p = 2
local step = {4, 1, 2, 0, 2}
local m = 0
while n > 1 do
if p * p > n then
p = n
end
if n % p == 0 then
local d = 0
repeat
d = d + 1
n = n / p
until n % p ~= 0
m = m + 1
primes[m] = p
degrees[m] = d
terms[m] = {}
end
p = p + step[p % 6]
end
local parts = {}
for j = 1, factors do
parts[j] = 1
end
local best_sum = math.huge
local best_parts = {}
local process_next_prime
local function split_in_terms(sum, qty, k)
if qty < factors then
local max_val = parts[qty] == parts[qty + 1] and sum > terms[k][qty] and terms[k][qty] or sum
qty = qty + 1
local min_val = qty == factors and sum or 0
for val = min_val, max_val do
terms[k][qty] = val
split_in_terms(sum - val, qty, k)
end
else
local p = primes[k]
for j = 1, factors do
parts[j] = parts[j] * p^terms[k][j]
end
process_next_prime(k)
for j = 1, factors do
parts[j] = parts[j] / p^terms[k][j]
end
end
end
function process_next_prime(k)
if k < m then
split_in_terms(degrees[k + 1], 0, k + 1)
else
local sum = 0
for j = 1, factors do
sum = sum + parts[j]
end
if sum < best_sum then
best_sum = sum
for j = 1, factors do
best_parts[j] = parts[j]
end
end
end
end
process_next_prime(0)
table.sort(best_parts)
return best_parts
end
用法:
local t = split_number_into_factors_having_min_sum(100, 3)
print(unpack(t)) --> 4 5 5
推荐阅读
- laravel - 查询关系以获取基于最大值的属性
- python - Run function in parallel
- java - RxJava equivalent of simple ThreadPoolExecutor example
- php - How to use parallel looping?
- r - 使用 plot.ts() 的时间序列的日期转换问题
- python - 如何使用特定字符串搜索数据框中的所有值
- rest - 需要帮助寻找生活成本相关数据的 api
- sql - FIND THE MINIMUM VALUE
- oauth-2.0 - How to disable device flow and implicit flow in identity server?
- scala - 在 Scala 中将 Map[String, String]() 附加到具有 [String] 类型的数组或列表中