使用std::vector将数组的最佳匹配搜索到矩阵中

Question

我刚刚完成了一个程序，它的作用如下：

• 您有t[10][5]和p[10]阵列
• 您阅读了dimT和dimP
• 在t[][]中写入dimT值，在p[]中写入dimP值

要在t[][]中写入值，必须先填充行。输出必须是与p[]数组匹配次数最多的列。示例：

INPUT -> 14 (dimT) 2 (dimP) 0 1 2 3 4 0 2 7 9 1 0 11 12 0 (t[][]) 0 0 (p[])

因此，最终的矩阵显示是：

0  1  2 3 4
0  2  7 9 1
0 11 12 0

OUTPUT->最佳匹配列为0，其中有2个匹配项（重叠计数）。

我使用数组创建了这个程序，但它真的很糟糕，所以我正在从一些专家那里寻找一个更好、更干净的解决方案，可能是使用向量而不是简单的数组。

Answer 1

这是我当前的代码。如果我把它再拆分成一两个函数会更好，但这样会更短：

#include <iostream>
#include <vector>
using namespace std;
bool IsMatch(vector<double>& col, vector<double>& p, int n)
{
    for (size_t i=0; i<p.size() ;i++)
        if (col[i+n]!=p[i])
            return false;
    return true;
}
int main()
{   
    int dimT;
    int dimP;
    cin >> dimT;
    cin >> dimP;        
    int lineN = (dimT+5-1)/5;       
    vector<vector<double> > t(lineN,vector<double>(5));
    vector<vector<double> > tTran(5,vector<double>());
    vector<double> p(dimP);
    t[lineN-1].resize(dimT%5);          
    //input matrices
    for (int i=0; i<dimT;i++) {     
        double inputVal;
        cin >> inputVal;    
        tTran[i%5].push_back(inputVal);
        t[i/5][i%5]=inputVal;
        }               
    for (int i=0; i<dimP;i++)
        cin >> p[i];            
    //print it out
    for (int line=0; line<lineN; line++){       
        for (size_t j=0; j<t[line].size(); j++)
            cout << t[line][j] << " ";
        cout << endl;
        }   
    //transpose t
    /*vector<vector<double> > tTran(5,vector<double>());
    for (int line=0; line<lineN; line++)
        for (size_t j=0; j<t[line].size(); j++)
            tTran[j].push_back(t[line][j]);
    //output tTran
    for (int line=0; line<5; line++){       
        for (size_t j=0; j<tTran[line].size(); j++)
            cout << tTran[line][j] << " ";
        cout << endl;
        }   
    */
    int maxCol=0;
    int maxMatchN=0;
    for (int col=0; col<5; col++){
        int matchN=0;
        for (size_t j=0; j<tTran[col].size()-p.size()+1; j++)
            if (IsMatch(tTran[col],p,j) )
                matchN++;           
        if (matchN>maxMatchN){
            maxMatchN = matchN;
            maxCol = col;
            }
        }
    cout << "The best matching column is " << maxCol
         << " with " << maxMatchN << " matches (overlap counted)." << endl;
}

Answer 2

这是我在评论中建议的更简单（全转置）的版本：我试图展示的是，非转置副本没有值。你知道在输入过程中转置比以后更容易。但您也保留了非转置副本，并从非转置拷贝中进行输出，并从转置拷贝进行处理。

如果你没有一个非转置副本，看看所有可以跳过的多余的废话。然后将转置副本的输出循环直接与原始输出循环进行比较。对输出循环的更改是微不足道的，而且好处是显著的。

int main()
{   
    int dimT;
    int dimP;
    cin >> dimT;
    cin >> dimP;        
    vector<double>  t[5+1];  // +1 because empty guard vector makes output loop simpler
    vector<double> p(dimP);
    //input matrices
    for (int i=0; i<dimT;i++) {     
        double inputVal;
        cin >> inputVal;    
        t[i%5].push_back(inputVal);
        }               
    for (int i=0; i<dimP;i++)
        cin >> p[i];            
    //print it out
    for (size_t line=0; line<t[0].size(); line++){       
        for (size_t j=0; line<t[j].size(); j++)
            cout << t[j][line] << " ";
        cout << endl;
        }
    int maxCol=0;
    int maxMatchN=0;
    for (int col=0; col<5; col++){
        int matchN=0;
        for (size_t j=0; j<t[col].size()-p.size()+1; j++)
            if (IsMatch(t[col],p,j) )
                matchN++;           
        if (matchN>maxMatchN){
            maxMatchN = matchN;
            maxCol = col;
            }
        }
    cout << "The best matching column is " << maxCol
         << " with " << maxMatchN << " matches (overlap counted)." << endl;
}

这个空的"保护"向量是一个很有用的技巧，在更复杂的问题中可以避免很多细节和可能的错误。在这段代码中，它只在一个位置节省了所需的j<5 &&。