fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3.  
  4. class Ideone {
  5.  
  6. 	public static int plainDotProduct(int[] v1, int[] v2) {
  7. 		int dotProduct = 0;
  8. 		for (int i = 0 ; i < v1.length; i++) {
  9. 			dotProduct += v1[i] * v2[i];
  10. 		}
  11. 		return dotProduct;
  12. 	}
  13.  
  14. 	public static int dotProduct(List<int[]> v1, List<int[]> v2) {
  15. 		int dotProduct = 0;
  16. 		for (int i = 0, j = 0; i < v1.size() && j < v2.size(); ) {
  17. 			int[] a = v1.get(i);
  18. 			int[] b = v2.get(j);
  19.  
  20. 			int multiplier = Math.min(a[0], b[0]);
  21. 			a[0] -= multiplier;
  22. 			b[0] -= multiplier;
  23.  
  24. 			dotProduct += a[1] * b[1] * multiplier;
  25.  
  26. 			if (a[0] == 0) i++;
  27. 			if (b[0] == 0) j++;
  28. 		}
  29. 		return dotProduct;
  30. 	}
  31.  
  32. 	public static List<int[]> compress(int[] arr) {
  33. 		List<int[]> compressed = new ArrayList<>();
  34. 		for (int i = 0; i < arr.length; i++) {
  35. 			int val = arr[i];
  36. 			int count = 1;
  37. 			for (; i + 1 < arr.length && arr[i + 1] == val; i++) {
  38. 				count++;
  39. 			}
  40. 			compressed.add(new int[] {count, val});
  41. 		}
  42. 		return compressed;
  43. 	}
  44.  
  45. 	public static void main (String[] args) {
  46. 		int[] a = {1, 1, 4, 4, 4, 4, 7, 7, 7, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2};
  47. 		int[] b = {2, 2, 5, 5, 5, 5, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
  48. 		System.out.println(plainDotProduct(a, b));
  49. 		System.out.println(dotProduct(compress(a), compress(b)));
  50. 	}
  51. }
Success #stdin #stdout 0.07s 54588KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
291
291
https://ideone.com/nX6BOO
Space efficient representation and dot product of 2 vectors
language:
Java (HotSpot 12)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!