CODEWITHSUNDEEP
javasortingcollections
NarendraR
NarendraR

Reputation: 7708

Timeout Exception while sorting bigger List

I'm trying to solve big-sorting problem from HackerRank. I have below solution for that:

static String[] bigSorting(String[] unsorted) {

    List<BigInteger> newValues = new ArrayList<BigInteger>();

    String[] newValuesArray = new String[unsorted.length];
    for (int i = 0; i < unsorted.length; i++) {
        newValues.add(new BigInteger((unsorted[i])));
    }

    Collections.sort(newValues);

    for (int i = 0; i < newValues.size(); i++) {
        newValuesArray[i] = newValues.get(i).toString();
    }
    return newValuesArray;
}

Although my solution is working if input is short but for lengthy input it giving the TimeoutException

As I come to know the testcase which causing issue is : 

total input = 7693
And Values :
123121
22
2
23123
12312
2
8400195277734975809347292766456055069919837818826921595732345474832683881284408515491064519242069257576624629524016550879441266062080977804902962370685876553901611732
And So on...until 7693 values

So I have question here regarding Collections.sort(newValues); weather it causing the issue as there is huge numbers to be sort so it might be taking time or something else ?

Please find below snap regarding output :

enter image description here

And this is what it takes as input

enter image description here

Upvotes: 0

Views: 441

Answers (2)

Stephen C
Stephen C

Reputation: 718798

Lets break your code into sections:

List<BigInteger> newValues = new ArrayList<BigInteger>();

String[] newValuesArray = new String[unsorted.length];
for (int i = 0; i < unsorted.length; i++) {
    newValues.add(new BigInteger((unsorted[i])));
}

The performance of this section depends on two things:

  1. The size of unsorted.
  2. The lengths of the strings in sorted.

The reason that string lengths matter is that converting a decimal string to the internal representation used by BigInteger is expensive. For a single string with D digits, the time complexity is O(D2). So the overall complexity is O(ND2).

Collections.sort(newValues);

This sorting step is typically O(NlogN), or O(NlogND) in the worst case1.

for (int i = 0; i < newValues.size(); i++) {
    newValuesArray[i] = newValues.get(i).toString();
}

This is O(ND2) because of the toString() call.

So looking at this overall we have a typical complexity of O(ND2 + NlogN).

(The complexity analysis about is pretty rough and ready. If I've made any major mistakes, please comment ...)

One thing we can see from the above analysis is that the cost of the conversions from strings to BigInteger and back could be dominating the sorting cost. Especially if the most numbers have many digits.

Can we avoid this? Yes! It is possible to write a Comparator<String> that can compare decimal numbers without converting them to binary.

The second thing we could optimize is the sorting.

  • In some cases, the Collections::sort method actually copies the collection to an array, sorts the array, then copies the sorted array back to the list.

  • There another method called Arrays::sort. If you use this, you may be able to avoid one or more list <-> array copying steps.

  • There is yet another method called Arrays::parallelSort. If there are C cores available, using this method could give (up to) C-fold speedup.

1 - The typical case is occurs when the numbers in the list are significantly different, and you can typically compare a pair of them in O(1). The worst case is when the nnumbers are all the same (or close) and comparison typically is O(D).

Upvotes: 1

Eran
Eran

Reputation: 393821

Instead of using BigInteger, sort the Strings directly.

Using the natural ordering of Strings won't work, since 2 will come after 10.

However, you can define your own Comparator<String> that supports numeric Strings. That Comparator's compare method will first compare the Strings lengths. It will return -1 if the first String is shorter and 1 if it's longer.

If the two Strings have the same length, you would iterate on the characters of the two Strings and compare one character at a time. If all the characters are equal, you return 0. Else you return -1 or 1 depending on whether the first character for which the Strings are different is smaller or larger in the first String.

Here's a possible implementation of the Comparator's compare method:

public int compare(String one, String two) {
    if (one.length != two.length)
        return one.length() - two.length();       
    for (int i = 0; i < one.length; i++) {
        char c1 = one.charAt(i);
        char c2 = two.charAt(i);
        if (c1 != c2) {
            return c1 - c2;
        }
    }
    return 0;
}

Then: 

static String[] bigSorting(String[] unsorted) {
    Comparator<String> comparator = ... // the above mentioned Comparator
    Arrays.sort(unsorted, comparator);
    return unsorted;
}

Upvotes: 2

Related Questions