如何更高效实现索引依赖列表的数组子集提取？

Nice work getting your function working—let's look at how we can streamline and speed it up for the general case where your array has no predictable pattern.

First: Understand the Original Logic #

Your current function works by pairing the full list of array indices with your input list xs, then recursively checking for matches to pull the shifted element. The main inefficiency here is generating the full [0..len] index list (which wastes memory for large arrays) and the nested traversal pattern that leads to an O(m*n) time complexity (where m is the array length, n is the length of xs).

Optimization 1: Simplified Dual-Pointer Tail Recursion #

We can rewrite the logic to use a dual-pointer approach, eliminating the need to generate the full index list. This keeps the same core behavior but is more memory-efficient and concise:

let shiftFrom (n: int) (xs: 'T list) (arr: 'T []) : 'T list = 
    let maxIndex = arr.Length - 1
    let rec loop currentArrIndex remainingXs acc =
        match remainingXs with
        | [] -> List.rev acc // Done with xs, reverse accumulator for correct order
        | x::rest ->
            if currentArrIndex > maxIndex then List.rev acc // Reached end of array early
            elif arr.[currentArrIndex] = x then
                let shiftedIndex = currentArrIndex + n
                if shiftedIndex > maxIndex then List.rev acc // Shifted index out of bounds
                else loop (currentArrIndex + 1) rest (arr.[shiftedIndex]::acc)
            else loop (currentArrIndex + 1) remainingXs acc // No match, move to next array element
    loop 0 xs []

Why this is better:

• No unnecessary index list generation (saves memory for large arrays)
• Tail-recursive, so F# will optimize it to a loop (no stack overflow risk)
• Time complexity stays O(m) in the worst case (we only traverse the array once)

Testing with your sample input gives the exact same result:

let arr = [0..10] |> Array.ofList 
let xs = [0; 2; 5; 7; 9] 
shiftFrom 2 xs arr // val it : int list = [2; 4; 7; 9]

Optimization 2: Preprocessed Index Map (For Large Arrays/Xs) #

If your array or xs list is very large, we can preprocess the array to create a map of elements to their indices. This reduces the time complexity to O(m + n) (m for preprocessing, n for traversing xs):

open System.Collections.Generic

let shiftFromOptimized (n: int) (xs: 'T list) (arr: 'T []) : 'T list =
    let maxIndex = arr.Length - 1
    // Preprocess: Map each element to a queue of its indices (preserves order)
    let indexQueueMap = Dictionary<'T, Queue<int>>()
    for i in 0..maxIndex do
        let elem = arr.[i]
        if not (indexQueueMap.ContainsKey elem) then
            indexQueueMap.[elem] <- Queue<int>()
        indexQueueMap.[elem].Enqueue(i)
    
    let rec loop remainingXs acc =
        match remainingXs with
        | [] -> List.rev acc
        | x::rest ->
            match indexQueueMap.TryGetValue x with
            | false, _ -> List.rev acc // Element not found in array
            | true, queue ->
                if queue.Count = 0 then List.rev acc // No more indices left for this element
                else
                    let matchedIndex = queue.Dequeue()
                    let shiftedIndex = matchedIndex + n
                    if shiftedIndex > maxIndex then List.rev acc
                    else loop rest (arr.[shiftedIndex]::acc)
    loop xs []

Why this is better:

• Avoids re-traversing the array for each element in xs
• Ideal for cases where xs has repeated elements or both the array and xs are large
• Preserves the original "first match first" behavior

Which to Choose? #

• Use the dual-pointer version for small-to-medium arrays or when you want minimal code overhead.
• Use the preprocessed map version for large arrays or when xs contains many repeated elements.

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