给定数学表达式的裁缝更快的算法 [英] Faster Algorithm to Tailor Given Mathematical Expression

问题描述

是否有更优化的解决方案来解决上述问题?

Is there a more optimized solution to solve the stated problem?

给定一个由'N'个元素组成的数组'arr'和一个数字'M'，找到满足方程的最小索引'z'. []被视为floor().

Given an array 'arr' of 'N' elements and a number 'M', find the least index 'z' at which the equation gets satisfied. [ ] is considered as floor().

代码:

counts=0
ans=0
while(ans==0):
    s=0
    for i in range(counts,len(arr)):
        s+=int(arr[i]/(i+1-counts))
        if(s>M):
            break
    if((i+1)==len(arr) and s<=M):
        print(counts)
        ans=1
    counts+=1

说明:

1. 从左到右检查数组.满足条件的第一个指标就是答案.这比从右到左考虑的要优化.

1. Check array from left to right. The first index that satisfies the condition is the answer. This is more optimized than considering from right to left.

如果在计算过程中的任何时候，"s"被认为大于M，请打破循环并考虑下一个.这比完全计算's'更为优化.

If at any time during the calculation, 's' is deemed more than M, break the loop and consider the next. This is more optimized than calculating 's' completely.

示例:

输入:

N = 3 M = 3

N=3 M=3

arr = [1 2 3]

arr=[1 2 3]

输出:

0

这将使答案为0，因为第0个索引包含满足给定关系的第一个元素.

This would give the answer 0 since the 0th index contains the first element to satisfy the given relation.

谢谢.

推荐答案

如果使用相对较小的数组，则算法将足够快.通过稍微重新组织代码，可以实现较小的改进，但是没有什么大的变化.

If you're working with relatively small arrays, your algorithm is going to be fast enough. Minor improvements could be achieved by reorganizing the code a bit but nothing dramatic.

如果您正在处理非常大的数组，那么我建议您研究numpy.它针对阵列范围的操作进行了优化，并具有令人印象深刻的性能.

If you're working with very large arrays, then I would suggest you look into numpy. It is optimized for array wide operations and has impressive performance.

例如，您可以在一个操作中将数组中的所有元素按其倒置位置进行划分:

For example, you can divide all the elements in an array by their inverted position in one operation:

terms = arr / np.arange(len(arr),0,-1)

然后在一行中获取累积总和和第一个索引

and then get cumulative sums and the first index in a single line

index = np.where(np.cumsum(terms) <= M)

这篇关于给定数学表达式的裁缝更快的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！