Оптимизация времени выполнения Java Алгоритм логики

Question

Я разработал приведенный ниже лог c, но он не может быть выполнен в данный момент Это займет более 4 секунд для набора тестовых данных из 100 000 номеров. Может кто-то предложить или оптимизировать его для запуска в течение 0,2 секунд для большого набора данных. Ниже приводится описание проблемы:

Радиоцентр получает некоторые сигналы и должен классифицировать их по частоте.

Центру известны стандартные частоты. Они идентифицировали

различных сигналов, которые должны быть классифицированы. Учитывая стандартные частоты сигналов freq_standard и частоты сигналов, подлежащих классификации freq_signal, вы можете помочь радиоцентру идентифицировать их?

Сигнал X принадлежит стандартному сигналу Y, если частота X ближе к частоте Y чем на любую другую частоту. Если оно равноудалено от двух известных частот, то выбирается сигнал с более высокой частотой.

Рассмотрим, например, freq_standard = [2, 3, 1, 4, 8] и freq_classify = [1, 5, 6]. Частоты 1 и 5 относятся к стандартным частотам 1 (индекс = 3) и 4 (индекс = 4) соответственно. Поскольку 6 равноудалено от двух стандартных частот 4 и 8, выберите более высокую частоту 8 (индекс = 5). Соответствующие классификации: [3, 4, 5].

Описание функции:

Завершите функцию classifySignals в редакторе ниже. Функция должна возвращать целочисленный массив, обозначающий классификацию каждой частоты.

classifySignals имеет два параметра -

• freq_standard: целочисленный массив

• freq_signals: целочисленный массив

Формат ввода:

Первая строка ввода содержит 2 пробела -разделенные целые числа: n,q - количество строк и количество запросов.

Вторая строка содержит разделенные пробелом целые числа, массив freq_standard.

Следующая строка содержит q целые числа через пробел, массив freq_signals.

Ограничения:

• n <= 10 <sup>5

• q <= 10 <sup>5

• | freq_standard _i | <= 10 <sup>9

• | freq_signals _i | <= 10 <sup>9

Формат вывода:

Печать q строк: каждая строка должна содержать целое число, представляющее индекс стандартной частоты, соответствующий данному сигналу. Существует заглушка кода для обработки ввода / вывода, если вы решите ее использовать.

Пример ввода 0:

5 5    
7 1 12 9 15    
2 9 2000 13 4

Пример вывода 0:

2
4
5
3
1

Моя попытка:

    import java.io.BufferedReader;
    import java.io.BufferedWriter;
    import java.io.FileWriter;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;

    class Result1 {

/*
 * Complete the 'classifySignals' function below.
 *
 * The function is expected to return an INTEGER_ARRAY. The function accepts
 * following parameters: 1. INTEGER_ARRAY freq_standard 2. INTEGER_ARRAY
 * freq_signals
 */

public static List<Integer> classifySignals(List<Integer> freq_standard, List<Integer> freq_signals) {
    List<Integer> out = new ArrayList<>();
    int match = 0;
    int n = freq_standard.size();
    int q = freq_signals.size();
    List<Integer> freq_standard_unordered = new ArrayList<>(freq_standard);
    Collections.sort(freq_standard);

    for (int i = 0; i < q; i++) {
        int signalToCompare = freq_signals.get(i);
        if (signalToCompare < freq_standard.get(0)) {
            match = freq_standard.get(0);
            out.add(freq_standard_unordered.indexOf(match) + 1);
            continue;
        }
        if (signalToCompare > freq_standard.get(n - 1)) {
            match = freq_standard.get(n - 1);
            out.add(freq_standard_unordered.indexOf(match) + 1);
            continue;
        }
        int j = 0, k = n, mid = 0;
        while (j < k) {
            mid = (j + k) / 2;

            if (freq_standard.get(mid) == signalToCompare) {
                match = freq_standard.get(mid);
                break;
            }

            if (signalToCompare < freq_standard.get(mid)) {
                match = mid - 1 > 0
                        ? findClosest(freq_standard.get(mid), freq_standard.get(mid - 1), signalToCompare)
                        : freq_standard.get(mid);
                k = mid;
            } else {
                match = mid + 1 < n
                        ? findClosest(freq_standard.get(mid + 1), freq_standard.get(mid), signalToCompare)
                        : freq_standard.get(mid);
                j = mid + 1;
            }

        }
        out.add(freq_standard_unordered.indexOf(match) + 1);
    }

    return out;
}

public static int findClosest(int n, int m, int target) {
    if (Math.abs(n - target) == Math.abs(m - target)) {
        return n;
    }
    if (Math.abs(n - target) > Math.abs(m - target)) {
        return m;
    } else {
        return n;
    }
}

    }

    public class GFG {
        public static void main(String[] args) throws IOException {
            BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

    String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

    int n = Integer.parseInt(firstMultipleInput[0]);

    int q = Integer.parseInt(firstMultipleInput[1]);

    String[] fTemp = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

    List<Integer> f = new ArrayList<>();

    for (int i = 0; i < n; i++) {
        int fItem = Integer.parseInt(fTemp[i]);
        f.add(fItem);
    }

    String[] FTemp = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

    List<Integer> F = new ArrayList<>();

    for (int i = 0; i < q; i++) {
        int FItem = Integer.parseInt(FTemp[i]);
        F.add(FItem);
    }

    List<Integer> ans = Result1.classifySignals(f, F);

    System.out.println(ans);

}
}

Answer 1

Попробуйте это, братан, на моем компьютере потребовалось 0,1 с, чтобы протестировать набор данных из числа 1 лакха. это просто тестовая логика c, если она работает правильно, вы можете оптимизировать ее.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

public class a4_test {
    public static void main(String[] args) {
        // sampleTest1
        int[] freq_standard = new int[]{1, 2};
        int[] freq_signals = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        // sampleTest2
        freq_standard = new int[]{7, 1, 12, 9, 15};
        freq_signals = new int[]{2, 9, 2000, 13, 4};

//         randomArray For Testing
        freq_standard = randomArray((int) Math.pow(10,5),(int) Math.pow(10,9));
        freq_signals = randomArray((int) Math.pow(10,5),(int) Math.pow(10,9));
        System.out.println("standard:" + Arrays.toString(freq_standard));
        System.out.println("signals" + Arrays.toString(freq_signals));

        long start = System.currentTimeMillis();
        int[] classify = classifySignals(freq_standard, freq_signals);
        long end = System.currentTimeMillis();
        System.out.println("time cost:" + (end - start));
        System.out.println("classifyArray:" + Arrays.toString(classify));
    }

    // mainMethod
    public static int[] classifySignals(int[] freq_standard, int[] freq_signals) {
        Map<Integer, Integer> map = freq_sort(freq_standard);

        Arrays.sort(freq_standard); // there are better sort algorithms for a lower time complexity,fix me~

        // a caching classifyArray,should be construct with 'n'
        ArrayList<Integer> list = new ArrayList<>((int) Math.pow(10, 5));
        for (int freq_signal : freq_signals) {
            int index = findTarget(freq_standard, freq_signal);
            list.add(map.get(freq_standard[index]));    // get original index in original freq_standard[]
        }

        // truly classifyArray，the problem asked a int[] to return
        int[] classifyArray = new int[list.size()];
        for (int i = 0; i < classifyArray.length; i++) {
            classifyArray[i] = list.get(i);
        }
        return classifyArray;
    }

    // record the original index of freq_standard
    public static Map<Integer, Integer> freq_sort(int[] freq_standard) {
        Map<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < freq_standard.length; i++) {
            map.put(freq_standard[i], i + 1);   // ok,the problem defined 1 is the begin of array index
        }
        return map;
    }

    // find targetIndex
    private static int findTarget(int[] array, int targetNum) {
        // boundaryCheck
        if (targetNum <= array[0]) {
            return 0;
        } else if (targetNum >= array[array.length - 1]) {
            return array.length - 1;
        }
        // binary search
        int left = 0, right = array.length - 1;
        for (; right - left > 1; ) {
            int pivot = (right + left) / 2;
            int middle = array[pivot];
            if (targetNum == middle) {
                return pivot;
            }
            if (targetNum > middle) {
                left = pivot + 1;
            } else {
                right = pivot - 1;
            }
        }
        int index = targetNum < ((array[right] + array[left]) * 1.0 / 2) ?
                left : right;
//        System.out.println("target:" + targetNum + ",leftV:" + array[left] + ",rightV:" + array[right] + ",indexV:" + array[index]);
        return index;
    }

    // generate random array to test
    public static int[] randomArray(int maxMember, int maxValue) {
        int[] randomArray = new int[maxMember];
        for (int i = 0; i < maxMember; i++) {
            randomArray[i] = (int) (Math.random() * maxValue);
        }
        return randomArray;
    }
}

Answer 2

У вас есть

out.add(freq_standard_unordered.indexOf(match) + 1);

, который находит индекс совпадения, который принимает O (n) в самом худшем случае сам по себе. Это также внутри al oop, что делает его O (n ² ).

Ваша идея бинарного поиска верна. Но при сортировке вы не можете потерять индексы элементов, что на самом деле и заставляет вас делать out.add(freq_standard_unordered.indexOf(match) + 1);

Чтобы избежать этого, вы можете создать класс (или иметь двумерный массив), который будет хранить значение как а также индексировать и делать бинарный поиск по ним соответственно. Таким образом, вы можете правильно оценить фактический индекс элемента в его первоначальном порядке. Ниже описано, как я это сделал (обратите внимание, что в нем могут быть некоторые ненужные проверки, но вы все равно получите представление об общей стратегии) ​​

Фрагмент:

class Result {
    static class Data{
        int val,actual_index;
        Data(int val,int index){
            this.val = val;
            this.actual_index = index;
        }
    }
    public static List<Integer> classifySignals(List<Integer> freq_standard, List<Integer> freq_signals) {
        Data[] d = new Data[freq_standard.size()];
        for(int i=0;i<d.length;++i) d[i] = new Data(freq_standard.get(i),i);
        Arrays.sort(d,new Comparator<Data>(){
            public int compare(Data d1,Data d2){
                if(d1.val <= d2.val) return -1;
                return 1; // not doing d1.val - d2.val to avoid overflows(although irrelevant here)
            }
        });    

        int size = freq_signals.size();        
        List<Integer> ans = new ArrayList<>();
        for(int i = 0;i < size; ++i){
            int ele = freq_signals.get(i);
            int index = getClosest(d,freq_standard,ele);
            ans.add(index + 1);
        }

        return ans;
    }

    private static int getClosest(Data[] d,List<Integer> freq_standard,int ele){
        int index = -1;
        int low = 0,high = d.length - 1;
        while(low <= high){
            int mid = low + (high - low) / 2;
            if(d[mid].val == ele) return d[mid].actual_index;
            if(d[mid].val > ele){
                if(index == -1 || Math.abs(freq_standard.get(d[index].actual_index) - ele) > Math.abs(d[mid].val - ele)) index = mid;
                high = mid - 1;
            }else{
                if(index == -1 || Math.abs(freq_standard.get(d[index].actual_index) - ele) > Math.abs(d[mid].val - ele)) index = mid;
                low = mid + 1;
            }
        }

        if(index + 1 < d.length){
            int current_closest = freq_standard.get(d[index].actual_index);
            int next_closest = freq_standard.get(d[index + 1].actual_index);
            if(Math.abs(ele - current_closest) == Math.abs(ele - next_closest)) return d[index + 1].actual_index;
        }

        return d[index].actual_index;
    }    
}