Somme des produits des deux tableaux (dotProduct)

Question

Tout d'abord, je sais que mon titre peut être formulé mieux, mais mes cours de mathématiques sont si loin de nous, je ne me souviens pas les bons mots plus ..

je dois faire quelque chose comme ceci (pseudo 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 

Ceci serait la somme du produit de l'élément [i] de chaque tableau.

Cela ne fonctionne évidemment pas. Des suggestions pour un meilleur titre ou la solution? Clarification: Je sais que je pourrais les boucler tous les deux et faire le calcul. EDIT Fondamentalement, je pense qu'il ya une meilleure façon de le faire et je le cherche purement par curiosité personnelle.

Answer 1

Avec LINQ:

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

Zip va produire une séquence de transmission en continu contenant les produits des éléments correspondants des deux matrices, qui sont ensuite sommés dans un nombre entier avec Sum.

Notez que cela ne manquera pas comme il se doit lorsque les tableaux de longueur inégale, de sorte que vous avez probablement besoin de valider l'entrée:

//null checks here 

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

EDIT: Comme le souligne Jeff M sur, Enumerable.Zip n'a été ajoutée à le cadre dans .NET 4.0. Dans .NET 3.5, vous pouvez le faire (l'idée est efficace que pour les collections qui exposent indexeurs rapide):

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(); 

Answer 2

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

Answer 3

Très simplement, faites une boucle.

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

Boom.

Answer 4

Solutions avec 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]); 

tests de performances100000 itérations:

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 

Answer 5

J'ai écrit un banc d'essai pour comparer les temps de ces méthodes sur ma machine.

Spécifications:
Windows 7 Professionnel 64 bits
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(); 
     } 
    } 
} 

cible 32 bits:

 
Regular Loop 
Iterations: 1000000 
Time(ms): 0/   0/  0 (  1172) 
Ticks:  3/ 3.101365/  526 ( 3244251) 

Enumerable "Loop" 
Iterations: 1000000 
Time(ms): 0/ 4.3E-05/  25 (  9054) 
Ticks:  24/ 24.93989/ 69441 ( 25052172) 

Using Zip 
Iterations: 1000000 
Time(ms): 0/ 2.4E-05/  16 ( 16282) 
Ticks:  41/ 44.941406/ 45395 ( 45052491) 

Using Indexed Select 
Iterations: 1000000 
Time(ms): 0/ 5.3E-05/  32 ( 13473) 
Ticks:  34/ 37.165088/ 89602 ( 37280177) 

Using Indexed Select with ElementAt 
Iterations: 1000000 
Time(ms): 0/ 1.5E-05/  6 ( 160215) 
Ticks: 405/443.154147/ 17821 (443306156) 

Parallel Enumerable "Loop" 
Iterations: 1000000 
Time(ms): 0/ 0.000103/  29 ( 17194) 
Ticks:  38/ 47.412312/ 81906 ( 47576133) 

Using Parallel Zip 
Iterations: 1000000 
Time(ms): 0/ 9.4E-05/  19 ( 21703) 
Ticks:  49/ 59.859005/ 53200 ( 60051081) 

Using Parallel Indexed Select 
Iterations: 1000000 
Time(ms): 0/ 0.000114/  27 ( 20579) 
Ticks:  45/ 56.758491/ 75455 ( 56943627) 

Using Parallel Indexed Select with ElementAt 
Iterations: 1000000 
Time(ms): 0/ 8.1E-05/  19 ( 61137) 
Ticks: 144/ 168.97909/ 53320 (169165086) 

cible 64 bits:

 
Regular Loop 
Iterations: 1000000 
Time(ms): 0/   0/  0 (  506) 
Ticks:  1/ 1.254137/ 1491 ( 1401969) 

Enumerable "Loop" 
Iterations: 1000000 
Time(ms): 0/ 2.9E-05/  15 ( 10118) 
Ticks:  27/ 27.850086/ 41954 ( 27995994) 

Using Zip 
Iterations: 1000000 
Time(ms): 0/ 2.2E-05/  13 ( 17089) 
Ticks:  45/ 47.132834/ 38506 ( 47284608) 

Using Indexed Select 
Iterations: 1000000 
Time(ms): 0/ 3.1E-05/  12 ( 14057) 
Ticks:  37/ 38.740923/ 33846 ( 38897274) 

Using Indexed Select with ElementAt 
Iterations: 1000000 
Time(ms): 0/ 3.8E-05/  29 ( 117412) 
Ticks: 304/324.711279/ 82726 (324872753) 

Parallel Enumerable "Loop" 
Iterations: 1000000 
Time(ms): 0/ 9.9E-05/  28 ( 24234) 
Ticks:  38/ 66.79389/ 77578 ( 67054956) 

Using Parallel Zip 
Iterations: 1000000 
Time(ms): 0/ 0.000111/  24 ( 30193) 
Ticks:  46/ 83.264037/ 69029 ( 83542711) 

Using Parallel Indexed Select 
Iterations: 1000000 
Time(ms): 0/ 6.5E-05/  20 ( 28417) 
Ticks:  45/ 78.337831/ 56354 ( 78628396) 

Using Parallel Indexed Select with ElementAt 
Iterations: 1000000 
Time(ms): 0/ 9.2E-05/  16 ( 65233) 
Ticks: 112/180.154663/ 44799 (180496754)