c# - 根据找到的数据修剪 3 维数组请求

Question

我有一个服务可以获取以下数据

Func(List<symbols>,List<fields>,StartDate,EndDate)

它将返回一个 3 维值数组。

Sym1   field1 field2 field3
Sym2   field1 field2 field3
    Date1
     Date2
      Date3

即x轴是字段，y轴是符号，z轴是日期。

我还以字典的格式缓存了上述一些值(我之前获取的)

<Date<Symbol<field,value>>>

该服务根据它将返回的每个数据点收费。因此，如果我们有 3 个符号、4 个字段和 2 个数据日期，那么我们将收取 24 个点的费用。

我需要将原来较大的请求分解为多个较小的请求，仅针对缓存中未找到的数据。

例如。如果我有 5 个符号 A、B、C、D、E 和 4 个字段 F1、F2、F3、F4 的原始请求，用于 3 个日期 D1、D2、D3。

A,B,C,D,E     F1,F2,F3,F4     D1,D2

假设在缓存中我已经有以下字段的数据

B,F2,D2
C,F4,D1

然后，如果优化和损坏，我将向服务发出的后续请求将是

Request1 A,B,C,D   F1,F3    D1,D2
Request2 A,D       F2,F4    D1,D2
Request3 B         F2,F4    D1
Request4 B         F4       D2
Request5 C         F2,F4    D2
Request6 C         F2       D1

是否有一些标准方法可以将以上内容划分为更小的请求/3D 数组。实现这一目标的最佳方式是什么？什么类型的数据结构适合我的需要？

Answer 1

您的问题可以可视化如下:

您有一个密集的 3D 网格，其中一些单元格(灰色单元格)已被缓存占用。任务是找到最少数量的长方体来填充可用空间。但是，您的情况有点特殊，因为符号和字段的轴没有排序。

我感觉这个问题没有多项式解。因此，如果您真的需要找到最佳解决方案，您很有可能需要搜索整个解决方案空间(例如使用回溯)。这是一个近似贪心算法的想法:

for each iSymbol
    for each iField
        for each iDate
        {
            if(values[iSymbol, iField, iDate] != null) //already filled
                continue;

            set<int> symbols = {iSymbol}; //the symbols in the current cuboid
            set<int> fields = {iField}; //the fields in the current cuboid
            int maxDate = iDate; //the maximum date index

            bool dateAxisFinished = false;
            bool symbolAxisFinished = false;
            bool fieldAxisFinished = false;

            for(int i = 0; i < 3; ++i) //extend along all three axis
            {
                //check which axis allows the greatest extension                
                int extDate;
                if(!dateAxisFinished)
                    extDate = checkExtensionDate(iDate, symbols, fields);
                set<int> extSymbols;
                if(!symbolAxisFinished)
                    extSymbols = checkExtensionSymbol(iDate, maxDate, iSymbol, fields);
                set<int> extFields;
                if(!fieldAxisFinished) 
                    extFields = checkExtensionField(iDate, maxDate, symbols, iField); 
                }

                if(!dateAxisFinished && extDate-iDate+1 >= extSymbols.size && extDate-iDate+1 >= extFields.size)
                {
                    //fix this extension
                    maxDate = extDate;
                    dateAxisFinished = true;
                }
                else if(!symbolAxisFinished && extSymbols.size >= extFields.size)
                {
                    symbols = extSymbols;
                    symbolAxisFinished = true:
                }
                else
                {
                    fields = extFields;
                    fieldAxisFinished = true;
                }
            }
            perform a query for symbols, fields from iDate to maxDate and put result into values
        }

// -----------------------

//returns the maximum date index that can be included in the current cuboid
int checkExtensionDate(int dateFrom, set<int> symbols, set<int> fields)
{
    for iDate from dateFrom + 1 to maxDate
        for each iSymbol in symbols
            for each iField in fields
                if(values[iSymbol, iField, iDate] != null
                    return iDate - 1;
}

//returns the maximum set of symbols that can be included in the current cuboid
set<int> checkExtensionSymbol(int dateFrom, int dateTo, int startSymbol, set<int> fields)
{
    set<int> result = { startSymbol };
    for each iSymbol in allSymbols \ { iSymbol }
    {
        bool symbolOk = true;
        for each iDate from dateFrom to dateTo
        {
            if(!symbolOk)
                break;
            for each iField in fields
            {
                if(!symbolOk)
                     break;
                if(values[iSymbol, iField, iDate] != null
                    symbolOk = false;
            }
        }
        if(symbolOk)
            result.add(iSymbol);
    }
    return result;
}

//similar method for fields

这只是一个基本想法，可能需要一些改进。