2010-10-21 25 views
13

Prima di tutto, so che il mio titolo può essere formulato meglio, ma le mie lezioni di matematica sono così lontano andato io non ricordo più le parole giuste ..Somma di prodotti di due array (dotproduct)

ho bisogno di fare qualcosa di simile (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 

questa sarebbe la somma del prodotto dell'elemento [i] di ciascun array.

Questo ovviamente non funziona. Qualche suggerimento verso un titolo migliore o la soluzione?

EDIT chiarimento: so che potrei collegarli entrambi e fare i conti. Fondamentalmente penserei che ci sia un modo migliore per farlo e lo sto cercando solo per curiosità personale.

+1

Giusto per essere chiaro, stai parlando di '(0 * 0) + (1 * 1) + (2 * 2) + ...' giusto? –

+0

@ conto: sì. totalmente –

+2

FYI, il tipo di prodotto che sembri desiderare si chiama prodotto punto: http://en.wikipedia.org/wiki/Dot_product –

risposta

30

Con LINQ:

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

Zip produrrà una sequenza di streaming contenente i prodotti degli elementi di entrambi gli array, che viene poi sommati in un intero con Sum corrispondente.

Si noti che questo non mancherà come dovrebbe quando gli array di lunghezza diversa, quindi probabilmente è necessario per convalidare l'input:

//null checks here 

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

EDIT: Come Jeff M sottolinea, Enumerable.Zip è stato aggiunto solo per il framework in .NET 4.0. In .NET 3.5, è possibile farlo (l'idea è efficace solo per le collezioni che espongono indicizzatori veloci):

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

Per .NET 3.5: 'int result = digits1.Select ((n, i) => n * digits2 [i]). Sum();' –

+0

Non conoscevo la funzione Zip. Controllerò. Grazie :) –

+2

@boris: dovresti notare che il metodo di estensione 'Zip()' è stato aggiunto in .NET 4.0. –

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

Beh, sì, ma non c'è un algoritmo migliore per questo? –

+1

Io non la penso così, devi fare almeno n moltiplicazioni e n aggiunte, e questo fa. Credo che sia la minima quantità di lavoro possibile. Ci possono essere modi per farlo con meno codice, ma il lavoro che fa il codice sarà lo stesso. –

+0

Sembra che ci sia un modo migliore per farlo, è passato troppo tempo da quando ho fatto C#. Ma credo che il runtime dovrebbe essere simile per Zip e il ciclo poiché lo stesso lavoro deve essere fatto. –

8

Molto semplicemente, fare un ciclo.

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

Boom.

9

soluzioni con 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]); 

Performance Test100000 iterazioni:

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 
+0

Questo è interessante. Grazie. Mi chiedo da dove viene il diff da 2. –

7

Ho scritto un banco di prova per confrontare i tempi di questi metodi sulla mia macchina.

Spec:
Windows 7 Professional a 64 bit
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(); 
     } 
    } 
} 

bersaglio a 32 bit:

 
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) 

bersaglio a 64 bit:

 
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) 
+0

Wow, ho pensato che il ciclo sarebbe stato più veloce, ma non di molto. I metodi LINQ sono decisamente più brevi e discutibili più semplici da scrivere, ma creano un sacco di spese generali. Grazie per aver eseguito il test. –

+0

I metodi linq non sarebbero più veloci in uno scenario multi-threading? –

+1

@boris: No, non lo farebbe. Mentre ci sono opportunità di ottimizzazione, utilizzerà solo un singolo thread. Se cambiato per usare PLINQ, allora sì sicuramente. Farò delle modifiche per includerli e ripubblicare i miei risultati. –