HackerLand National Bank 有一個(gè)簡(jiǎn)單的政策來警告客戶可能的欺詐賬戶活動(dòng)。如果客戶在某一天花費(fèi)的金額大于或等于客戶連續(xù)幾天的中位數(shù)花費(fèi)，他們會(huì)向客戶發(fā)送有關(guān)潛在欺詐的通知。銀行不會(huì)向客戶發(fā)送任何通知，直到他們至少擁有前幾天交易數(shù)據(jù)的尾隨數(shù)量。我寫了下面的代碼。但是，該代碼適用于某些測(cè)試用例，并且某些測(cè)試用例會(huì)“因超時(shí)而終止”。誰能告訴我如何改進(jìn)代碼？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; }}
2 回答
犯罪嫌疑人X
TA貢獻(xiàn)2080條經(jīng)驗(yàn) 獲得超4個(gè)贊
性能改進(jìn)的第一條規(guī)則是：如果不需要，不要改進(jìn)性能。
性能改進(jìn)通常會(huì)導(dǎo)致代碼可讀性降低，因此只有在真正需要時(shí)才應(yīng)該這樣做。
第二條規(guī)則是：在低級(jí)改進(jìn)之前改進(jìn)算法和數(shù)據(jù)結(jié)構(gòu)。
如果您需要提高代碼的性能，請(qǐng)?jiān)谶M(jìn)行低級(jí)改進(jìn)之前始終嘗試使用更高效的算法和數(shù)據(jù)結(jié)構(gòu)。在您的代碼示例中是：不要使用BubbleSort，但嘗試使用更高效的算法，如Quicksort或Mergesort，因?yàn)樗鼈兪褂脮r(shí)間復(fù)雜度，O(n*log(n)而 Bubble sort 的時(shí)間復(fù)雜度O(n^2)在您必須進(jìn)行大排序時(shí)要慢得多陣列。您可以使用Arrays.sort(int[])來執(zhí)行此操作。
您的數(shù)據(jù)結(jié)構(gòu)只是數(shù)組，因此無法在您的代碼中進(jìn)行改進(jìn)。
這將為您的代碼提供相當(dāng)大的加速，并且不會(huì)導(dǎo)致無法再讀取代碼。諸如使用移位和其他快速計(jì)算（如果經(jīng)常使用則很難理解）將簡(jiǎn)單計(jì)算更改為稍微更快的計(jì)算等改進(jìn)幾乎總是會(huì)導(dǎo)致代碼只是稍微快一點(diǎn)，但沒有人能夠再輕松理解它.
可以應(yīng)用于您的代碼的一些改進(jìn)（也只會(huì)略微提高性能）是：
while如果可能，用循環(huán)替換for循環(huán)（它們可以由編譯器改進(jìn)）System.out.println如果不是完全需要，請(qǐng)不要用于許多文本（因?yàn)樗鼘?duì)于大文本來說很慢）嘗試使用System.arraycopy復(fù)制數(shù)組，這通常比使用 while 循環(huán)復(fù)制更快
因此，您的改進(jìn)代碼可能如下所示（我用注釋標(biāo)記了更改的部分）：
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();
}
}
編輯：
如果您不在每次迭代中對(duì)完整（子）數(shù)組進(jìn)行排序，而是僅刪除一個(gè)值（不再使用的第一天）并添加一個(gè)新值（不再使用的新日期），則可以使解決方案更快現(xiàn)在使用）在正確的位置（就像@Vojtěch Kaiser 在他的回答中提到的那樣）
這將使它更快，因?yàn)閷?duì)數(shù)組進(jìn)行排序需要時(shí)間，而將新值添加到數(shù)組中時(shí)，如果您使用搜索樹，O(d*log(d))則已經(jīng)排序的新值只需要時(shí)間。O(log(d))使用數(shù)組時(shí)（就像我在下面的示例中所做的那樣）需要時(shí)間O(d)，因?yàn)槭褂脭?shù)組時(shí)您需要復(fù)制需要線性時(shí)間的數(shù)組值（如評(píng)論中提到的@dyukha）。因此（再次）可以通過使用更好的算法來進(jìn)行改進(jìn)（也可以通過使用搜索樹而不是數(shù)組來改進(jìn)此解決方案）。
所以新的解決方案可能是這樣的：
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);*/
}
}
白板的微信
TA貢獻(xiàn)1883條經(jīng)驗(yàn) 獲得超3個(gè)贊
您主要擔(dān)心的是您在每次迭代中都對(duì)部分?jǐn)?shù)組進(jìn)行排序，從而使問題的總復(fù)雜度增加O(nd log(d)) ，對(duì)于大的d值，這可能會(huì)變得非常棘手。
您想要的是在迭代之間對(duì)數(shù)組進(jìn)行排序并對(duì)更改的值進(jìn)行排序/排序。為此，您將實(shí)施二叉搜索樹（BST）或其他一些平衡選項(xiàng)（AVL，...），執(zhí)行O(log(d))刪除最舊的值，然后執(zhí)行O(log(d))插入新值, 并簡(jiǎn)單地在中間尋找中位數(shù)?？偟臐u近復(fù)雜度為O(n log(d))，據(jù)我所知這是你能得到的最好的——其余的優(yōu)化是低級(jí)的臟工作。
看看 java https://docs.oracle.com/javase/10/docs/api/java/util/TreeSet.html，它應(yīng)該處理大部分工作，但請(qǐng)記住底層結(jié)構(gòu)是由比數(shù)組慢的對(duì)象組成。
添加回答
舉報(bào)
0/150
提交
取消