Created
January 28, 2020 11:08
-
-
Save rishisidhu/e56c5c0c10ddd2f45af90352f790d69a to your computer and use it in GitHub Desktop.
Two different functions to create histogram are compared on speed
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Random; | |
public class Histogram { | |
static int NUM_STUDENTS = 20000; | |
static int HIGHEST_GRADE = 10; | |
//Function to compute histogram faster O(N) | |
public void getHistFast(int iArr[], int oArr[]) | |
{ | |
for(int i=0;i<iArr.length;i++) | |
{ | |
oArr[iArr[i]]++; | |
} | |
} | |
//Function to compute histogram faster O(N^3) | |
public void getHistSlow(int iArr[], int oArr[]) | |
{ | |
for(int i=0;i<HIGHEST_GRADE;i++) | |
{ | |
int count=0; | |
for(int j=0;j<iArr.length;j++) | |
{ | |
if(iArr[j]==i) | |
{ | |
count++; | |
} | |
} | |
oArr[i]=count; | |
} | |
} | |
public static void main(String[] args) | |
{ | |
Random random = new Random(); | |
int[] student_grades = random.ints(NUM_STUDENTS, 0,HIGHEST_GRADE).toArray(); | |
int[] grade_histogram = new int[HIGHEST_GRADE]; | |
int[] grade_histogram_fast = new int[HIGHEST_GRADE]; | |
Histogram histObj = new Histogram(); | |
long start = System.currentTimeMillis(); //Count Time | |
histObj.getHistSlow(student_grades, grade_histogram); | |
long endSlow = System.currentTimeMillis(); | |
histObj.getHistFast(student_grades, grade_histogram_fast); | |
long endFast = System.currentTimeMillis(); | |
System.out.println("Time Taken For Slow Hist: "+ (endSlow - start) + " ms"); | |
System.out.println("Time Taken For Fast Hist: "+ (endFast - endSlow) + " ms"); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment