2
\$\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
5
\$\begingroup\$

Commented code is dead code which should be deleted to add 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;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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