C#如何按另一列表的顺序高效提取列表项？

一、通用场景：处理ID不存在的情况 #

原实现的核心问题是每次遍历小列表时都要全量扫描大列表，当数据规模较大时性能会急剧下降（时间复杂度为O(n*m)）。最优优化方案是先将大列表转换为以ID为键的字典，把单次查找的时间复杂度降到O(1)，整体时间复杂度优化为O(n+m)，性能提升显著。

优化后代码 #

using System;
using System.Linq;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    { 
        var biglist = new List<Tuple<int, string>>()
        {
            new Tuple<int, string>(11032035, "GBP"),
            new Tuple<int, string>(11025566, "USD"),
            new Tuple<int, string>(11020456, "USD"),
            new Tuple<int, string>(11020457, "USD"),
            new Tuple<int, string>(11030141, "CAD"),
            new Tuple<int, string>(11026859, "USD"),
            new Tuple<int, string>(11030142, "CAD"),
            new Tuple<int, string>(11033667, "USD"),
            new Tuple<int, string>(11033676, "USD"),
            new Tuple<int, string>(11031834, "EUR"),
            new Tuple<int, string>(11020422, "USD"),
            new Tuple<int, string>(11020423, "USD"),
            new Tuple<int, string>(11019982, "EUR"),
            new Tuple<int, string>(11029609, "USD"),
            new Tuple<int, string>(11000491, "EUR"),
            new Tuple<int, string>(11020084, "EUR"),
            new Tuple<int, string>(11029141, "LC"),
            new Tuple<int, string>(11025166, "EUR")
        };

        var smalllist = new List<Tuple<int, string, int>>()
        {
            new Tuple<int, string, int>(43, "CAD", 11030141),
            new Tuple<int, string, int>(90, "USD", 11020457),
            new Tuple<int, string, int>(91, "USD", 11029141),
            new Tuple<int, string, int>(102, "USD", 11030142),
            new Tuple<int, string, int>(103, "USD", 11020084),
            new Tuple<int, string, int>(112, "EUR", 11020456),
            new Tuple<int, string, int>(113, "USD", 12345678),
            new Tuple<int, string, int>(114, "USD", 11020423),
            new Tuple<int, string, int>(115, "USD", 11025566),
            new Tuple<int, string, int>(129, "CAD", 11000491)
        };

        // 将大列表转为字典，以ID为键快速查找
        var bigDict = biglist.ToDictionary(item => item.Item1, item => item);

        // 按小列表顺序提取，处理未找到的项
        var orderedExtract = smalllist.Select(smallItem => 
        {
            if (bigDict.TryGetValue(smallItem.Item3, out var foundItem))
            {
                return foundItem;
            }
            // 未找到时构造默认返回项
            return new Tuple<int, string>(smallItem.Item3, "not found");
        }).ToList();

        // 输出结果
        foreach (var pair in orderedExtract)
        {
            Console.WriteLine($"{pair.Item1} {pair.Item2}");
        }
    }
}

输出结果 #

11030141 CAD
11020457 USD
11029141 LC
11030142 CAD
11020084 EUR
11020456 USD
12345678 not found
11020423 USD
11025566 USD
11000491 EUR

方案优势 #

• 字典仅需一次遍历大列表构建（O(n)）
• 每个小列表元素的查找操作都是O(1)，遍历小列表为O(m)
• 严格保留小列表的原始顺序，同时完整处理ID不存在的边界情况

二、简单场景：小列表ID均存在于大列表中 #

如果可以确保小列表的所有ID都在大列表中存在，可直接简化代码，省略未找到的判断分支：

// 构建字典
var bigDict = biglist.ToDictionary(item => item.Item1, item => item);

// 直接按顺序提取元素
var orderedExtract = smalllist.Select(smallItem => bigDict[smallItem.Item3]).ToList();

该方案同样保持O(n+m)的时间复杂度，代码更简洁高效，适合ID全存在的确定性场景。

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