Java算法执行时间优化请求：10万级数据需压缩至0.2秒内

Hey there! I totally get your frustration with the slow runtime—processing 100k entries in 4+ seconds is way too sluggish for this use case. The root cause here is definitely those linear indexOf lookups, which push the time complexity to O(n*m) (n = number of signals, m = number of standard frequencies). Let's fix this with a smarter approach that drops the complexity to O(n log m)—easily getting you under that 0.2s target.

The Core Idea #

Instead of checking every standard frequency for each signal, we'll:

1. Preprocess the standard frequencies by sorting them (while keeping track of their original 1-based indices)
2. Use binary search to quickly pin down the closest standard frequency for each signal
3. Handle the "equal distance" tiebreaker by picking the higher frequency (and its original index)

Step-by-Step Implementation #

1. Helper Class to Track Frequency + Original Index #

First, we need a way to link each standard frequency to its original position without losing data during sorting:

class FrequencyWithIndex {
    double frequency;
    int originalIndex;

    public FrequencyWithIndex(double frequency, int originalIndex) {
        this.frequency = frequency;
        this.originalIndex = originalIndex;
    }
}

2. Preprocess the Standard Frequencies #

Sort the standard array once upfront—this one-time cost pays off massively for large datasets:

// Convert standard frequencies to our helper class (avoiding indexOf here!)
List<FrequencyWithIndex> sortedStandards = new ArrayList<>();
for (int i = 0; i < freq_standard.length; i++) {
    sortedStandards.add(new FrequencyWithIndex(freq_standard[i], i + 1)); // original index is 1-based
}

// Sort the list by frequency
Collections.sort(sortedStandards, Comparator.comparingDouble(f -> f.frequency));

3. Binary Search for Closest Match #

For each signal, use binary search to find its insertion point in the sorted standards, then compare neighboring candidates to find the closest match:

public static int[] classifySignals(double[] freq_standard, double[] freq_signals) {
    // Preprocess sorted standards with original indices
    List<FrequencyWithIndex> sortedStandards = new ArrayList<>();
    for (int i = 0; i < freq_standard.length; i++) {
        sortedStandards.add(new FrequencyWithIndex(freq_standard[i], i + 1));
    }
    Collections.sort(sortedStandards, Comparator.comparingDouble(f -> f.frequency));

    int[] result = new int[freq_signals.length];
    for (int i = 0; i < freq_signals.length; i++) {
        result[i] = findClosestStandard(freq_signals[i], sortedStandards);
    }
    return result;
}

private static int findClosestStandard(double signal, List<FrequencyWithIndex> sortedStandards) {
    int left = 0;
    int right = sortedStandards.size() - 1;

    // Edge case: signal is smaller than all standards
    if (signal <= sortedStandards.get(left).frequency) {
        return sortedStandards.get(left).originalIndex;
    }
    // Edge case: signal is larger than all standards
    if (signal >= sortedStandards.get(right).frequency) {
        return sortedStandards.get(right).originalIndex;
    }

    // Binary search to find first standard >= signal
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (sortedStandards.get(mid).frequency < signal) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    // Compare the two closest candidates (left-1 and left)
    FrequencyWithIndex lowerCandidate = sortedStandards.get(left - 1);
    FrequencyWithIndex upperCandidate = sortedStandards.get(left);

    double distToLower = signal - lowerCandidate.frequency;
    double distToUpper = upperCandidate.frequency - signal;

    // Tie goes to the higher frequency (upper candidate)
    if (distToLower < distToUpper) {
        return lowerCandidate.originalIndex;
    } else {
        return upperCandidate.originalIndex;
    }
}

Why This Works #

• Preprocessing: Sorting takes O(m log m) time—negligible compared to processing 100k signals.
• Binary Search: Each signal lookup takes O(log m) time. For 100k signals and m=1k standards, that's 100,000 * 10 = 1 million operations (vs. 100 million with linear search).
• Edge Cases: We explicitly handle signals outside the standard frequency range to avoid missing any cases.

Performance Expectation #

With this implementation, you'll see runtime drop drastically—even with 100k signals, it's easily going to land under 0.2 seconds. The key is eliminating all linear lookups and leveraging binary search's logarithmic time complexity.

内容的提问来源于stack exchange，提问作者code-match