基于时间的班次时段拆分关联代码优化：百万级数据性能提升需求

业务场景 #

• 存在时段列表shiftRange，示例：

start  to  end
9:00am to 10:00 am
10:00am to 11:00am
11:00am to 12:00 pm

• 存在员工签到签退记录列表applyRecords（记录可能重叠），示例：

signIn to signOut
E1: 9:10am to 9:30am
E2: 9:20am to 10:10am
E3: 10:10am to 11:00am

• 需求：用applyRecords拆分shiftRange，生成关联员工信息的时段片段，示例：

start  to   end
9:00am to 9:10am
9:10am to 9:20am E1
9:20am to 9:30am E1, E2
9:30am to 10:00am E2
10:00am to 10:10am E2
10:10am to 11:00am E3
11:00am to 12:00pm 

现有实现问题 #

当前代码对每个shift遍历所有applyRecords，且每次处理activeList时都复制列表，在shiftRange达到百万级时，时间复杂度为O(NMK)（N=shift数量，M=apply数量，K=每次拆分后的片段数），执行效率极低。现有代码如下：

protected override IEnumerable<TSplit> Join(Query query, IEnumerable<TSplit> shiftRange, IEnumerable<TApply> applyRecords)
{
    var state = this.GetState(query);
    var applyRecordsCached = applyRecords.ToArray();

    foreach (var split in splitRecords) // 注：此处疑似笔误，应为shiftRange
    {
        var activeList = new LinkedList<TSplit>();
        activeList.AddLast(split);

        foreach (var apply in applyRecordsCached)
        {
            foreach (var current in activeList.ToList())
            {
                // Apply split logic and replace nodes in-place
                activeList.Remove(current);
                var parts = current.Split(apply); // 返回before, during, after三个时段
                if (parts.Item1 != null) activeList.AddLast(parts.Item1);
                if (parts.Item2 != null) activeList.AddLast(this.ApplyRecord(apply, parts.Item2, state)); // 绑定员工信息
                if (parts.Item3 != null) activeList.AddLast(parts.Item3);
            }
        }

        // 输出所有拆分后的片段
        foreach (var remainingSplit in activeList)
        {
            yield return remainingSplit;
        }
    }
}

核心优化方案 #

1. 预过滤：仅处理与当前shift重叠的apply记录 #

• 提前将applyRecords按signIn排序，对每个shift用二分查找快速定位出所有与该shift时间范围有重叠的apply记录，避免遍历全量apply。
• 进阶：为applyRecords构建区间索引（如区间树、线段树），进一步提升重叠查询效率。
• 代码思路示例：

  // 提前排序applyRecords
  var sortedApplies = applyRecordsCached.OrderBy(a => a.SignIn).ToArray();
  foreach (var shift in shiftRange)
  {
      // 二分查找找到第一个signIn <= shift.End的记录
      int left = 0, right = sortedApplies.Length - 1;
      int startIdx = sortedApplies.Length;
      while (left <= right)
      {
          int mid = (left + right) / 2;
          if (sortedApplies[mid].SignIn <= shift.End)
          {
              startIdx = mid;
              right = mid - 1;
          }
          else
          {
              left = mid + 1;
          }
      }
      // 过滤出与shift重叠的apply
      var relevantApplies = sortedApplies.Skip(startIdx).TakeWhile(a => a.SignOut >= shift.Start).ToArray();
      // 仅用relevantApplies处理当前shift
  }
  

2. 批量拆分：基于时间点一次性拆分时段 #

• 收集当前shift的起止时间，以及所有关联apply的signIn和signOut时间，去重后排序得到所有关键时间点。
• 遍历相邻时间点生成时段片段，再为每个片段匹配所有覆盖它的apply记录，避免多次拆分操作，时间复杂度从O(M*K)降至O(M + K)。
• 代码思路示例：

  foreach (var shift in shiftRange)
  {
      var timePoints = new List<DateTime> { shift.Start, shift.End };
      foreach (var apply in relevantApplies)
      {
          timePoints.Add(apply.SignIn);
          timePoints.Add(apply.SignOut);
      }
      // 去重并排序
      var sortedPoints = timePoints.Distinct().OrderBy(t => t).ToArray();
      
      for (int i = 0; i < sortedPoints.Length - 1; i++)
      {
          var segmentStart = sortedPoints[i];
          var segmentEnd = sortedPoints[i + 1];
          // 过滤出完全覆盖当前片段的apply
          var coveringApplies = relevantApplies.Where(a => a.SignIn <= segmentStart && a.SignOut >= segmentEnd).ToList();
          var segment = CreateSegment(segmentStart, segmentEnd);
          if (coveringApplies.Any())
          {
              segment = ApplyRecords(coveringApplies, segment, state);
          }
          yield return segment;
      }
  }
  

3. 数据结构优化：减少操作开销 #

• 替换LinkedList<TSplit>为List<TSplit>：LinkedList的内存开销和缓存命中率远低于List，百万级场景下List的批量操作效率更高。
• 避免activeList.ToList()复制：遍历前将需要处理的元素存入临时列表，直接操作原List，减少不必要的内存复制。

4. 并行处理：利用多核CPU资源 #

• 若shift之间无依赖关系，使用Parallel.ForEach替代普通foreach，并行处理多个shift。
• 注意：需确保ApplyRecord等方法线程安全，或为每个线程分配独立状态。
• 代码思路示例：

  var results = new ConcurrentBag<TSplit>();
  Parallel.ForEach(shiftRange, shift =>
  {
      // 处理单个shift的逻辑
      var segments = ProcessSingleShift(shift, relevantApplies, state);
      foreach (var seg in segments)
      {
          results.Add(seg);
      }
  });
  return results.OrderBy(s => s.Start); // 若需要按时间排序
  

5. 减少对象创建：复用实例或使用值类型 #

• 拆分过程会生成大量TSplit实例，若TSplit是引用类型，可考虑对象池复用；若场景允许，改为值类型减少GC压力。

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