Java 线程中的 ArrayList 异常 "main" java.lang.NegativeArraySizeException: -28

Question

我对排序算法有疑问。我正是使用这个 TimSort 来排序 https://www.geeksforgeeks.org/timsort/ (Java)。例如，我正在前 2500 行的循环中读取 CSV 文件。

这是我的阅读代码：

    private void readFile(){
        try{
            int i = 0;
            BufferedReader csvReader = new BufferedReader(new FileReader(this.filename));
            while ((row = csvReader.readLine()) != null){
                String[] entry = row.split(",(?=(?:[^\"]*\"[^\"]*\")*[^\"]*$)", -1);
                if(i > 0 && i <= 2500){
                    int price = Integer.parseInt(entry[5]);
                    entries.add(price);
                }
                i++;
            }
            csvReader.close();

        }catch(Exception e){
            e.printStackTrace();
        }
    }

之后我以这种方式将字符串转换为 int[] Arraylist：

public int[] convertArrayList(){
    ArrayList<Integer> arrayList = this.entries;
    int[] converted = new int[arrayList.size()];
    for(int i=1; i < converted.length; i++){
        converted[i] = arrayList.get(i);
    }
    return converted;
}

我主要有：

    private static synchronized void getPrices(){
        try{
            File dataset = new File("src/CSV/Schools.csv");
            CSVReader reader = new CSVReader(dataset.getCanonicalPath());
            prices = reader.convertArrayList();
        } catch(Exception e){
            e.printStackTrace();
        }
    }

然后运行它：

    getPrices();
    int n = prices.length;
    System.out.println(n);

    Instant start = Instant.now();
    System.out.print("Given Array is\n");
    GFG.printArray(prices, n);
    Instant end = Instant.now();

    System.out.println("Time for executing the unsorted array: " + Duration.between(start, end).toNanos());


    GFG.timSort(prices, n);

    Instant start2 = Instant.now();
    System.out.print("\nAfter Sorting Array is\n");
    GFG.printArray(prices, n);
    Instant end2 = Instant.now();

    System.out.println("Time for executing the sorted array: " + Duration.between(start2, end2).toNanos());

事情是这样的 如果我运行将循环更改为 i > 0 && i <= 1000 的代码可以正常工作。但是，如果我采用更大的数字，如 2500 或 5000，我会收到以下错误：

Exception in thread "main" java.lang.NegativeArraySizeException: -28
at GFG.merge(TimSort.java:32)
at GFG.timSort(TimSort.java:111)
at Main.main(Main.java:27)

它引用了 TimSort 算法中的合并方法...我无法解决这个问题，请问有什么想法吗？

Answer 1

可能是因为您链接到的 TimSort 算法实现有问题。

List.sort、Collections.sort 和 Arrays.sort(T[]) 都已经使用了 timsort。无需从随机站点复制代码即可使用 TimSort。实用方法 java.util.Arrays.sort(int[]) 使用双主元排序。我认为这具有更好的性能特征，因此可以用来代替 timsort。

如果您想了解您链接到的 timsort 代码，请忘记您粘贴的所有代码，专注于您链接到的 timsort impl，然后调试它。

Java 线程中的 ArrayList 异常 "main" java.lang.NegativeArraySizeException: -28

Java ArrayList Exception in thread "main" java.lang.NegativeArraySizeException: -28

java

csv

sorting

timsort