Java 8 3小时滑动窗口日志计数求和的高效实现咨询

Great question! Since your log data is already sorted by timestamp, we can leverage this ordered property to completely avoid scanning the entire list for each log entry—this is the key to fixing the O(n²) inefficiency of your original approach.

Why the Original Code Is Slow #

Your current implementation streams the entire log list for every single log entry to filter entries within the 3-hour window. For a list of size n, this results in O(n²) time complexity, which becomes painfully slow as the dataset grows.

Optimized Approaches #

We have two efficient options here, both taking advantage of the sorted timestamp order:

1. Two-Pointer Technique (O(n) Time, Optimal for Large Datasets)

Since the logs are sorted, we can use a sliding window with two pointers to maintain the sum of the current window. The right pointer only moves forward, so each log is processed exactly twice (once by the right pointer, once by the left pointer).

Here's how to implement it:

// Assume sortedLogs is your pre-sorted list of Log objects (ascending by timestamp)
List<Log> sortedLogs = ...; 
List<Long> windowSums = new ArrayList<>();
int rightPointer = 0;
long currentWindowSum = 0;

for (int leftPointer = 0; leftPointer < sortedLogs.size(); leftPointer++) {
    Log currentLog = sortedLogs.get(leftPointer);
    LocalDateTime windowEnd = currentLog.getTimestamp().plusHours(3);

    // Expand the right end of the window as far as possible
    while (rightPointer < sortedLogs.size()) {
        Log rightLog = sortedLogs.get(rightPointer);
        if (rightLog.getTimestamp().isAfter(windowEnd)) {
            break; // Exit if we've gone beyond the 3-hour window
        }
        currentWindowSum += rightLog.getCount();
        rightPointer++;
    }

    // Record the sum for the current window
    windowSums.add(currentWindowSum);
    
    // Optional: Print the window details as per your requirement
    System.out.printf("%s ~ %s %d%n",
        currentLog.getTimestamp(),
        windowEnd.minusSeconds(1), // Adjust to show inclusive end time
        currentWindowSum);

    // Shrink the window from the left for the next iteration
    currentWindowSum -= currentLog.getCount();
}

How it works:

• The leftPointer iterates each log as the window start.
• The rightPointer keeps track of the farthest log that fits within the 3-hour window of the current left pointer.
• We maintain a running sum that we adjust by adding new right entries and removing the left entry once we move past it.

2. Prefix Sum + Binary Search (O(n log n) Time, Simpler Implementation)

If you prefer a more straightforward approach (or need to handle edge cases where logs might be modified later), you can precompute a prefix sum array and use binary search to find the window's right boundary for each log.

Step 1: Precompute the prefix sum array

long[] prefixSum = new long[sortedLogs.size() + 1];
for (int i = 0; i < sortedLogs.size(); i++) {
    prefixSum[i + 1] = prefixSum[i] + sortedLogs.get(i).getCount();
}

Step 2: Iterate each log and use binary search to find the window end

List<Long> windowSums = new ArrayList<>();

for (int i = 0; i < sortedLogs.size(); i++) {
    Log currentLog = sortedLogs.get(i);
    LocalDateTime windowEnd = currentLog.getTimestamp().plusHours(3);

    // Binary search to find the last log with timestamp <= windowEnd
    int left = i;
    int right = sortedLogs.size() - 1;
    int windowRightIndex = i; // Default to current log if none others fit

    while (left <= right) {
        int mid = left + (right - left) / 2;
        Log midLog = sortedLogs.get(mid);
        if (midLog.getTimestamp().isBefore(windowEnd) || midLog.getTimestamp().isEqual(windowEnd)) {
            windowRightIndex = mid;
            left = mid + 1; // Look for a later log that still fits
        } else {
            right = mid - 1; // Move left if mid log is outside the window
        }
    }

    // Calculate sum using prefix sum: sum from i to windowRightIndex = prefix[windowRightIndex+1] - prefix[i]
    long sum = prefixSum[windowRightIndex + 1] - prefixSum[i];
    windowSums.add(sum);

    // Optional: Print window details
    System.out.printf("%s ~ %s %d%n",
        currentLog.getTimestamp(),
        windowEnd.minusSeconds(1),
        sum);
}

How it works:

• The prefix sum array lets us calculate any subarray sum in O(1) time.
• Binary search finds the rightmost log in the window in O(log n) time per entry, leading to an overall O(n log n) time complexity.

Which to Choose? #

• Use the two-pointer technique for the best performance with large datasets (O(n) time is unbeatable here).
• Use the prefix sum + binary search if you want a simpler implementation or need to handle non-contiguous window queries later.

Both approaches eliminate the full list scan per entry, making them drastically more efficient than your original code for large log datasets.

内容的提问来源于stack exchange，提问作者ttt