Skip to content

Instantly share code, notes, and snippets.

@rishisidhu
Created January 28, 2020 11:08
Show Gist options
  • Save rishisidhu/e56c5c0c10ddd2f45af90352f790d69a to your computer and use it in GitHub Desktop.
Save rishisidhu/e56c5c0c10ddd2f45af90352f790d69a to your computer and use it in GitHub Desktop.
Two different functions to create histogram are compared on speed
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