计算两个不同数的倍数之差

Question

这是一个算法问题。为了简单起见，假设我有两个双倍数，A和B，我想构造一个函数，这个函数将给出A的下一个倍数或B的下一个倍数，如果有意义的话。在

例如，假设A是3，B是5。在

考虑倍数：（3,6,9,12,15）和（5,10,15）。在

我希望函数输出： （3，2，1，3，1，2，3），因为需要3个单位才能达到3个单位，然后2个单位才能达到5个单位，然后1到6个单位，然后3个单位到9个单位，等等。。。在

我希望这有道理。理想的是Python风格发生器（虽然我在ARDIONI~C++中写这个）。我需要它快点-真的很快。在

任何帮助都将不胜感激。我的伪代码在下面，但不是很好。在

a = 3
b = 5

current = 0
distToA = a
distToB = b
for i in xrange(100):
  if distToA > distToB: #B comes first
    print "Adding {0}".format(distToB)
    current += distToB
    distToA -= distToBb
    distToB = b
  elif distToB > distToA: #A comes first
    print "Adding {0}".format(distToA)
    current += distToA
    distToB -= distToA
    distToA = a
  else: #Equal
    print "Adding {0}".format(distToA)
    current += distToA #Arbitrarily, could be distToB
    distToA = a
    distToB = b

编辑：如果有多个值，它会是什么样子？不仅仅是a和b，还有c、d、e等。。 我想我会做更多的if语句，但是成本更高（每个分支的操作更多）。在

Answer 1

让我们从一些基本点开始。最好从直观的代码开始，这样你和你的同事就会理解它。然后测量性能并找出瓶颈。如果您从一开始就尝试超优化，您将：

• 使代码变得复杂、容易出错且不易理解。在
• 最有可能的是优化代码，使其在总体性能上几乎没有任何变化，同时忽略了主要的瓶颈。除非您对处理器、编译器、编程语言和环境的细微差别了如指掌，否则，如果您试图猜测优化，很有可能会使性能更差。在

最好是度量、发现瓶颈，然后针对这些瓶颈改进性能。如果您怀疑某个算法/实现速度慢，请分析它。如果您想知道哪种算法/实现的性能最好，那么就对它们进行竞争。使用不同的数据集进行测试，因为对于一组输入（3,5）性能良好的内容可能对另一组输入（350000000）性能不佳。在

话虽如此，让我们从你所拥有的开始，探索一些选项，然后最终为你在编辑中描述的案例提供一个起始实现，即多个值。请注意，这些实现中的一些可能并不适合您的情况或应用于您的环境，但它们涉及到一种通用的方法。在

现状（您的代码原样）

这段代码执行一些条件运算和算术运算。这些是处理器早餐吃的那种操作……在他们醒来之前……在纳米颗粒的眼皮眨眼的时候，也就是说，非常快。现在，我知道您使用的是Arduino，因此不会有世界上最强大的处理器来使用，但是，这些操作都是处理器很快就能完成的。我想创建一些自己的基准，所以我在C++中实现了与你的函数非常相似的功能（你提到C++在你的问题中是可以的）。我调用了测试ConditionalTest，因为它遵循if...else流，而且我不擅长命名。在

注意：虽然我已经对结果做了一些初步的测试，但这些答案中提供的代码决不是生产就绪的。它缺少基本的参数检查（例如空值或未初始化的变量），并且有一些性能优化，为了安全起见，我通常会忽略这些优化。总之，代码是：

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峎u结果，而不是打印它以节省在我的控制台中填满消息的时间，而且还因为与其他操作相比，打印到屏幕的操作需要很长时间，因此会使结果膨胀。在
• 我不得不将unsigned long long用于testIterations和其他一些变量，否则{}将被包围。在
• gl_是测试中的全局变量。在

这个算法的好处是它使用非常基本的构造，因此

• 其他程序员即使对编程或其他编程语言有非常基本的了解，也会很快理解它在做什么。在
• 它非常便携，很容易翻译成其他语言和操作系统。在
• 关于性能，是wysiwyg—您看到的就是您得到的，因此第三方库调用中不太可能存在隐藏的性能瓶颈。在

我花了一万六百万次的时间才开始运行，所以我花了一万六千次。在本例中，执行10亿次迭代平均需要2400毫秒。我认为这很快，但让我们看看如何改进。首先让我们看看我们能做些什么。在

对实现进行调整

参数是(3,5)，因此最初distA是3，distB是5。注意3小于5。第e first if将检查distToA > distToB:，然后elif distToB > distToA:。然而，distToB（最初为5）可能是distToA（最初为3）的两倍。为了提高性能，您希望尽可能经常地满足第一个if条件，以尽量减少在每次迭代中检查的条件数。在说这些的时候，我对编译器做了一些假设，但稍后会有更多的讨论。在

所以，非常简单，我们可以交换ifs左右。然而，事情并不是那么简单。我发现的问题是编译器在second if和last else上做了一些很好的优化。你看到你的评论了Arbitrarily, could be distToB？实际上，else if中的gl_current += distToA;和{}中的gl_current += distToA允许编译器将其优化为一个语句。所以，在我的例子中，它不是任意的（对于您来说，它将取决于您的编译器）。因此，我们需要更改else以允许这些优化发生。最终代码是：

^{pr2}$

注意：if( distToB > distToA )在else if( distToA > distToB )之前，而else现在有gl_result = distToB和{}。有了这些更改，测试运行所用的时间是：2108毫秒。这些简单的调整使执行时间减少了12%，这很好。在

从中得到的最大教训是衡量你对意外结果所做的任何改变。在

您的编译器和执行环境可能与我的不同，因此您的结果可能会有所不同。如果你要开始在这个层次上调整东西，我建议你熟悉汇编程序，并在关键点逐步检查程序集，以确定条件实际是如何实现的。我确信还有其他的优化，比如这些。如果你真正进入它并使用GNUC++，那么有一个叫做^ {CD22}}的地方，你可以指导编译器支持哪个分支。在

您可能并不总是按顺序获得起始值，在这种情况下，您需要将一次性排序的成本与执行算法的总时间进行比较。在

其他需要指出的是：

• 您维护了一个变量current，但是您没有使用它。如果不使用current，则可以将其删除。如果编译器已经对性能进行了优化，您可能看不到性能的提高。在
• 你有一个100的范围，但是这个循环会重复3*5=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（）的一些令人惊讶的低效率，但详细说明会使这篇长文章变得更长。在

我做的下一件事就是看数据。有时候如果你能找到特征数据中的ics/patterns可以相应地优化实现。在

模式

再看看你的数据，你会发现，这些差异会每隔a * b个周期重复出现。所以，在你的测试中，一旦你达到15，距离就会重复。您可能已经意识到了这一点，但是在代码片段中，您运行了100个周期（for i in xrange(100)），所以我不确定。在

使用这个事实的一种方法是存储这些值，直到到达a * b，然后重用这些值，直到完成为止。请注意，这实际上是一个问题，首先使用您的算法，然后从那时开始迭代列表。在

static void PatternTest( 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 ) //A comes first (where a is more likely to be first than b)
        {       
            gl_result = distToA;                
            distToB -= distToA;
            distToA = startA;                               
        }
        else if( distToA > distToB ) //B comes first
        {           
            gl_result = distToB;                
            distToA -= distToB;
            distToB = startB;               
        }
        else
        {       
            gl_result = distToB;                
            distToA = startA;
            distToB = startB;
        }
        val += gl_result;
        resultList.push_back(gl_result);
        count++;
    }
    std::list<int>::const_iterator iter;
    while( count < testIterations )
    {
        for( iter = resultList.begin(); iter != resultList.end() && count < testIterations; iter++ )
        {
            gl_result = *iter;
            count++;
        }       
    }
}

这个测试用了1711毫秒，比原来快了29%，比现在最好的快了18%。我不确定这在您的案例中有多适用，但它是一个例子，说明了分析预期数据可以提供一些良好的性能提升。在

线财富！

现在，这可能不适用于你的情况，因为你在和Arduino一起工作。但也许将来会支持线程，或者您可以将问题分散到不同的处理器上。不管怎样，不包含线程基准都是不友善的，因为这正是它们生存的目的。另外，我的电脑有8个核心，其中7个都在闲逛，所以给他们一个疯狂奔跑的机会是件好事。在

如果您的数据或算法可以分解为独立的离散部分，那么您可以设计您的程序，使其在不同的线程上运行独立的操作。{26}我们现在知道在每一个序列之前。所以，我们可以从不同的点开始n，其中'（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 ) //A comes first (where a is more likely to be first than b)
        {       
            gl_result = distToA;                
            distToB -= distToA;
            distToA = startA;                               
        }
        else if( distToA > distToB ) //B comes first
        {           
            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);//http://stackoverflow.com/a/10662506/746754        
    }
    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...

我们通常会尝试排序下一个值，所以这就是我要开始的地方。我的第一个想法是将值存储在某种有序的数据结构中。我选择使用集合是因为集合是由一个键自然排序的（实际上它是一个多集，因为我们需要允许重复）。在这个集合中，我放置了一个结构（称为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的值执行此操作（例如，对于简单的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 //handle case where equal
        {
            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网站-那些家伙很厉害。在

不管怎样，这只是一个选择，它可能对您有用，也可能不适合您，这取决于您的实际性能要求。在

其他一些想法：

1. 你有多可能得到相同的一组值（a，b，c，d…）？如果有可能，您可能需要缓存以前的结果。然后只需从缓存数组中读取它们，这将非常快。在
2. 另一种提高性能的方法是启用编译器优化。如何做到这一点以及它的有效性取决于编译器。在

祝你好运。在

Answer 2

不清楚你为什么对你的代码不满意。如果是因为有“太多”if测试，那么在没有测试的情况下很容易做到：

def diffgen(a, b):
    from itertools import cycle
    diffs = []
    current = 0
    ab = a*b
    while current < ab:
        nextone = min((current // a + 1) * a,
                      (current // b + 1) * b)
        diffs.append(nextone - current)
        yield nextone - current
        current = nextone
    for d in cycle(diffs):
        yield d

请注意，一旦到达a*b，diff序列就会重复，因此不需要再进行计算。在

Answer 3

下面是一种使用模运算的方法：

a = 3
b = 5
current = 0

def nearest_multiple_of_a_or_b_to_current(current, a, b):
    distance_to_a = (a - current%a)
    distance_to_b = (b - current%b)
    return current + min(distance_to_a, distance_to_b)

for i in range(100):
    next = nearest_multiple_of_a_or_b_to_current(current, a, b)
    print(next - current)
    current = next

输出：

^{pr2}$