代码之家 › 专栏 › 技术社区 › NarendraR TheSociety

排序较大列表时出现超时异常

collections sorting java

-1

NarendraR TheSociety · 技术社区 · 6 年前

我正在努力解决 big-sorting 问题来自 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); 天气是不是会引起这个问题,因为有大量的数据需要整理,所以可能需要时间或者其他什么?

请在下面找到有关输出的快照:

这就是它作为输入的东西

2 回复 | 直到 6 年前

Stephen C 6 年前

让我们将代码分成若干部分:

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

本节的性能取决于两个方面:

的大小 unsorted .
弦的长度 sorted 。

字符串长度之所以重要,是因为将十进制字符串转换为 BigInteger 很贵。对于具有d位数的单个字符串,时间复杂性为o(d ^二 )所以总的复杂性是 ^二 )

Collections.sort(newValues);

在最坏的情况下,此排序步骤通常是O(nlogn)或O(nlognd)。 ^一 .

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

这是O(nd) ^二 )因为 toString() 呼叫。

所以从整体上看,我们有一个典型的O(nd)复杂性 ^二 +取消登录)。

( 关于的复杂性分析非常粗略和准备。如果我犯了什么大错误,请评论… )

从上面的分析中我们可以看到,从字符串到 大整数 然后回来 可能是统治 分拣成本。尤其是如果大多数数字都有很多位数。

我们能避免这个吗?对!可以写一个 Comparator<String> 它可以比较十进制数而不将其转换为二进制数。

我们可以优化的第二件事是排序。

在某些情况下, Collections::sort 方法实际将集合复制到数组,对数组进行排序,然后将排序后的数组复制回列表。
有另一个方法调用 Arrays::sort . 如果使用此选项,则可以避免一个或多个列表复制步骤。
还有另一个方法 Arrays::parallelSort . 如果有可用的C核心,使用这种方法可以放弃(最多)C倍加速。

^{1-典型情况是当列表中的数字显著不同时发生,您通常可以在o(1)中比较一对数字。最坏的情况是,当n个数都相同(或接近)时,比较通常是o(d)。}

Eran 6 年前

而不是使用 BigInteger ,排序 String 直接。

使用的自然顺序 字符串 S不起作用,因为10点后会有2个。

但是,您可以定义自己的 Comparator<String> 支持数字 字符串 S.那 Comparator 的 compare 方法将首先比较 字符串 S长度。如果第一个字符串较短,则返回-1;如果较长,则返回1。

如果两个 弦 s的长度相同,您将迭代这两个字符 字符串 并一次比较一个字符。如果所有字符都相等,则返回0。否则返回-1或1,具体取决于 弦 S是不同的,在第一个是小的还是大的 字符串 .

下面是 比较器 的 比较 方法:

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