3
\$\begingroup\$

I want to optimize my code for performance and fine-tuned logic.

import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Collections;
import java.util.Comparator;

/**
 * Created by ShrivasA on 1/30/2015.
 */
/* Take an Element and Apply the following conditions:
    1. The element should not already be there.
    2. The element should have an element which is last element-1 otherwise create a new one.
    3. in case the element is eligible in all the lists add the element in the list which has least number of elements.
 */
public class TeamFormation {

    /**
     * Bucket sort
     * @param array array to be sorted
     * @param bucketCount number of buckets
     * @return array sorted in ascending order
     */
    public static int[] bucketSort(int[] array, int bucketCount) {
        if (bucketCount <= 0) throw new IllegalArgumentException("Invalid bucket count");
        if (array.length <= 1) return array; //trivially sorted

        int high = array[0];
        int low = array[0];
        for (int i = 1; i < array.length; i++) { //find the range of input elements
            if (array[i] > high) high = array[i];
            if (array[i] < low) low = array[i];
        }
        double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket

        ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
        for (int i = 0; i < bucketCount; i++) { //initialize buckets
            buckets[i] = new ArrayList();
        }

        for (int i = 0; i < array.length; i++) { //partition the input array
            buckets[(int)((array[i] - low)/interval)].add(array[i]);
        }

        int pointer = 0;
        for (int i = 0; i < buckets.length; i++) {
            Collections.sort(buckets[i]); //mergeSort
            for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets
                array[pointer] = buckets[i].get(j);
                pointer++;
            }
        }
        return array;
    }



    public static void main(String[] args) {

        Scanner scanInput = new Scanner(System.in);
        int testCases = scanInput.nextInt();
        //long startTime=0;
        //System.out.println("The Input given is:::"+testCases);
        StringBuilder result = new StringBuilder();
        TeamFormation tm= new TeamFormation();
        try {
               // Thread t1= new Thread();
                //t1.wait(2000);
                while (testCases > 0) {
                //Scanner inputTeam = (new Scanner(System.in));
               // startTime= System.currentTimeMillis();
                Integer lng = scanInput.nextInt();
                if(lng!=0){
                int[] sortArray= new int[lng];
                    long stime=System.currentTimeMillis();
                    for (int i = 0; i < lng; i++) {
                    Integer test = scanInput.nextInt();
                    //System.out.println(test);
                    sortArray[i] = test;
                }
                tm.bucketSort(sortArray,lng);
                //Arrays.sort(sortArray);
                //long etime=System.currentTimeMillis();
                //System.out.println("Time to prepare and sort Array::"+(etime-stime));
                //long stTime = System.currentTimeMillis();
                List<List> lst = new ArrayList<List>(5);
                int len = sortArray.length;
                    //System.out.println("Array Size::::"+len);
                for (int i = 0; i < len; i++) {
                    long test = sortArray[i];
                    if (lst.size() == 0) {
                        List l1 = new ArrayList(5);
                        //if(l1.contains())
                        //l1[i]=test;
                        l1.add(test);
                        lst.add(l1);
                    } else {
                        List<List> temp = new ArrayList<List>(lst);
                        for (List strlist : temp) {
                            if (!strlist.contains(test) && strlist.contains(test - 1)) {
                                strlist.add(test);
                                lst.add(strlist);
                                test = 0;
                            }
                        }
                        //lst.toArray();
                        if (test != 0) {
                            List<Long> l2 = new ArrayList<Long>(5);
                            l2.add(test);
                            lst.add(l2);
                        }
                    }

                    Collections.sort(lst, new Comparator<List>() {
                        public int compare(List a1, List a2) {
                            return a1.size() - a2.size(); // assumes you want smallest to biggest
                        }
                    });
                }
                result.append((lst.get(0)).size() + "\n");
                //long enTime=System.currentTimeMillis();
               // System.out.println("Time taken for second Half process::"+(enTime-stTime));
            }else{
                    result.append(0+"\n");
                }
                testCases--;
            }
        } catch (Exception ex) {
            ex.printStackTrace();
        }
        System.out.println(result);
        //long endTime= System.currentTimeMillis();
        //System.out.println("The total time taken is:::"+(endTime-startTime));
    }

}
\$\endgroup\$
  • 1
    \$\begingroup\$ Can you tell us more about what the code does? It makes it much easier on reviewers if there's a plain English description of what you expect the code to accomplish. \$\endgroup\$ – RubberDuck Feb 25 '15 at 13:40
6
\$\begingroup\$

Code which is commented out is dead code which should be deleted to increase readability.


Using correct indention will add readability.

            while (testCases > 0) {

            Integer lng = scanInput.nextInt();
            if(lng!=0){
            int[] sortArray= new int[lng];
                long stime=System.currentTimeMillis();
                for (int i = 0; i < lng; i++) {
                Integer test = scanInput.nextInt();
                sortArray[i] = test;
            }

looks strange and not readable while

            while (testCases > 0) {
                Integer lng = scanInput.nextInt();
                if(lng!=0){
                    int[] sortArray= new int[lng];
                    long stime=System.currentTimeMillis();
                    for (int i = 0; i < lng; i++) {
                        Integer test = scanInput.nextInt();
                        sortArray[i] = test;
                    }

looks much more readable. Your IDE will have some kind of keyboard shortcut to automatically format your source.


You should always code against interfaces rather than against concrete implementations.

ArrayList<Integer> buckets[] = new ArrayList[bucketCount];  

should be

List<Integer> buckets[] = new ArrayList[bucketCount];  

Using braces {} for single line if statements also, makes your code less error prone.


Variables should be declared as near as possible to their usage.

double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket

ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
for (int i = 0; i < bucketCount; i++) { //initialize buckets
    buckets[i] = new ArrayList();
}

for (int i = 0; i < array.length; i++) { //partition the input array
    buckets[(int)((array[i] - low)/interval)].add(array[i]);
}

should be

ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
for (int i = 0; i < bucketCount; i++) { //initialize buckets
    buckets[i] = new ArrayList();
}

double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket
for (int i = 0; i < array.length; i++) { //partition the input array
    buckets[(int)((array[i] - low)/interval)].add(array[i]);
}

You should let your variables have some space to breathe.

double interval = ((double) (high - low + 1))/bucketCount;

should be

double interval = ((double) (high - low + 1)) / bucketCount;
| improve this answer | |
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.