dot product of two sparse vectors In Java
The dot product, also known as the scalar product or inner product, is a fundamental operation in linear algebra that combines two vectors to produce a scalar value. In the context of sparse vectors, where most elements are zero, computing the dot product can be optimized by considering only the non-zero elements.
Examples:
Example 1:
Input:
'N' = 4
'vec1' = {1, 2, 3, 4}
'vec2' = {5, 6, 7, 8}
Output:
Dot product: 70
Explanation:
Dot product: (1 * 5) + (2 * 6) + (3 * 7) + (4 * 8) = 5 + 12 + 21 + 32 = 70
Hence, the final answer is 70.
Example 2:
Input:
'N' = 3
'vec1' = {3, 1, 2}
'vec2' = {4, 2, 0}
Output:
Dot product: 14
Explanation:
Dot product: (3 * 4) + (1 * 2) + (2 * 0) = 12 + 2 + 0 = 14
Hence, the final answer is 14.
Approach 1: Using Naïve Method
ALGORITHM:
Step 1: Create a HashMap to store the non-zero elements of the first sparse vector (vec1). The HashMap will use the index as the key and the corresponding value from vec1 as the value.
Step 2: Iterate through vec1 and store the non-zero elements in the HashMap. If an element is non-zero, add it to the HashMap with its index as the key and the element value as the value.
Step 3: Initialize a variable dotProduct to store the final dot product result.
Step 4: Iterate through the second sparse vector (vec2). For each non-zero element in vec2, check if the corresponding index exists in the HashMap created in step 1. If the index exists, multiply the element from vec2 with the corresponding value from vec1 (retrieved from the HashMap) and add the result to the dotProduct variable.
Step 5: After iterating through both vectors, return the final value of dotProduct, which represents the dot product of the two sparse vectors.
Implementation:
The implementation of the above steps given below
FileName: SparseVectorDotProduct1.java
import java.util.HashMap;
public class SparseVectorDotProduct1 {
// Function to calculate dot product of two sparse vectors
public static int dotProduct(int[] vec1, int[] vec2) {
// Create a HashMap to store non-zero elements of vec1
HashMap map = new HashMap<>();
// Iterate through vec1 and store non-zero elements in the map
for (int i = 0; i < vec1.length; i++) {
if (vec1[i] != 0) {
map.put(i, vec1[i]);
}
}
int dotProduct = 0;
// Iterate through vec2 and calculate dot product with elements from vec1
for (int i = 0; i < vec2.length; i++) {
// If current element of vec2 is non-zero and corresponding index exists in vec1
if (vec2[i] != 0 && map.containsKey(i)) {
dotProduct += vec2[i] * map.get(i);
}
}
return dotProduct;
}
public static void main(String[] args) {
// Example 1
int[] vec1_1 = {1, 2, 3, 4};
int[] vec2_1 = {5, 6, 7, 8};
int result1 = dotProduct(vec1_1, vec2_1);
System.out.println("Dot product: " + result1); // Output: 70
// Example 2
int[] vec1_2 = {3, 1, 2};
int[] vec2_2 = {4, 2, 0};
int result2 = dotProduct(vec1_2, vec2_2);
System.out.println("Dot product: " + result2); // Output: 14
}
}
Output:
Dot product: 70 Dot product: 14
Complexity Analysis:
Time Complexity:
The overall time complexity of the dotProduct function is O(m+n), where m and n are the lengths of vec1 and vec2, respectively.
Space Complexity:
The space complexity is O(m), as we store the non-zero elements of vec1 in the HashMap, which can have at most m entries (assuming vec1 has m non-zero elements).
Approach 2: Efficient Method
ALGORITHM:
Step 1: Start by setting the dot product variable to 0, which will accumulate the result of the dot product calculation.
Step 2: Use a single loop to iterate over both vec1 and vec2 at the same time, considering elements at the same index.
Step 3: For each index, check if both elements from vec1 and vec2 are non-zero. If both elements are non-zero, proceed to calculate their product.
Step 4: Multiply the non-zero elements from vec1 and vec2 at the current index and add the result to the dot product variable.
Step 5: Continue iterating through the vectors until all elements have been processed, calculating the dot product for each pair of non-zero elements.
Step 6: Once all elements have been processed, return the accumulated dot product as the final result of the function.
Implementation:
The implementation of the above steps given below
FileName: SparseVectorDotProduct2.java
import java.util.HashMap;
public class SparseVectorDotProduct2 {
// Function to calculate dot product of two sparse vectors
public static int dotProduct(int[] vec1, int[] vec2) {
int dotProduct = 0;
// Iterate through both vectors simultaneously
for (int i = 0; i < vec1.length; i++) {
// Multiply corresponding elements only if both are non-zero
if (vec1[i] != 0 && vec2[i] != 0) {
dotProduct += vec1[i] * vec2[i];
}
}
return dotProduct;
}
public static void main(String[] args) {
// Example 1
int[] vec1_1 = {1, 2, 3, 4};
int[] vec2_1 = {5, 6, 7, 8};
int result1 = dotProduct(vec1_1, vec2_1);
System.out.println("Dot product: " + result1); // Output: 70
// Example 2
int[] vec1_2 = {3, 1, 2};
int[] vec2_2 = {4, 2, 0};
int result2 = dotProduct(vec1_2, vec2_2);
System.out.println("Dot product: " + result2); // Output: 14
}
}
Output:
Dot product: 70 Dot product: 14
Complexity Analysis:
Time Complexity:
The dotProduct function iterates through both vec1 and vec2 simultaneously using a single loop, which takes O(n) time, where n is the length of the longer vector between vec1 and vec2. Therefore, the overall time complexity of the dotProduct function is O(n), where n is the length of the longer vector between vec1 and vec2.
Space Complexity:
The space complexity of the dotProduct function is O(1) because it only uses a constant amount of extra space for the dotProduct variable and loop counters. It does not require any additional data structures that grow with the input size.