java - 如何减少测试用例中元素数量很大的程序中的迭代次数？

请参考此problem from HackerrankHackerLand国家银行有一个简单的政策，可以警告客户可能存在欺诈性帐户活动。如果客户在特定日期花费的金额连续几天都大于或等于客户的中位数支出，则他们会向客户发送有关潜在欺诈的通知。直到他们至少拥有前几天交易数据的尾数，银行才会向客户发送任何通知。我写了下面的代码。但是，该代码在某些测试用例中有效，并且在某些情况下由于“超时”而终止。谁能告诉我如何改善代码？import java.io.*;import java.math.*;import java.security.*;import java.text.*;import java.util.*;import java.util.concurrent.*;import java.util.regex.*;public class Solution { // Complete the activityNotifications function below. static int activityNotifications(int[] expenditure, int d) { //Delaring Variables int iterations,itr,length,median,midDummy,midL,midR, midDummy2,i,i1,temp,count; float mid,p,q; length = expenditure.length; iterations = length-d; i=0; i1=0; itr=0; count = 0; int[] exSub = new int[d]; while(iterations>0) { // Enter the elements in the subarray while(i1<d) { exSub[i1]=expenditure[i+i1]; //System.out.println(exSub[i1]); i1++; } //Sort the exSub array for(int k=0; k<(d-1); k++) { for(int j=k+1; j<d; j++) { if(exSub[j]<exSub[k]) { temp = exSub[j]; exSub[j] = exSub[k]; exSub[k] = temp; } } } //Printing the exSub array in each iteration for(int l = 0 ; l<d ; l++) { System.out.println(exSub[l]); } i1=0; //For each iteration claculate the median if(d%2 == 0) // even { midDummy = d/2; p= (float)exSub[midDummy]; q= (float)exSub[midDummy-1]; mid = (p+q)/2; //mid = (exSub[midDummy]+exSub [midDummy-1])/2; //System.out.println(midDummy); } else // odd { midDummy2 =d/2; mid=exSub[midDummy2]; //System.out.println(midDummy2); } if(expenditure[itr+d]>=2*mid) { count++; } itr++; i++; iterations--; System.out.println("Mid:"+mid); System.out.println("---------"); } System.out.println("Count:"+count); return count; } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); String[] nd = scanner.nextLine().split(" "); int n = Integer.parseInt(nd[0]); int d = Integer.parseInt(nd[1]); int[] expenditure = new int[n]; String[] expenditureItems = scanner.nextLine().split(" "); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); for (int i = 0; i < n; i++) { int expenditureItem = Integer.parseInt(expenditureItems[i]); expenditure[i] = expenditureItem; } int result = activityNotifications(expenditure, d); bufferedWriter.write(String.valueOf(result)); bufferedWriter.newLine(); bufferedWriter.close(); scanner.close(); }} 最佳答案 性能改进的第一条规则是：如果不需要，则不要提高性能。性能改进通常会导致代码的可读性降低，因此仅应在真正需要时执行。第二条规则是：在进行低级改进之前先改进算法和数据结构。如果需要提高代码的性能，请务必先尝试使用更高效的算法和数据结构，然后再进行低级改进。在您的代码示例中，将是：不要使用BubbleSort，而是尝试使用更高效的算法，例如Quicksort或Mergesort，因为它们使用的时间复杂度是O(n*log(n)，而Bubble排序的时间复杂度是，这在您必须对大型数组进行排序时要慢得多。您可以使用Arrays.sort(int[])来执行此操作。您的数据结构只是数组，因此无法在代码中进行改进。这将使您的代码有相当大的加速，并且不会导致代码无法读取。诸如将简单的计算更改为使用位移位和其他快速计算（如果经常使用很难理解）这样的改进，几乎总会导致代码的速度稍快，但是没有人能够再容易地理解它了。可以应用于您的代码的一些改进（也只会稍微改善性能）是：如果可能，将O(n^2)循环替换为while循环（编译器可以对其进行改进）如果不是完全不需要，请不要在许多文本中使用for（因为对于大文本来说它很慢）尝试使用System.arraycopy复制阵列通常比使用while循环复制要快因此，经过改进的代码可能如下所示（我用注释标记了更改的部分）：import java.io.BufferedWriter;import java.io.FileWriter;import java.io.IOException;import java.util.Arrays;import java.util.Scanner;public class Solution { // Complete the activityNotifications function below. static int activityNotifications(int[] expenditure, int d) { //Delaring Variables int iterations, itr, length, median, midDummy, midL, midR, midDummy2, i, i1, temp, count; float mid, p, q; length = expenditure.length; iterations = length - d; i = 0; i1 = 0; itr = 0; count = 0; int[] exSub = new int[d]; //EDIT: replace while loops with for loops if possible //while (iterations > 0) { for (int iter = 0; iter < iterations; iter++) { //EDIT: here you can again use a for loop or just use System.arraycopy which should be (slightly) fasters // Enter the elements in the subarray /*while (i1 < d) { exSub[i1] = expenditure[i + i1]; //System.out.println(exSub[i1]); i1++; }*/ System.arraycopy(expenditure, i, exSub, 0, d); //EDIT: Don't use bubble sort!!! It's one of the worst sorting algorithms, because it's really slow //Bubble sort uses time complexity O(n^2); others (like merge-sort or quick-sort) only use O(n*log(n)) //The easiest and fastest solution is: don't implement sorting by yourself, but use Arrays.sort(int[]) from the java API //Sort the exSub array /*for (int k = 0; k < (d - 1); k++) { for (int j = k + 1; j < d; j++) { if (exSub[j] < exSub[k]) { temp = exSub[j]; exSub[j] = exSub[k]; exSub[k] = temp; } } }*/ Arrays.sort(exSub); //Printing the exSub array in each iteration //EDIT: printing many results also takes much time, so only print the results if it's really needed /*for (int l = 0; l < d; l++) { System.out.println(exSub[l]); }*/ i1 = 0; //For each iteration claculate the median if (d % 2 == 0) // even { midDummy = d / 2; p = (float) exSub[midDummy]; q = (float) exSub[midDummy - 1]; mid = (p + q) / 2; //mid = (exSub[midDummy]+exSub [midDummy-1])/2; //System.out.println(midDummy); } else // odd { midDummy2 = d / 2; mid = exSub[midDummy2]; //System.out.println(midDummy2); } if (expenditure[itr + d] >= 2 * mid) { count++; } itr++; i++; //iterations--;//EDIT: don't change iterations anymore because of the for loop System.out.println("Mid:" + mid); System.out.println("---------"); } System.out.println("Count:" + count); return count; } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); String[] nd = scanner.nextLine().split(" "); int n = Integer.parseInt(nd[0]); int d = Integer.parseInt(nd[1]); int[] expenditure = new int[n]; String[] expenditureItems = scanner.nextLine().split(" "); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); for (int i = 0; i < n; i++) { int expenditureItem = Integer.parseInt(expenditureItems[i]); expenditure[i] = expenditureItem; } int result = activityNotifications(expenditure, d); bufferedWriter.write(String.valueOf(result)); bufferedWriter.newLine(); bufferedWriter.close(); scanner.close(); }}编辑：如果您没有在每次迭代中对完整的（子）数组进行排序，而是仅删除一个值（不再使用的第一天）并添加新值（即现在被使用）在正确的位置（例如他的答案中提到的@VojtěchKaiser）这将使速度更快，因为对数组进行排序需要时间System.out.println，而在向数组中添加新值时，如果您正在使用搜索树，则已经进行排序的时间仅需O(d*log(d))。使用数组时（如我在下面的示例中所做的那样），它花费时间O(log(d))，因为使用数组时，您需要复制花费线性时间的数组值（例如注释中提到的@dyukha）。因此（再次）可以通过使用更好的算法来进行改进（也可以通过使用搜索树而不是数组来改进此解决方案）。因此，新的解决方案可能如下所示：import java.io.BufferedWriter;import java.io.FileWriter;import java.io.IOException;import java.util.Arrays;import java.util.Scanner;public class Solution { // Complete the activityNotifications function below. static int activityNotifications(int[] expenditure, int d) { //Delaring Variables int iterations, length, midDummy, midDummy2, count;//EDIT: removed some unused variables here float mid, p, q; length = expenditure.length; iterations = length - d; count = 0; //EDIT: add the first d values to the sub-array and sort it (only once) int[] exSub = new int[d]; System.arraycopy(expenditure, 0, exSub, 0, d); Arrays.sort(exSub); for (int iter = 0; iter < iterations; iter++) { //EDIT: don't sort the complete array in every iteration //instead remove the one value (the first day that is not used anymore) and add the new value (of the new day) into the sorted array //sorting is done in O(n * log(n)); deleting and inserting a new value into a sorted array is done in O(log(n)) if (iter > 0) {//not for the first iteration int remove = expenditure[iter - 1]; int indexToRemove = find(exSub, remove); //remove the index and move the following values one index to the left exSub[indexToRemove] = 0;//not needed; just to make it more clear what's happening System.arraycopy(exSub, indexToRemove + 1, exSub, indexToRemove, exSub.length - indexToRemove - 1); exSub[d - 1] = 0;//not needed again; just to make it more clear what's happening int newValue = expenditure[iter + d - 1]; //insert the new value to the correct position insertIntoSortedArray(exSub, newValue); } //For each iteration claculate the median if (d % 2 == 0) // even { midDummy = d / 2; p = exSub[midDummy]; q = exSub[midDummy - 1]; mid = (p + q) / 2; //mid = (exSub[midDummy]+exSub [midDummy-1])/2; //System.out.println(midDummy); } else // odd { midDummy2 = d / 2; mid = exSub[midDummy2]; //System.out.println(midDummy2); } if (expenditure[iter + d] >= 2 * mid) { count++; } } System.out.println("Count:" + count); return count; } /** * Find the position of value in expenditure */ private static int find(int[] array, int value) { int index = -1; for (int i = 0; i < array.length; i++) { if (array[i] == value) { index = i; } } return index; } /** * Find the correct position to insert value into the array by bisection search */ private static void insertIntoSortedArray(int[] array, int value) { int[] indexRange = new int[] {0, array.length - 1}; while (indexRange[1] - indexRange[0] > 0) { int mid = indexRange[0] + (indexRange[1] - indexRange[0]) / 2; if (value > array[mid]) { if (mid == indexRange[0]) { indexRange[0] = mid + 1; } else { indexRange[0] = mid; } } else { if (mid == indexRange[1]) { indexRange[1] = mid - 1; } else { indexRange[1] = mid; } } } System.arraycopy(array, indexRange[0], array, indexRange[0] + 1, array.length - indexRange[0] - 1); array[indexRange[0]] = value; } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); String[] nd = scanner.nextLine().split(" "); int n = Integer.parseInt(nd[0]); int d = Integer.parseInt(nd[1]); int[] expenditure = new int[n]; String[] expenditureItems = scanner.nextLine().split(" "); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); for (int i = 0; i < n; i++) { int expenditureItem = Integer.parseInt(expenditureItems[i]); expenditure[i] = expenditureItem; } int result = activityNotifications(expenditure, d); bufferedWriter.write(String.valueOf(result)); bufferedWriter.newLine(); bufferedWriter.close(); scanner.close(); //Just for testing; can be deleted if you don't need it /*int[] exp = new int[] {2, 3, 4, 2, 3, 6, 8, 4, 5}; int d = 5; activityNotifications(exp, d); int[] exp2 = new int[] {1, 2, 3, 4, 4}; d = 4; activityNotifications(exp2, d);*/ }}