Java Program to Implement Sparse Vector

«
»
This is a Java Program to implement Sparse Vector. Sparse vectors are useful implementation of vectors that mostly contains zeroes. Here sparse vectors consists of (index, value) pairs.

Here is the source code of the Java Program to implement Sparse Vector. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  ** Java Program to implement Sparse Vector
  3.  **/
  4.  
  5. import java.util.Scanner;
  6. import java.util.TreeMap;
  7. import java.util.Map;
  8.  
  9. /** Class SparseVector **/
  10. class SparseVector
  11. {
  12. 	/* Tree map is used to maintain sorted order */
  13.     private TreeMap<Integer, Double> st;
  14.     private int N;
  15.  
  16.     /** Constructor **/
  17.     public SparseVector(int N)
  18.     {
  19.         this.N = N;
  20.         st = new TreeMap<Integer, Double>();
  21.     }
  22.  
  23.     /** Function to insert a (key, value) pair **/
  24.     public void put(int i, double value) 
  25.     {
  26.         if (i < 0 || i >= N) 
  27.                throw new RuntimeException("\nError : Out of Bounds\n");
  28.  
  29.         if (value == 0.0) 
  30.             st.remove(i);
  31.         else
  32.             st.put(i, value);
  33.     }
  34.  
  35.     /** Function to get value for a key **/
  36.     public double get(int i) 
  37.     {
  38.         if (i < 0 || i >= N) 
  39.         {
  40.             throw new RuntimeException("\nError : Out of Bounds\n");
  41.         }
  42.         if (st.containsKey(i)) 
  43.             return st.get(i);
  44.         else                
  45.             return 0.0;
  46.     }
  47.  
  48.     /** Function to get size of the vector **/
  49.     public int size() 
  50.     {
  51.         return N;
  52.     }
  53.  
  54.     /** Function to get dot product of two vectors **/
  55.     public double dot(SparseVector b) 
  56.     {
  57.         SparseVector a = this;
  58.         if (a.N != b.N) 
  59.                throw new RuntimeException("Error : Vector lengths are not same");
  60.  
  61.         double sum = 0.0;
  62.  
  63.         if (a.st.size() <= b.st.size()) 
  64.         {
  65.             for (Map.Entry<Integer, Double> entry : a.st.entrySet())
  66.                 if (b.st.containsKey(entry.getKey()))
  67.                     sum += a.get(entry.getKey()) * b.get(entry.getKey());
  68.         }          
  69.         else  
  70.         {
  71.             for (Map.Entry<Integer, Double> entry : b.st.entrySet())
  72.                 if (a.st.containsKey(entry.getKey()))
  73.                     sum += a.get(entry.getKey()) * b.get(entry.getKey());
  74.         }
  75.         return sum;
  76.     }
  77.  
  78.     /** Function to get sum of two vectors **/
  79.     public SparseVector plus(SparseVector b) 
  80.     {
  81.         SparseVector a = this;
  82.         if (a.N != b.N) 
  83.                throw new RuntimeException("Error : Vector lengths are not same");
  84.  
  85.         SparseVector c = new SparseVector(N);
  86.  
  87.         for (Map.Entry<Integer, Double> entry : a.st.entrySet())
  88.             c.put(entry.getKey(), a.get(entry.getKey()));
  89.  
  90.         for (Map.Entry<Integer, Double> entry : b.st.entrySet())
  91.             c.put(entry.getKey(), b.get(entry.getKey()) + c.get(entry.getKey()));
  92.  
  93.         return c;
  94.     }
  95.  
  96.     /** Function toString() for printing vector **/
  97.     public String toString() 
  98.     {
  99.         String s = "";
  100.         for (Map.Entry<Integer, Double> entry : st.entrySet())
  101.             s += "(" + entry.getKey() + ", " + st.get(entry.getKey()) + ") ";
  102.  
  103.         return s;
  104.     }
  105. }
  106.  
  107. /** Class SparseVector **/
  108. public class SparseVectorTest
  109. {
  110.     public static void main(String[] args)
  111.     {
  112.         System.out.println("Sparse Vector Test\n");
  113.         Scanner scan = new Scanner(System.in);
  114.  
  115.         System.out.println("Enter size of sparse vectors");
  116.         int n = scan.nextInt();
  117.  
  118.         SparseVector v1 = new SparseVector(n);
  119.         SparseVector v2 = new SparseVector(n);
  120.  
  121.         System.out.println("\nEnter number of entries for vector 1");
  122.         int n1 = scan.nextInt();
  123.         System.out.println("Enter "+ n1 +" (int, double) pairs");
  124.         for (int i = 0; i < n1; i++)
  125.             v1.put(scan.nextInt(), scan.nextDouble() );
  126.  
  127.         System.out.println("\nEnter number of entries for vector 2");
  128.         int n2 = scan.nextInt();
  129.         System.out.println("Enter "+ n2 +" (int, double) pairs");
  130.         for (int i = 0; i < n2; i++)
  131.             v2.put(scan.nextInt(), scan.nextDouble() );
  132.  
  133.         System.out.println("\n");
  134.         System.out.println("Vector v1 = " + v1);
  135.         System.out.println("Vector v2 = " + v2);
  136.         System.out.println("\nv1 dot v2 = " + v1.dot(v2));
  137.         System.out.println("v1  +  v2   = " + v1.plus(v2));
  138.     }
  139. }

advertisement
Sparse Vector Test
 
Enter size of sparse vectors
70000
 
Enter number of entries for vector 1
4
Enter 4 (int, double) pairs
3 1.0
2500 6.3
5000 10.0
60000 5.7
 
Enter number of entries for vector 2
3
Enter 3 (int, double) pairs
1 7.5
3 5.7
2500 -6.3
 
 
Vector v1 = (3, 1.0) (2500, 6.3) (5000, 10.0) (60000, 5.7)
Vector v2 = (1, 7.5) (3, 5.7) (2500, -6.3)
 
v1 dot v2 = -33.989999999999995
v1  +  v2   = (1, 7.5) (3, 6.7) (5000, 10.0) (60000, 5.7)

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.