计算两个不同数字的倍数之间的差异

Question

计算两个不同数字的倍数之间的差异

sre*_*ond 9 c++ python algorithm

这是一个算法问题.为了简单起见,我说我有两个双打,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-esque生成器(虽然我在Arduino~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

Run Code Online (Sandbox Code Playgroud)

编辑:如何看待多个值？不仅仅是a和b,还有c,d,e等.我想我只是做一些if语句,但成本更高(每个分支的操作更多).

Answer 1

aca*_*lon 2

让我们从一些一般要点开始。从您和您的同事可以理解的直观代码开始总是更好。然后测量性能并找出瓶颈。如果您从一开始就尝试进行超级优化，您将：-

使代码变得复杂、容易出错且难以理解。
最有可能优化的代码几乎不会影响整体性能，同时忽略主要瓶颈。除非您从头到尾了解处理器、编译器、编程语言和环境的细微差别，否则如果您尝试猜测优化，很可能会使性能变得更糟。

最好测量、找到瓶颈，然后针对这些瓶颈改进性能。如果您怀疑某个算法/实现速度很慢，请对其进行分析。如果您想知道哪种算法/实现效果最好，那么就对它们进行竞赛。使用不同的数据集进行测试，因为对于一组输入 (3,5) 表现良好的内容可能不适用于另一组输入 (3, 500000000)。

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

现状（您的代码按原样）

该代码执行一些条件和算术运算。这些是处理器作为早餐吃的操作类型......在它们醒来之前......在纳米颗粒的眼睑眨眼之间，即非常快。现在，我知道您使用的是 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;
        }
    }    
}

Run Code Online (Sandbox Code Playgroud)

笔记： -

我将值分配给全局 gl_result 而不是打印它，以节省用消息填充我的控制台的时间，而且还因为与其他操作相比，打印到屏幕的操作需要很长时间，因此它会使结果膨胀。
我必须使用unsigned long longfortestIterations和其他一些变量，因为否则int会环绕。
gl_是测试中的全局变量。

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

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

现在，我正在运行一台相当糟糕的机器（i7 2600），因此需要 1000000000（10 亿）次迭代才能开始获得需要超过一秒的结果。在这种情况下，执行 10 亿次迭代平均需要 2400 毫秒。我认为这很快，但让我们看看如何改进。首先让我们看看我们可以调整什么。

对您的实施进行调整

参数为(3,5)，因此最初 distA 为 3，distB 为 5。请注意，3 小于 5。第一个if将检查是否distToA > distToB:then elif distToB > distToA:。然而，distToB（最初为 5）的可能性是 distToA（最初为 3）的两倍。if为了提高性能，您希望尽可能频繁地满足第一个条件，以尽量减少每次迭代中检查的条件数量。在这么说时，我对编译器做了一些假设，稍后会详细介绍。

所以，很简单，我们可以交换一下ifs。然而，事情并没有那么简单。我发现的问题是编译器对第二个 if 和最后一个 else 做了一些很好的优化。你看到你在哪里发表评论了Arbitrarily, could be distToB吗？gl_current += distToA;事实上，您在else if和gl_current += distToA中的事实else允许编译器将其优化为一个语句。所以，就我而言，它不是任意的（对你来说，这取决于你的编译器）。因此，我们需要更改 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 ) //A comes first (where a is more likely to be first than b)
        {       
            gl_result = distToA;
            gl_current += distToA;
            distToB -= distToA;
            distToA = startA;                               
        }
        else if( distToA > distToB ) //B comes first
        {           
            gl_result = distToB;
            gl_current += distToB;
            distToA -= distToB;
            distToB = startB;               
        }
        else
        {       
            gl_result = distToB;   //Should be distToB for optimisations
            gl_current += distToB; //Should be distToB for optimisations
            distToA = startA;
            distToB = startB;
        }
    }      
}

Run Code Online (Sandbox Code Playgroud)

注意：if( distToB > distToA )是之前else if( distToA > distToB )的， else 现在有gl_result = distToB和gl_current += distToB。进行这些更改后，测试运行所需的时间为：2108 毫秒。令人高兴的是，这些简单的调整使执行时间减少了 12%。

从中得到的最大教训是衡量你所做的任何改变是否会带来意想不到的后果。

您的编译器和执行环境可能与我的不同，因此您的结果可能会有所不同。如果您打算开始在这个级别上进行调整，我建议您熟悉汇编程序，并在关键点逐步完成汇编，以确定条件是如何实际实现的。我确信还可以进行其他诸如此类的优化。如果你真的投入其中并且正在使用 GNU C++，有一个叫做“__builtin_expect你可以指导编译器选择哪个分支”的东西。

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

其他需要指出的事情是：-

您维护一个变量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)));
    }
}

Run Code Online (Sandbox Code Playgroud)

结果是 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;
    }
}

Run Code Online (Sandbox Code Playgroud)

其中 mod 为 50000，即使在这种情况下，测试花费的时间也比您的测试长 5 倍，所以我认为如果我们寻求纯粹的性能增益，则 modulo 已经不适用了。我还发现 stl min() 存在一些令人惊讶的低效率，但详细说明会使这篇长文章变得更长。

我做的接下来的事情就是查看数据。有时，如果您可以在数据中找到特征/模式，您可以相应地优化您的实施。

图案

再次查看您的数据，会发现差异会在每个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++;
        }       
    }
}

Run Code Online (Sandbox Code Playgroud)

此次测试耗时 1711 毫秒，比原始测试快了约 29%，比当前最佳测试快了约 18%。我不确定这在您的情况下有多适用，但它是一个示例，说明分析预期数据如何提供一些良好的性能提升。

线程富矿！

现在，这可能不适用于您的情况，因为您正在使用 Arduino。但也许将来会支持线程，或者您可以将问题转移给不同的处理器。无论哪种方式，不包含线程基准都是不友善的，因为这就是他们的生存目的。另外，我的电脑有 8 个核心，其中 7 个核心都在闲逛，所以给它们一个尽情发挥的机会也很好。

如果您的数据或算法可以分解为独立的离散部分，那么您可以设计您的程序，使其在单独的线程上运行独立的操作。现在我们从之前知道该序列每个都会重复a * b。因此，我们可以从不同的点开始n，其中“(n modulo (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;
}

Run Code Online (Sandbox Code Playgroud)

结果是这花了 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()
    {

    }
};

Run Code Online (Sandbox Code Playgroud)

然后，我需要做的就是迭代该集合。在每次迭代中，集合的前面将具有最小的下一个值。所以我可以通过从中减去前一个间隔来计算当前间隔。然后，我只需要一个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 //handle case where equal
        {
            ValuesStruct valuesStruct = *iter;
            values.erase(iter);
            valuesStruct.Next += valuesStruct.Value;
            values.insert( valuesStruct );
            iter = values.begin();
        }while( (*iter).Next == prev );
    }
}

Run Code Online (Sandbox Code Playgroud)

该函数的使用方法如下：

multiset<ValuesStruct> values;
values.insert(ValuesStruct(3));
values.insert(ValuesStruct(5));
values.insert(ValuesStruct(7));
values.insert(ValuesStruct(11));
MultiConditionalTest( values, testIterations );

Run Code Online (Sandbox Code Playgroud)

正如您所看到的，这里发生了很多事情，所以我预计性能会出现井喷，结果是：105156 毫秒 - 大约慢了 50 倍。每次迭代仍然不到一微秒，因此这又取决于您的目标。由于我今天晚上刚刚敲定这个问题而没有对其进行太多分析，所以我很确定可以进行性能优化。首先，该集合通常被实现为二叉搜索树。我会做一些研究并确定这是否是解决这个问题的最佳数据结构。此外，当将新值插入到列表中时，可以给出有关将其放置在何处的提示。如果我们巧妙地选择位置，那么我们也许能够加快这一操作的速度。另外，和以前一样，当我们到达 (a * b * c * d...) 时，该序列将重复，因此我们可以存储这些值，然后从那时起将它们写出来。我还会查看问题空间，看看是否有办法优化算法，可能会在 math.stackexchange.com 上询问数学序列 - 这些人非常敏锐。

无论如何，这只是一个选项，它可能适合也可能不适合您，具体取决于您的实际性能要求。

其他一些想法：

您获得同一组值（a、b、c、d...）的可能性有多大？如果可能，您可能需要缓存以前的结果。然后只需从缓存数组中读取它们就可以了，这会非常快。
提高性能的另一种方法是打开编译器优化。如何执行此操作以及其效果如何取决于您的编译器。

祝你好运。

归档时间：	12 年前
查看次数：	989 次
最近记录：	12 年前