两个数组的乘积之和（点积）

Question

两个数组的乘积之和（点积）

19

首先，我知道我的标题可以更好地表达，但是我的数学课已经过去了，我不记得正确的术语了...

我需要做类似于以下的事情（伪c#）

int[] digits1 = new int[10]{0,1,2,3,4,5,6,7,8,9};
int[] digits2 = new int[10]{0,1,2,3,4,5,6,7,8,9};
int result = digits1*digits2

这将是每个数组的element[i]的乘积之和。

这显然行不通。对于更好的标题或解决方案有什么建议吗？

编辑：澄清：我知道我可以循环它们并进行计算。基本上，我认为有一种更好的方法来做到这一点，我正在出于个人好奇心寻找它。

- Boris Callens

1

你是在说 (0*0) + (1*1) + (2*2) + ... 这个吧？ - Bill the Lizard

2

你好，你似乎需要的产品类型被称为点积：http://en.wikipedia.org/wiki/Dot_product。 - Michael McGowan

太好了，谢谢。我知道这个有一个名字 :) - Boris Callens

6个回答

11

LINQ解决方案

int[] digits1 = new int[10]{0,1,2,3,4,5,6,7,8,9};
int[] digits2 = new int[10]{0,1,2,3,4,5,6,7,8,9};

int result1 = digits1.Zip(digits2, (x, y) => x * y).Sum();

int result2 = digits1.Select((x, y) => x * digits2.ElementAt(y)).Sum();

int result3 = digits1.Select((n, i) => n * digits2[i]).Sum();

// Ani answer
int result4 = Enumerable.Range(0, digits1.Length)
    .Sum(i => digits1[i] * digits2[i]);

性能测试 100000 次迭代：

Queries
Fn: Result 1       Ticks 135306
Fn: Result 2       Ticks 2470614
Fn: Result 3       Ticks 130034
Fn: Result 4       Ticks 123374

-------------

Fastest
Fn: Result 4       Ticks 123374
Fn: Result 3       Ticks 130034
Fn: Result 1       Ticks 135306
Fn: Result 2       Ticks 2470614

- BrunoLM

这很有趣。谢谢。我想知道2的差异来自哪里。 - Boris Callens

9

我在我的电脑上编写了一个测试工具来比较这些方法的时间。

规格: Windows 7 Professional 64位 Intel Core 2 Quad Q9550 @ 2.83GHz 4x1GiB Corsair Dominator DDR2 1066 (PC2-8500)

using System;
using System.Linq;

namespace Testbench
{
    class Program
    {
        static void Main(string[] args)
        {
            var digits1 = Enumerable.Range(0, 500).ToArray();
            var digits2 = digits1.ToArray(); // create a copy

            Test("Regular Loop", () =>
            {
                int result = 0;
                for (int i = 0; i < digits1.Length; i++)
                {
                    result += digits1[i] * digits2[i];
                }
                return result;
            });

            // using LINQ
            Test("Enumerable \"Loop\"", () => Enumerable.Range(0, digits1.Length).Sum(i => digits1[i] * digits2[i]));
            Test("Using Zip", () => digits1.Zip(digits2, (x, y) => x * y).Sum());
            Test("Using Indexed Select", () => digits1.Select((n, i) => n * digits2[i]).Sum());
            Test("Using Indexed Select with ElementAt", () => digits1.Select((n, i) => n * digits2.ElementAt(i)).Sum());

            // using PLINQ
            Test("Parallel Enumerable \"Loop\"", () => ParallelEnumerable.Range(0, digits1.Length).Sum(i => digits1[i] * digits2[i]));
            Test("Using Parallel Zip", () => digits1.AsParallel().Zip(digits2.AsParallel(), (x, y) => x * y).Sum());
            Test("Using Parallel Indexed Select", () => digits1.AsParallel().Select((n, i) => n * digits2[i]).Sum());
            Test("Using Parallel Indexed Select with ElementAt", () => digits1.AsParallel().Select((n, i) => n * digits2.ElementAt(i)).Sum());

            Console.Write("Press any key to continue . . . ");
            Console.ReadKey(true);
            Console.WriteLine();
        }

        static void Test<T>(string testName, Func<T> test, int iterations = 1000000)
        {
            Console.WriteLine(testName);
            Console.WriteLine("Iterations: {0}", iterations);
            var results = Enumerable.Repeat(0, iterations).Select(i => new System.Diagnostics.Stopwatch()).ToList();
            var timer = System.Diagnostics.Stopwatch.StartNew();
            for (int i = 0; i < results.Count; i++)
            {
                results[i].Start();
                test();
                results[i].Stop();
            }
            timer.Stop();
            Console.WriteLine("Time(ms): {0,3}/{1,10}/{2,8} ({3,10})", results.Min(t => t.ElapsedMilliseconds), results.Average(t => t.ElapsedMilliseconds), results.Max(t => t.ElapsedMilliseconds), timer.ElapsedMilliseconds);
            Console.WriteLine("Ticks:    {0,3}/{1,10}/{2,8} ({3,10})", results.Min(t => t.ElapsedTicks), results.Average(t => t.ElapsedTicks), results.Max(t => t.ElapsedTicks), timer.ElapsedTicks);
            Console.WriteLine();
        }
    }
}

32位目标:

常规循环
迭代次数：1000000
时间（毫秒）：0 / 0 / 0（1172）
时钟周期：3 / 3.101365 / 526（3244251）
可枚举的“循环”
迭代次数：1000000
时间（毫秒）：0 / 4.3E-05 / 25（9054）
时钟周期：24 / 24.93989 / 69441（25052172）
使用Zip
迭代次数：1000000
时间（毫秒）：0 / 2.4E-05 / 16（16282）
时钟周期：41 / 44.941406 / 45395（45052491）
使用索引选择
迭代次数：1000000
时间（毫秒）：0 / 5.3E-05 / 32（13473）
时钟周期：34 / 37.165088 / 89602（37280177）
使用带有ElementAt的索引选择
迭代次数：1000000
时间（毫秒）：0 / 1.5E-05 / 6（160215）
时钟周期：405 / 443.154147 / 17821（443306156）
并行可枚举的“循环”
迭代次数：1000000
时间（毫秒）：0 / 0.000103 / 29（17194）
时钟周期：38 / 47.412312 / 81906（47576133）
使用并行Zip
迭代次数：1000000
时间（毫秒）：0 / 9.4E-05 / 19（21703）
时钟周期：49 / 59.859005 / 53200（60051081）
使用并行索引选择
迭代次数：1000000
时间（毫秒）：0 / 0.000114 / 27（20579）
时钟周期：45 / 56.758491 / 75455（56943627）
使用带有ElementAt的并行索引选择
迭代次数：1000000
时间（毫秒）：0 / 8.1E-05 / 19（61137）
时钟周期：144 / 168.97909 / 53320（169165086）

64位目标:

正常循环迭代次数：1000000 时间（毫秒）：0 / 0 / 0（506）滴答声：1 / 1.254137 / 1491（1401969）

可枚举的“循环” 迭代次数：1000000 时间（毫秒）：0 / 2.9E-05 / 15（10118）滴答声：27 / 27.850086 / 41954（27995994）

使用Zip 迭代次数：1000000 时间（毫秒）：0 / 2.2E-05 / 13（17089）滴答声：45 / 47.132834 / 38506（47284608）

使用索引选择迭代次数：1000000 时间（毫秒）：0 / 3.1E-05 / 12（14057）滴答声：37 / 38.740923 / 33846（38897274）

使用具有ElementAt的索引选择迭代次数：1000000 时间（毫秒）：0 / 3.8E-05 / 29（117412）滴答声：304 / 324.711279 / 82726（324872753）

并行可枚举的“循环” 迭代次数：1000000 时间（毫秒）：0 / 9.9E-05 / 28（24234）滴答声：38 / 66.79389 / 77578（67054956）

使用并行Zip 迭代次数：1000000 时间（毫秒）：0 / 0.000111 / 24（30193）滴答声：46 / 83.264037 / 69029（83542711）

使用并行索引选择迭代次数：1000000 时间（毫秒）：0 / 6.5E-05 / 20（28417）滴答声：45 / 78.337831 / 56354（78628396）

使用具有ElementAt的并行索引选择迭代次数：1000000 时间（毫秒）：0 / 9.2E-05 / 16（65233）滴答声：112 / 180.154663 / 44799（180496754）

- Jeff Mercado

哇，我以为循环会更快，但没有想到会快那么多。LINQ方法肯定更短，写起来也更简单，但会产生很多开销。感谢你运行测试。 - Alan Geleynse

在多线程场景下，LINQ 方法不会更快吗？ - Boris Callens

1

@boris：不会的。虽然有优化机会，但它只会使用单个线程。如果改用PLINQ，那肯定可以。我会进行修改以包含它们，并重新发布我的结果。 - Jeff Mercado

@boris：我说“肯定有”，但是有一些注意事项。如果数组足够大，那么“肯定有”。否则，这是不必要的开销，可能没有好处。 - Jeff Mercado

@boris: 我会再次更新。（我需要找到更好的方法来测量时间）重新构建测试函数改善了所有方面的时间（因为我没有预料到的开销）。数字更加合理。 - Jeff Mercado

哇，感谢您的所有努力。看来对于我的情况，普通的for循环仍然更有趣。 - Boris Callens

8

非常简单，做一个循环。

int sum = 0;
for(int i = 0; i < digits1.length && i < digits2.length; i++)
{
    sum += digits1[i] * digits2[i];
}

嘭。

- JoshD

4

int result = 0;
for(int i = 0; i < digits1.length; i++)
{
    result += digits1[i] * digits2[i];
}

- Alan Geleynse

嗯，是的，但这个问题难道没有更好的算法吗？ - Boris Callens

1

我认为你至少需要进行n次乘法和n次加法，而这个代码已经做到了。我相信这是可能的最小工作量。也许有更少的代码可以实现同样的功能，但代码所完成的工作将是相同的。 - Alan Geleynse

我同意以上观点。短小而花哨的方法可以让工作更简洁，但是后来阅读代码的其他人可能不太容易理解。 - JoshD

1

有人能进行性能测试吗？@BrunoLM已经为LINQ解决方案运行了一个，但我很想将其与循环进行比较，而我现在没有可用的C#环境。 - Alan Geleynse

这是最好的。由于Linq提供了一些额外的开销，因此可以轻松地转换成任何其他语言，并具有最佳性能。 - Bitterblue

显示剩余4条评论

0

更快的方法是展开循环

Test("Regular Loop", () =>
            {
                int result = 0;
                for (int i = 0; i < digits1.Length; i++)
                {
                    result += digits1[i] * digits2[i];
                }
                return result;
            });
            // This will fail if vectors are not a multiple of 4 in length.
            Test("Unroll 4x", () =>
            {
                int result = 0;
                for (int i = 0; i < digits1.Length; i+=4)
                {
                    result += digits1[i] * digits2[i];
                    result += digits1[i+1] * digits2[i+1];
                    result += digits1[i+2] * digits2[i+2];
                    result += digits1[i+3] * digits2[i+3];
                }
                return result;
            });

            Test("Dynamic unroll", () =>
            {
                int result = 0;
                int limit = (digits1.Length/8)*8;
                int reminderLimit = digits1.Length;

                if (digits1.Length >= 8)
                {
                    for (int i = 0; i < limit; i+=8)
                    {
                        result += digits1[i] * digits2[i];
                        result += digits1[i+1] * digits2[i+1];
                        result += digits1[i+2] * digits2[i+2];
                        result += digits1[i+3] * digits2[i+3];
                        result += digits1[i+4] * digits2[i+4];
                        result += digits1[i+5] * digits2[i+5];
                        result += digits1[i+6] * digits2[i+6];
                        result += digits1[i+7] * digits2[i+7];
                    }

                    reminderLimit = digits1.Length % 8;
                }

                switch(reminderLimit)
                {
                    case 7: {
                                result += digits1[limit] * digits2[limit];
                                result += digits1[limit+1] * digits2[limit+1];
                                result += digits1[limit+2] * digits2[limit+2];
                                result += digits1[limit+3] * digits2[limit+3];
                                result += digits1[limit+4] * digits2[limit+4];
                                result += digits1[limit+5] * digits2[limit+5];
                                result += digits1[limit+6] * digits2[limit+6];
                                break;
                            }

                    case 6: {
                                result += digits1[limit] * digits2[limit];
                                result += digits1[limit+1] * digits2[limit+1];
                                result += digits1[limit+2] * digits2[limit+2];
                                result += digits1[limit+3] * digits2[limit+3];
                                result += digits1[limit+4] * digits2[limit+4];
                                result += digits1[limit+5] * digits2[limit+5];      
                                break;
                            }

                    case 5: {
                                result += digits1[limit] * digits2[limit];
                                result += digits1[limit+1] * digits2[limit+1];
                                result += digits1[limit+2] * digits2[limit+2];
                                result += digits1[limit+3] * digits2[limit+3];
                                result += digits1[limit+4] * digits2[limit+4];
                                break;
                            }

                    case 4: {
                                result += digits1[limit] * digits2[limit];
                                result += digits1[limit+1] * digits2[limit+1];
                                result += digits1[limit+2] * digits2[limit+2];
                                result += digits1[limit+3] * digits2[limit+3];
                                break;
                            }

                    case 3: {
                                result += digits1[limit] * digits2[limit];
                                result += digits1[limit+1] * digits2[limit+1];
                                result += digits1[limit+2] * digits2[limit+2];
                                break;
                            }

                    case 2: {
                                result += digits1[limit] * digits2[limit];
                                result += digits1[limit+1] * digits2[limit+1];
                                break;
                            }

                    case 1: {
                                result += digits1[limit] * digits2[limit];
                                break;
                            }
                    default :
                            {
                                break;
                            }
                }

                return result;
            });

在C#代码的调试模式和发布模式之间，运行时间有很大的差异。下面是使用发布模式运行的代码：

Regular Loop
Iterations: 1000000
Time(ms):   0/         0/       0 (       596)
Ticks:      1/  2,071213/     455 (   2154248)

Unroll 4x
Iterations: 1000000
Time(ms):   0/     2E-06/       1 (       575)
Ticks:      1/  1,984301/    3876 (   2076105)

Dynamic unroll
Iterations: 1000000
Time(ms):   0/         0/       0 (       430)
Ticks:      1/    1,4635/    3228 (   1554830)

调试模式：

Regular Loop
Iterations: 1000000
Time(ms):   0/     1E-06/       1 (      1296)
Ticks:      4/  4,529916/    3907 (   4678354)

Unroll 4x
Iterations: 1000000
Time(ms):   0/         0/       0 (       871)
Ticks:      2/  3,048466/     701 (   3145277)

Dynamic unroll
Iterations: 1000000
Time(ms):   0/         0/       0 (       819)
Ticks:      2/  2,858588/    1398 (   2957179)

- Stefan Granath

我是否正确地理解了结果，即在Release中，1M次迭代的最佳情况差异为160毫秒？看起来这是一个超级小众情况的不错优化，但并不建议将其作为常规解决方案 :) - Boris Callens

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ani · Accepted Answer

使用LINQ：

int dotProduct = digits1.Zip(digits2, (d1, d2) => d1 * d2)
                        .Sum();

Zip将生成一个流式序列，其中包含来自两个数组的相应元素的产品，然后使用Sum将其求和为整数。

请注意，这不会像应该的那样在长度不相等的数组时失败，因此您可能需要验证输入：

//null checks here

if(digits1.Length != digits2.Length)
   throw new ArgumentException("...");

编辑：正如Jeff M指出的那样，Enumerable.Zip仅在.NET 4.0中添加到框架中。在.NET 3.5中，您可以这样做（这个想法只对公开快速索引器的集合有效）：

int dotProduct = Enumerable.Range(0, digits1.Length)
                           .Sum(i => digits1[i] * digits2[i]);

//from Jeff M's comment:
int dotProduct = digits1.Select((n, i) => n * digits2[i])
                        .Sum();