java - 当测试用例中的元素数量非常大时，如何减少程序中的迭代次数？

Question

请引用此problem from Hackerrank

HackerLand National Bank 制定了一项简单的政策，用于警告客户可能存在的欺诈账户 Activity 。如果客户在特定日期的支出金额大于或等于客户在过去几天的支出中位数，他们会向客户发送有关潜在欺诈的通知。银行不会向客户发送任何通知，除非他们至少拥有前几天的交易数据的跟踪数据。

我编写了以下代码。但是，该代码对于某些测试用例有效，并且对于某些测试用例“由于超时而终止”。谁能告诉我如何改进代码？

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

Answer 1

关于性能改进的第一条规则是:如果不需要就不要改进性能。

性能改进通常会导致代码可读性较差，因此只有在真正需要时才应该这样做。

第二条规则是:在低级改进之前改进算法和数据结构。

如果您需要提高代码的性能，请在进行低级改进之前始终尝试使用更高效的算法和数据结构。在您的代码示例中，这将是: 不要使用 BubbleSort ，但尝试使用更有效的算法，例如 Quicksort或Mergesort ，因为它们使用 O(n*log(n) 的时间复杂度，而冒泡排序的时间复杂度为 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);*/
    }
}