Тайм-аут Исключение при сортировке большего списка - PullRequest
0 голосов
/ 22 мая 2018

Я пытаюсь решить проблему большой сортировки из HackerRank .У меня есть ниже решение для этого:

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;
}

Хотя мое решение работает, если ввод короткий, но для длинного ввода оно дает TimeoutException

Как я узнаю, тестовый случай, который вызываетпроблема заключается в следующем:

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

Итак, у меня есть вопрос относительно того, Collections.sort(newValues); погоду ли это вызывает проблему, поскольку есть огромные числа для сортировки, так что это может занять время или что-то еще?

Ниже приведена привязка к выводу:

enter image description here

И это то, что нужно для ввода

enter image description here

Ответы [ 2 ]

0 голосов
/ 22 мая 2018

Позволяет разбить ваш код на разделы:

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])));
}

Производительность этого раздела зависит от двух вещей:

  1. Размер unsorted.
  2. Длина строк в sorted.

Причина, по которой длины строк имеют значение, заключается в том, что преобразование десятичной строки во внутреннее представление, используемое BigInteger, является дорогостоящим.Для одной строки с D цифрами сложность времени равна O (D 2 ).Таким образом, общая сложность составляет O (ND 2 ).

Collections.sort(newValues);

Этот шаг сортировки обычно O (NlogN) или O (NlogND) в худшем случае 1 .

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

Это O (ND 2 ) из-за вызова toString().

Итак, в целом мы имеем типичную сложность:O (ND 2 + NlogN).

( Анализ сложности довольно груб и готов. Если я допустил какие-либо серьезные ошибки, пожалуйста, прокомментируйте ... )


Из вышеприведенного анализа видно, что стоимость преобразований из строк в BigInteger и обратно может доминировать в стоимости сортировки.Особенно, если большинство чисел имеет много цифр.

Можем ли мы избежать этого?Да!Можно написать Comparator<String>, который может сравнивать десятичные числа без преобразования их в двоичные.

Второе, что мы могли бы оптимизировать, - это сортировка.

  • В некоторыхВ некоторых случаях метод Collections::sort фактически копирует коллекцию в массив, сортирует массив, а затем копирует отсортированный массив обратно в список.

  • Существует еще один метод с именем Arrays::sort.Если вы воспользуетесь этим, вы сможете избежать одного или нескольких шагов копирования списка <-> массива.

  • Существует еще один метод с именем Arrays::parallelSort.Если есть доступные ядра C, использование этого метода может привести к (до) ускорению C-кратного.


1 - Типичный случай возникает, когда числа всписок значительно отличается, и вы можете сравнить их пару в O (1).Наихудший случай - когда все числа одинаковы (или близки), и для сравнения обычно используется O (D).

0 голосов
/ 22 мая 2018

Вместо использования BigInteger, сортируйте String s напрямую.

Использование естественного упорядочивания String s не будет работать, так как 2 придет после 10.

Тем не менее, вы можете определить свои собственные Comparator<String>, которые поддерживают числовые String s.Этот метод Comparator compare сначала сравнивает длины String s.Он вернет -1, если первая строка короче, и 1, если она длиннее.

Если два String имеют одинаковую длину, вы бы перебрали символы двух String и сравнили быодин персонаж за раз.Если все символы равны, вы возвращаете 0. В противном случае вы возвращаете -1 или 1, в зависимости от того, меньше или больше первый символ, для которого String s, первый String.

Вот возможная реализация Comparator compare метода:

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;
}

Тогда:

static String[] bigSorting(String[] unsorted) {
    Comparator<String> comparator = ... // the above mentioned Comparator
    Arrays.sort(unsorted, comparator);
    return unsorted;
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...