纸币分发代码性能优化咨询及LINQ效率疑问

我实现了一套纸币分发逻辑，现有面额为{1, 5, 10, 20, 100}的纸币各10张。代码功能正常，但在计算分发纸币和更新剩余库存时效率偏低，希望得到优化方案，同时想了解使用LINQ是否会影响性能。

原代码 #

public List<BankNotesEntity> GetNotes()
{
    bankNotes = new List<BankNotesEntity>();
    bankNotes.AddRange(new List<BankNotesEntity>
    {
        new BankNotesEntity(1, 10),
        new BankNotesEntity(5, 10),
        new BankNotesEntity(10, 10),
        new BankNotesEntity(20, 10),
        new BankNotesEntity(100, 10),
    });
    return bankNotes;
}

public List<BankNotesEntity> DispenseNotes(int notesToDispense)
{
    var input = notesToDispense;
    var inventoryNotes = bankNotes.OrderByDescending(n => n.Denomination).ToList();

    //Check if the inventory is sufficient enough to dispense notes
    var sum = inventoryNotes.Sum(s => s.Denomination * s.Inventory);
    var dispensedNotes = new List<BankNotesEntity>();

    if (sum < notesToDispense)
        dispensedNotes = new List<BankNotesEntity>();
    else
    {
        foreach (var invt in inventoryNotes)
        {
            var bankNoteEntity = new BankNotesEntity();
            bankNoteEntity.Denomination = invt.Denomination;
            var bill = invt.Denomination;
            while (input >= bill)
            {
                if (invt.Inventory == 0)
                    break;
                else
                {
                    input -= bill;
                    invt.Inventory -= 1;
                    bankNoteEntity.Inventory += 1;
                }
            }
            dispensedNotes.Add(bankNoteEntity);
        }

        //counter check to make sure that the total dispesedNotes is equal to amountToDispensed
        var sumOfDispensedNotes = dispensedNotes.Sum(s => s.Denomination * s.Inventory);
        if (sumOfDispensedNotes < notesToDispense)
        {
            //dipensedNotes is not equal to amountToDispensed, now we will return it to the inventory.
            dispensedNotes.ForEach(delegate (BankNotesEntity d)
            {
                var inventory = inventoryNotes.Find(i => i.Denomination == d.Denomination);
                if (inventory != null)
                    inventory.Inventory += d.Inventory;
            });
            dispensedNotes = new List<BankNotesEntity>();
        }
    }
    return dispensedNotes.OrderBy(n => n.Denomination).ToList();
}

优化方案 #

1. 用数学运算替代循环逐张计算 #

原代码用while循环逐张扣除金额和库存，改成除法直接计算当前面额最多能分发的数量，避免循环开销：

int maxPossible = Math.Min(input / invt.Denomination, invt.Inventory);
if (maxPossible > 0)
{
    input -= maxPossible * invt.Denomination;
    invt.Inventory -= maxPossible;
    bankNoteEntity.Inventory = maxPossible;
}

2. 用字典优化库存查找 #

归还库存时，List.Find是线性查找，改用Dictionary<int, BankNotesEntity>存储库存，实现O(1)时间复杂度的查找：
在初始化库存时就构建字典，或者在方法内转换：

var inventoryDict = inventoryNotes.ToDictionary(n => n.Denomination);
// 归还时直接查找
if (inventoryDict.TryGetValue(d.Denomination, out var inventory))
    inventory.Inventory += d.Inventory;

3. 减少不必要的LINQ调用与计算 #

• 计算总库存时，可以提前终止：一旦累加的金额超过目标金额，就停止计算，不用遍历所有面额
• 原代码中OrderByDescending后调用ToList会创建新列表，若库存是固定顺序的高到低，可以提前初始化时就按降序排列，避免每次分发都排序
• 分发完成后如果需要验证金额，直接用剩余的input是否为0判断，不用重新计算总和（因为input初始是目标金额，每分发一次就扣除对应金额，最终input == 0说明分发成功）

4. 优化初始化逻辑 #

GetNotes方法每次调用都会重新创建列表，若库存是全局维护的，无需每次重新初始化，避免重复对象创建。

优化后代码示例 #

// 建议全局维护库存字典，避免重复创建
private Dictionary<int, BankNotesEntity> _bankNoteInventory;

public void InitializeInventory()
{
    _bankNoteInventory = new Dictionary<int, BankNotesEntity>
    {
        {1, new BankNotesEntity(1, 10)},
        {5, new BankNotesEntity(5, 10)},
        {10, new BankNotesEntity(10, 10)},
        {20, new BankNotesEntity(20, 10)},
        {100, new BankNotesEntity(100, 10)}
    };
}

public List<BankNotesEntity> DispenseNotes(int notesToDispense)
{
    if (notesToDispense <= 0)
        return new List<BankNotesEntity>();

    var input = notesToDispense;
    // 按面额降序处理，直接从字典取排序后的集合
    var sortedInventory = _bankNoteInventory.Values.OrderByDescending(n => n.Denomination).ToList();
    var dispensedNotes = new List<BankNotesEntity>();
    bool dispenseSuccess = true;

    // 先快速校验库存是否足够（可选优化：提前终止累加）
    int totalInventory = 0;
    foreach (var note in sortedInventory)
    {
        totalInventory += note.Denomination * note.Inventory;
        if (totalInventory >= notesToDispense)
            break;
    }
    if (totalInventory < notesToDispense)
        return new List<BankNotesEntity>();

    // 计算分发数量
    foreach (var invt in sortedInventory)
    {
        var bankNoteEntity = new BankNotesEntity { Denomination = invt.Denomination };
        if (input <= 0)
        {
            dispensedNotes.Add(bankNoteEntity);
            continue;
        }

        int maxPossible = Math.Min(input / invt.Denomination, invt.Inventory);
        if (maxPossible > 0)
        {
            input -= maxPossible * invt.Denomination;
            invt.Inventory -= maxPossible;
            bankNoteEntity.Inventory = maxPossible;
        }
        dispensedNotes.Add(bankNoteEntity);
    }

    // 验证是否分发成功
    if (input != 0)
    {
        // 归还库存
        var inventoryDict = _bankNoteInventory;
        foreach (var d in dispensedNotes)
        {
            if (d.Inventory > 0 && inventoryDict.TryGetValue(d.Denomination, out var inventory))
                inventory.Inventory += d.Inventory;
        }
        dispensedNotes.Clear();
    }

    // 按面额升序返回
    return dispensedNotes.OrderBy(n => n.Denomination).ToList();
}

LINQ效率说明 #

LINQ确实会带来轻微的性能开销，主要来自委托调用和延迟执行的包装逻辑，但在这个纸币分发场景中，原代码的性能瓶颈并非LINQ本身，而是循环逐张计算和线性查找库存这两个点。

合理使用LINQ不会显著影响效率：

• 对于排序、过滤这类操作，LINQ的内部实现已经优化过，和手动写循环效率差距很小
• 若在热点路径（比如高频调用的分发逻辑）追求极致性能，可以把关键计算部分（如库存查找、金额计算）用原生代码实现，其他场景用LINQ提升代码可读性

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