如何减少测试用例中元素数量非常大的程序中的迭代次数？
HackerLand National Bank 有一个简单的政策来警告客户可能的欺诈账户活动。如果客户在某一天花费的金额大于或等于客户连续几天的中位数花费，他们会向客户发送有关潜在欺诈的通知。银行不会向客户发送任何通知，直到他们至少拥有前几天交易数据的尾随数量。
我写了下面的代码。但是，该代码适用于某些测试用例，并且某些测试用例会“因超时而终止”。谁能告诉我如何改进代码？
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;
}
}
开满天机浏览 96回答 2
2回答
-
犯罪嫌疑人X
性能改进的第一条规则是：如果不需要，不要改进性能。性能改进通常会导致代码可读性降低，因此只有在真正需要时才应该这样做。第二条规则是：在低级改进之前改进算法和数据结构。如果您需要提高代码的性能，请在进行低级改进之前始终尝试使用更高效的算法和数据结构。在您的代码示例中是：不要使用BubbleSort，但尝试使用更高效的算法，如Quicksort或Mergesort，因为它们使用时间复杂度，O(n*log(n)而 Bubble sort 的时间复杂度O(n^2)在您必须进行大排序时要慢得多阵列。您可以使用Arrays.sort(int[])来执行此操作。您的数据结构只是数组，因此无法在您的代码中进行改进。这将为您的代码提供相当大的加速，并且不会导致无法再读取代码。诸如使用移位和其他快速计算（如果经常使用则很难理解）将简单计算更改为稍微更快的计算等改进几乎总是会导致代码只是稍微快一点，但没有人能够再轻松理解它.可以应用于您的代码的一些改进（也只会略微提高性能）是：while如果可能，用循环替换for循环（它们可以由编译器改进）System.out.println如果不是完全需要，请不要用于许多文本（因为它对于大文本来说很慢）尝试使用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ěch Kaiser 在他的回答中提到的那样）这将使它更快，因为对数组进行排序需要时间，而将新值添加到数组中时，如果您使用搜索树，O(d*log(d))则已经排序的新值只需要时间。O(log(d))使用数组时（就像我在下面的示例中所做的那样）需要时间O(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);*/ }} -
白板的微信
您主要担心的是您在每次迭代中都对部分数组进行排序，从而使问题的总复杂度增加O(nd log(d)) ，对于大的d值，这可能会变得非常棘手。您想要的是在迭代之间对数组进行排序并对更改的值进行排序/排序。为此，您将实施二叉搜索树（BST）或其他一些平衡选项（AVL，...），执行O(log(d))删除最旧的值，然后执行O(log(d))插入新值, 并简单地在中间寻找中位数。总的渐近复杂度为O(n log(d))，据我所知这是你能得到的最好的——其余的优化是低级的脏工作。看看 java https://docs.oracle.com/javase/10/docs/api/java/util/TreeSet.html，它应该处理大部分工作，但请记住底层结构是由比数组慢的对象组成。
随时随地看视频慕课网APP
相关分类
Java