让我们从一些通用点开始。最好先编写易于您和同事理解的直观代码,然后测量性能并查找瓶颈。如果您试图从一开始就进行超级优化,则会出现以下问题:
- 编写复杂、容易出错且不易理解的代码。
- 很可能优化代码只会对整体性能产生微不足道的影响,同时忽略主要瓶颈。除非您对处理器、编译器、编程语言和环境细节了如指掌,否则如果尝试猜测优化方法,很可能会使性能变差。
最好进行测量,找到瓶颈,然后针对这些瓶颈提高性能。如果您怀疑算法/实现速度较慢,请对其进行分析。如果您想知道哪个算法/实现将表现最佳,请进行比赛。测试使用不同的数据集,因为对一个输入集(3,5)表现良好的算法/实现可能不适用于另一个输入集(3,500000000)。
话虽如此,让我们从您现有的内容开始,探索一些选项,最后为您描述的情况(即多个值)提供一个起始实现。请注意,其中一些实现可能不是您的情况的理想选择或适用于您的环境,但它们涉及到了一般性的方法。
现状(您现有的代码):
这段代码进行了一些条件和算术运算。这些是处理器在早餐前就能吞噬掉的操作……在纳米粒子眨眼间完成,即非常快。我知道您正在使用Arduino,所以没有最强大的处理器可供使用,但是这些操作处理器非常快。我想创建自己的基准测试,所以我在C ++中实现了一个与您的函数非常相似的函数(您在问题中提到C++可以使用)。我将测试称为“ConditionalTest”,因为它遵循一个“if...else”流程,并且我不擅长命名。
注意:虽然我对结果进行了一些基本测试,但是这些答案中提供的代码绝不是生产就绪的。它缺少基本参数检查(例如null值或未初始化变量),并且具有一些性能优化,我通常会省略这些优化而选择安全。无论如何,代码如下:
static void ConditionalTest( int startA, int startB, unsigned long long testIterations )
{
gl_result = 0;
gl_current=0;
int distToA = startA;
int distToB = startB;
for( unsigned long long i = 0; i < testIterations; i++ )
{
if( distToA > distToB ) //B comes first
{
gl_result = distToB;
gl_current += distToB;
distToA -= distToB;
distToB = startB;
}
else if( distToB > distToA ) //A comes first
{
gl_result = distToA;
gl_current += distToA;
distToB -= distToA;
distToA = startA;
}
else
{
gl_result = distToA;
gl_current += distToA; //Arbitrarily, could be distToB
distToA = startA;
distToB = startB;
}
}
}
注意: -
- 我将值分配给全局变量gl_result,而不是打印出来,以节省控制台输出信息的空间,同时由于屏幕输出操作与其他操作相比较慢,会使结果膨胀。
- 我必须使用unsigned long long来表示testIterations和一些其他变量,否则int类型会发生溢出。
- 在测试中,gl_是全局变量。
这个算法的优点是它使用非常基本的结构,因此:
- 即使对编程只有很基本的了解或来自其他编程语言的程序员也能快速理解它的功能。
- 这个算法非常可移植 - 它很容易翻译成其他语言和操作系统。
- 就性能而言,所见即所得——你看到的就是你得到的,因此不太可能隐藏在第三方库调用中的大性能瓶颈。
现在,我在一台相当强劲的机器上运行(即i7 2600),因此需要进行10亿次迭代才开始得到需要超过1秒的结果。在这种情况下,完成10亿次迭代平均需要2400毫秒。我认为这已经很快了,但让我们看看如何改进。首先,让我们看看什么可以调整。
改进您的实现
参数是(3,5),因此最初distA为3,distB为5。请注意,3小于5。第一个if将检查distToA > distToB:
然后为elif distToB > distToA:
。但是,distToB(最开始为5)比distToA(最开始为3)大的可能性要高两倍。出于性能方面的考虑,希望尽可能经常满足第一个if条件,以最小化每次迭代中要检查的条件数量。在这里,我对编译器做了一些假设,稍后再详细说明。
所以,我们可以非常简单地交换这些条件。但问题并不是那么简单。我发现的问题是编译器对第二个if和最后一个else进行了一些很好的优化。你看到的是“任意,也可能是distToB”这个注释吗?好吧,事实上,在else if中有“gl_current += distToA;”,而在else中也有“gl_current += distToA”,这使得编译器可以将其优化为一个语句。因此,在我的情况下它不是随意的(对于您来说,这取决于您的编译器)。因此,我们需要更改else以允许进行这些优化。最终的代码如下:
static void ConditionalTestV2( int startA, int startB, unsigned long long testIterations )
{
gl_result = 0;
gl_current=0;
int distToA = startA;
int distToB = startB;
for( unsigned long long i = 0; i < testIterations; i++ )
{
if( distToB > distToA )
{
gl_result = distToA;
gl_current += distToA;
distToB -= distToA;
distToA = startA;
}
else if( distToA > distToB )
{
gl_result = distToB;
gl_current += distToB;
distToA -= distToB;
distToB = startB;
}
else
{
gl_result = distToB;
gl_current += distToB;
distToA = startA;
distToB = startB;
}
}
}
注意:
if( distToB > distToA )
在
else if( distToA > distToB )
之前,现在else有了
gl_result = distToB
和
gl_current += distToB
。经过这些调整后,测试运行所花费的时间为:2108毫秒。很高兴这些简单的调整使执行时间减少了12%。
从中我们得到的最大教训是要测量您所做的任何更改是否会产生意外后果。
您的编译器和执行环境可能与我的不同,因此您的结果可能会有所不同。如果您要开始在这个级别上进行微调,请建议熟悉汇编语言,并在关键点上逐步执行汇编代码以确定实际上如何实现条件。我相信还有其他优化策略,例如可以采用类似于
__builtin_expect
这样的东西来指导编译器的分支选择。
您可能并不总是按顺序获取起始值,在这种情况下,您需要权衡一次性排序的成本与执行算法的整体时间之间的差异。
还有一些其他需要指出的事项:-
- 您维护一个变量
current
,但您没有使用它。如果您没有使用
current
,那么您可以将其删除。如果编译器已经对其进行了优化,则可能不会看到性能提升。
- 您有一个范围为100,但循环将每3 * 5 = 15次重复一次。因此,如果只需要15个结果,则可以在当前值为15时停止,或者可以存储结果,然后仅写出它们(请参见模式部分)。
取模
查看算法,我们总是获取到一个值的距离,因此一个想法就是采用取模的方法(已经有了一个答案来涵盖这一点)。我对性能有点怀疑,因为取模倾向于使用比减法操作更慢的除法。无论如何,这是我想到的:
static void ModuloTest( int startA, int startB, unsigned long long testIterations )
{
unsigned long long current = 0;
unsigned long long prev = 0;
int distToA = startA;
int distToB = startB;
for( long long i = 0; i < testIterations; i++ )
{
current += (gl_result = FastMin(distToA - (current%distToA), distToB - (current%distToB)));
}
}
结果为23349毫秒。比原来慢了近10倍。
通常情况下,我不会写出像current += (gl...
这样的代码,但我试图减少赋值语句的数量。这通常是一个愚蠢的做法,因为编译器会比我更好地进行优化,并且它也更容易出错。尽管如此,这个测试要慢得多,我想确保我给了它一个很好的机会。直接指责取模可能有点不公平,因为流程有点不同,所以可能还有其他原因。因此,我进行了一个更简单的取模测试:
static void PureModuloTest( unsigned long long testIterations, unsigned long long mod )
{
for(long long i = 1; i <= testIterations; i++)
{
gl_result = mod % i;
}
}
当 mod 为 50000 时,即使在这种情况下测试所花费的时间也比你的测试多了5倍,因此我认为如果我们正在寻求纯性能提升,那么模数是不适用的。我还发现了一些意想不到的STL min()的低效率,但是详细说明会让这篇长贴更长。
接下来我看了数据。有时候,如果你能找到数据中的特征/模式,就可以相应地优化实现。
模式
再次查看您的数据,突出显示的是差异将在每个a * b
周期重复。因此,在您的测试中,一旦达到15,距离就会重复。您可能已经意识到了这一点,但在您的代码片段中,您运行了100个周期的测试(for i in xrange(100)
),所以我不确定。
利用这个事实的一种方法是存储值,直到我们到达a * b
,然后仅重复使用这些值,直到完成。请注意,这本质上是使用您的算法,然后从那时起迭代通过列表。
static void PatternTest( int startA, int startB, unsigned long long testIterations )
else if( distToA > distToB )
else
val += gl_result;
resultList.push_back(gl_result);
count++;
}
std::list<int>::const_iterator iter;
while( count < testIterations )
}
}
这个测试耗时1711毫秒,比原始版本快了约29%,比当前最佳表现快了约18%。我不确定这在你的情况下是否适用,但这是分析预期数据如何提供一些良好性能收益的示例。
线程大爆发!现在,这可能不适用于您的情况,因为您正在使用Arduino。但也许将来会支持线程,或者您可以将问题分配给不同的处理器。无论哪种方式,都应该包括线程基准测试,因为这就是它们存在的目的。此外,我的计算机有8个核心,其中7个核心的时间都在闲逛,所以让它们有机会狂奔是很好的。
如果您的数据或算法可以分解为独立的离散部分,则可以设计程序使其在单独的线程上运行独立操作。现在我们知道序列每
a * b
个数就会重复一次。因此,我们可以从“(n模(a * b))== 0”的不同点开始。
但是,我们可以做得更好,先获取前
a * b
个值,然后在单独的线程上循环遍历这些值。这就是我在这里所做的。我选择运行4个线程。
struct BonanzaThreadInfo
{
long long iterations;
list<int> resultList;
int result;
};
static void BonanzaTestThread( void* param )
{
BonanzaThreadInfo* info = (BonanzaThreadInfo*)param;
std::list<int>::const_iterator iter;
for( long long count = 0; count < info->iterations; )
{
for( iter = info->resultList.begin(); iter != info->resultList.end() && count < info->iterations; iter++ )
{
info->result = *iter;
count++;
}
}
delete param;
}
static void ThreadBonanzaTest( int startA, int startB, unsigned long long testIterations )
{
int stop = startA * startB;
list<int> resultList;
int distToA = startA;
int distToB = startB;
int val = 0;
long long count = 0;
while( val < stop )
{
if( distToB > distToA )
{
gl_result = distToA;
distToB -= distToA;
distToA = startA;
}
else if( distToA > distToB )
{
gl_result = distToB;
distToA -= distToB;
distToB = startB;
}
else
{
gl_result = distToB;
distToA = startA;
distToB = startB;
}
val += gl_result;
resultList.push_back(gl_result);
count++;
}
long long threadIterations = (testIterations - count) / NUMTHREADS;
long long iterationsLeft = testIterations-count;
thread* bonanzaThreads = new thread[NUMTHREADS];
for( int i = 0; i < NUMTHREADS; i++ )
{
BonanzaThreadInfo* bonanzaThreadInfo = new BonanzaThreadInfo;
if( i == (NUMTHREADS - 1) )
{
bonanzaThreadInfo->iterations = iterationsLeft;
}
else
{
iterationsLeft -= threadIterations;
bonanzaThreadInfo->iterations = (threadIterations);
}
bonanzaThreadInfo->resultList = resultList;
bonanzaThreads[i] = thread(BonanzaTestThread,bonanzaThreadInfo);
}
for( int i = 0; i < NUMTHREADS; i++ )
{
bonanzaThreads[i].join();
}
delete [] bonanzaThreads;
}
结果是这花费了574毫秒,节省了整整76%!关于线程的一些基本要点:
- 复杂性和错误的几率大大增加。
- 如果在线程之间有任何共享资源,则该资源将需要由互斥量进行保护。如果线程经常需要同时访问同一受保护的资源,则所有需要该资源的线程都需要等待直到其可用,这可能会导致性能非常差。
这是我们目前为止的图表:
现在,关于多个值的编辑。
多个值
好吧,据我所见,如果您有多个输入值(a、b、c、d...),则您的if语句将变得非常嵌套并且很快就会变得很长。
if a < b && a < c && a < d...
我们通常试图对接下来的值进行排序,这就是我开始的地方。我的第一个想法是将值存储在某个有序数据结构中。我选择使用集合,因为集合自然按键(实际上它是一个multiset,因为我们需要允许重复项)。在集合内部,我放置了一个结构体(称为ValuesStruct,因为我非常不善于命名),其中包含要递增的值(a、b、c)以及此值将最接近的下一个整数。小于运算符是为了让stl知道将此值放在集合中的位置。
struct ValuesStruct
{
public:
int Value;
long long Next;
ValuesStruct( int start )
{
Value = start;
Next = start;
}
bool operator < (const ValuesStruct& rOther) const
{
return (Next < rOther.Next);
}
private:
ValuesStruct()
{
}
};
那么,我需要做的就是遍历这个集合。在每次迭代中,集合的开头将具有最小的下一个值。因此,我可以通过将前一个值从当前值中减去来计算当前间隔。然后,我只需要使用 do..while()
循环从列表中删除此值,并使用更新后的 Next 值将其添加回去,以便它将占据集合中适当的位置。我需要对所有具有此值作为 Next
的值进行这样的操作(例如,在您简单的 3,5 示例中的 15)。我将测试称为 MultiConditionalTest
,因为在这里我们需要检查多个比较条件,并且因为我在取名字方面非常糟糕。
static void MultiConditionalTest( multiset<ValuesStruct>& values, unsigned long long testIterations )
{
unsigned long long prev = 0;
for( unsigned long long i = 0; i < testIterations; i++ )
{
multiset<ValuesStruct>::iterator iter = values.begin();
gl_result = (*(iter)).Next - prev;
prev = (*(iter)).Next;
do
{
ValuesStruct valuesStruct = *iter;
values.erase(iter);
valuesStruct.Next += valuesStruct.Value;
values.insert( valuesStruct );
iter = values.begin();
}while( (*iter).Next == prev );
}
}
该函数的使用方法如下:
multiset<ValuesStruct> values;
values.insert(ValuesStruct(3));
values.insert(ValuesStruct(5));
values.insert(ValuesStruct(7));
values.insert(ValuesStruct(11));
MultiConditionalTest( values, testIterations );
正如您所看到的,这里有很多内容,因此我预计会有一些性能问题,并且确实存在:105156毫秒 - 大约慢了50倍。这仍然少于每次迭代的微秒数,因此这取决于您的目标是什么。由于我只是在今晚匆忙编写而没有进行太多分析,我相信可以进行性能优化。首先,集合通常实现为二叉搜索树。我会进行一些研究,确定这是否是解决此问题的最佳数据结构。此外,在将新值插入列表时,可以给出一个提示,指示其放置位置。如果我们聪明地选择位置,那么我们可能能够加快此操作的速度。同样,当我们达到(a * b * c * d ...)时,序列将重复,因此我们可以存储值,然后从那时起仅将它们写出来。我还会查看问题空间,并查看是否有一种优化算法的方法,可能要在math.stackexchange.com上询问数学序列 - 那些家伙非常聪明。
无论如何,这只是一种选择,它可能适用于您,也可能不适用于您,具体取决于您的实际性能要求。
其他想法:
- 您有多大可能获得相同的值集(a,b,c,d ...)?如果可能,您可能希望缓存先前的结果。然后,它只是从缓存的数组中读取它们,非常快速。
- 提高性能的另一种方法是打开编译器优化。如何做到这一点以及其有效性取决于您的编译器。
祝你好运。