用于过滤器优化的数据分组算法

Question

我正在使用 MCP2515（CAN 收发器）开展一个项目，该芯片的一个特点是我可以通过应用规则（掩码）来过滤 ID，只让特定范围的数据通过过滤器。我最多可以有 6 个不同的过滤器。在我正在编码的应用程序中，我解析了一个 DBC 文件以选择我想要接收的信号。如果我有 6 个或更少的信号，我可以为这些信号中的每一个制定“传递规则”，但如果我有 6 个以上的信号，我需要创建规则来包含我需要的所有 ID。理想情况下，每个组都将包含尽可能小的数据范围。我希望它自动计算，所以我需要创建一种算法来重新组合我的 ID。例如，如果我选择了以下 ID：32、154、157、160、354、363、680、682、841、845、871、932、936、940我的数据组将是 [32], [154, 157, 160], [354, 363], [680, 682], [841, 845, 871], [932, 936, 940]。这是我现在拥有的代码，但它无法处理范围的结尾（在上述情况下：32 和 940）。private void getMasks()    {        List<List<uint>> fields = new List<List<uint>>();        uint spectrum = 0;        uint chunkSize = 0;        IDs.Sort();        spectrum = IDs.Last() - IDs.First();        //Gets the sixth of my whole data range for a first grouping        chunkSize = (uint)Math.Ceiling(((double)spectrum / 6));        //Regroups data in the 6 ranges        for(int i = 0; i < 6; i++)        {            fields.Add(new List<uint>());            foreach (uint id in IDs)            {                if (id >= ((i * chunkSize) + IDs.First()) && id < (((i + 1) * chunkSize) - 1) + IDs.First())                    fields[i].Add(id);                                }                        }        //If a range doesn't have data, removes it        for (int j = 0; j < fields.Count; j++)            if (fields[j].Count == 0)            {                fields.RemoveAt(j);                j--;            }有人能给我一些关于如何在尽可能小的范围内重新组合数据的提示或示例吗？

Answer 1

这是您的列表，计算出到下一个项目的“距离”：

32(122), 154(3), 157(3), 160(194), 354(9), 363(317), 680(2), 682(159), 841(4), 845(26), 871(61), 932(4), 936(4), 940()

这里按“距离”降序排列的相同列表：

363(317), 160(194), 682(159), 32(122), 871(61), 845(26), 354(9), 841(4), 932(4), 936(4), 154(3), 157(3), 680(2), 940() 

你需要什么 - 拿前 5 项：

363(317), 160(194), 682(159), 32(122), 871(61)

并在这些项目之后“拆分”您的原始列表：

32(122)                  // split 4

154(3), 157(3), 160(194) // split 2

354(9), 363(317)         // split 1

680(2), 682(159)         // split 3

841(4), 845(26), 871(61) // split 5

932(4), 936(4), 940()

它将为您提供 6 组（您剪下 5 个最大的空间）

Answer 2

在代码中：

using System;

using System.Collections.Generic;

using System.Linq;

namespace ConsoleApp1

{

    class Program

    {

        static void Main(string[] args)

        {

            List<int> signals = new List<int>() { 680, 841, 154, 940, 160, 157, 936, 354, 363,  682, 871, 932, 845, 32};

            signals.Sort();

            List<GapData> gapsData = new List<GapData>();

            for(int i = 0; i < signals.Count - 1; i++)

            {

                GapData newGap = new GapData() { Index = i, Span = signals[i + 1] - signals[i] };

                gapsData.Add(newGap);

            }

            gapsData.Sort();

            gapsData = gapsData.Take(5).ToList(); //Keep 5 biggest gaps

            gapsData = gapsData.OrderBy(i => i.Index).ToList(); //sort on index

            List<List<int>> groupedList = new List<List<int>>();

            int index = 0;

            List<int> currentGroup = new List<int>();

            groupedList.Add(currentGroup);

            for(int i = 0; i < signals.Count; i++)

            {

                if (index < 5 && gapsData[index].Index < i)

                {

                    currentGroup = new List<int>();

                    groupedList.Add(currentGroup);

                    index++;

                }

                currentGroup.Add(signals[i]);

            }

        }

        public class GapData:IComparable<GapData>

        {

            public GapData()

            {

            }

            public int Index { get; set; }

            public int CompareTo(GapData other)

            {

                return - Span.CompareTo(other.Span);

            }

            public int Span { get; set; }

        }

    }

}