Location>code7788 >text

Sort matching algorithm

Popularity：500 ℃/2025-04-26 11:35:00

Sort matching algorithm

Background: In such a scenario, production line equipment will generate a large number of alarms in detail during work. We need to conduct statistical analysis of these alarms, especially the duration and alarm frequency of various types of alarms, to provide data analysis for the positioning of equipment failure problems. However, the current background is that the alarm and alarm end of the equipment are both independent details. If you want to calculate the duration of the alarm information, you need to match the two messages starting and ending alarms.

The principle of matching

  1. The equipment information is consistent
  2. Alarm type consistent
  3. The alarm status is: start of alarm and end of alarm
  4. The alarm end time is greater than the alarm start time, and is the closest time to the above conditions.

Solid Modeling

Alarm entity category

public class Alarm
     {
         /// <summary>
         /// Equipment number
         /// </summary>
         public string EquipmentCode { get; set; }

         /// <summary>
         /// Alarm content
         /// </summary>
         public string AlarmContent { get; set; }

         /// <summary>
         /// Alarm status
         /// </summary>
         public AlarmStatusEnum AlarmStatus { get; set; }
         /// <summary>
         /// Creation time
         /// </summary>
         public DateTime CreateTime { get; set; }

         /// <summary>
         /// Alarm number
         /// </summary>
         public string AlarmCode { get; set; }
     }
     /// <summary>
     /// Alarm status
     /// </summary>
     public enum AlarmStatusEnum
     {
         Start = 0,
         End = 1
     }

Output entity class

public class AlarmDto
  {
      /// <summary>
      /// Equipment number
      /// </summary>
      public string EquipmentCode { get; set; }
     
      /// <summary>
      /// Alarm number
      /// </summary>
      public string AlarmCode { get; set; }
     
      /// <summary>
      /// Alarm content
      /// </summary>
      public string AlarmContent { get; set; }

      /// <summary>
      /// Creation time
      /// </summary>
      public DateTime StartTime { get; set; }
     
      /// <summary>
      /// End time
      /// </summary>
      public DateTime EndTime { get; set; }
     
      /// <summary>
      /// Alarm duration
      /// </summary>
      public string Duration { get; set; }


  }

Now to find out[startTime,deadLine]The alarm records in this time period are matched and combined to subsequently calculate the duration and number of alarm types in this time period.

Original algorithm

public static List<AlarmDto> CrateAlarmDto(List<Alarm> alarms, DateTime startTime, DateTime deadLine)
 {
     //1. Grouping
     var startAlarms = (s=> == ).OrderBy(s=>).ToList();
     var endAlarms = (s => == ).OrderBy(s => ).ToList();
     var alarmDtos = new List<AlarmDto>();
     foreach (var alarm in startAlarms)
     {
         AlarmDto windingAlarmDto = new AlarmDto
         {

             EquipmentCode = ,
             AlarmContent = ,
             StartTime =
         };
         //Be sure to match according to AlarmCode because different AlarmCodes will have the same error content
         var endAlarm = (s=> == && () && >= ).OrderBy(s=>).FirstOrDefault();
         if (endAlarm != null)
         {
              = ;
             //Removing from the original endAlarms? Is it necessary?  Will there be two consecutive identical errors on the same number of units?  This will not happen with verification, but this will gradually reduce the length of endAlarm and match will be faster.
             (endAlarm);
         }
         else
         {
             //The end time of the start of the alarm without matching must exceed the deadLine. We only count the range so we use deadLine as the end time
              = deadLine;
         }
         TimeSpan ts = - ;
          = $"{:D2}min{:D2}seconds";
         (windingAlarmDto);
     }
     //If there is still something left in endAlarms, it means that it has not been matched before. Use the given filtering start time as the start time
     if (())
     {
         foreach (var alarm in endAlarms)
         {
             AlarmDto windingAlarmDto = new AlarmDto
             {
                 EquipmentCode = ,
                 AlarmContent = ,
                 StartTime = startTime,
                 EndTime =
             };
             TimeSpan ts = - ;
              = $"{:D2}min{:D2}seconds";
             (windingAlarmDto);
         }
     }
     return alarmDtos;
 }

Improved algorithm

public static List<AlarmDto> CrateAlarmDtoNew(List<Alarm> alarms, DateTime startTime, DateTime deadLine)
  {
      var startAlarms = (s => == ).ToList();
      var endAlarms = (s => == ).ToList();
      var alarmDtos = new List<AlarmDto>();
      var endGroups = endAlarms
                      .GroupBy(e => new { , })
                      .ToDictionary(
                          g => ,
                          g => (e => ).ToList()
                      );
      var leftEndList1 = (s => ).ToList();
      foreach (var alarm in (a => ))
      {
          AlarmDto windingAlarmDto = new AlarmDto
          {
              EquipmentCode = ,
              AlarmContent = ,
              AlarmCode = ,
              StartTime =
          };
          //Search for any corresponding alarm information collection of devices of the same type.
          var key = new { , };
          if ((key, out var endList))
          {
              // Binary search, find the element of alarm according to the defined CompareTo method. If it is not found, it returns the complement of the elements that CompareTo is greater than alarm. If there is no element that is greater than alarm, it returns
              int index = (alarm, Comparer<Alarm>.Create((x, y) => ()));
              if (index < 0) index = ~index;
              if (index < )
              {
                  var endAlarm = endList[index];
                   = ;
                  endGroups[key].RemoveAt(index); //Remove the corresponding object by subscripting, which is more efficient
              }
          }
          //If there is no corresponding matching alarm ending information, use the expiration time to match
          if ( == )
          {
               = deadLine;
          }
          TimeSpan ts = - ;
           = $"{:D2}min{:D2}seconds";
          (windingAlarmDto);
      }
      //If there is still some left in endAlarms, it means that the alarm time is before startTime. We use startTime as the starting time
      var leftEndList = (s=>).ToList();
      if (())
      {
          foreach (var alarm in leftEndList)
          {
              AlarmDto windingAlarmDto = new AlarmDto
              {
                  EquipmentCode = ,
                  AlarmContent = ,
                  AlarmCode = ,
                  StartTime = startTime,
                  EndTime =
              };
              TimeSpan ts = - ;
               = $"{:D2}min{:D2}seconds";
              (windingAlarmDto);
          }
      }
      return alarmDtos;
  }

in conclusion

Overall, the improved algorithm matches faster after testing, with data of about 2,000 or so, and the original algorithm is about 14 milliseconds. And the larger the data volume, the more obvious the improved algorithm advantages.

<Previous Next>