C++ 与 n-Gram 的最快文本行比较？使用字符串、char*、 vector ？

Question

所以我目前正在写一些东西来比较数据表中的列。所以我基本上需要行、列，所有这些都是从 .csv 文件中读入的文本。

目前的问题是处理需要多长时间。我在 C# 中有重复代码，它使用带有行和列的“数据表”，处理 1500 行文本大约需要 13 秒。我的 C++ 程序使用“vector < vector >”作为表格，并且在这段时间内只处理了 175 行文本。算法与我所看到的相同，但我猜这与我在 C++ 中使用的数据类型有关，这使得速度变慢了。

有人知道原因吗？

//C++
void CheckColumn(int colNum)
{
    for (int i = 1; i < RowCount; i++)
    {
        for (int j = i + 1; j < RowCount; j++)
        {
            nGram(Data[colNum][i], Data[colNum][j], 3);
        }
    }
}
double nGram(string one, string two, int count)
{
    //Change to uppercase
    transform(one.begin(), one.end(), one.begin(), toupper);
    transform(two.begin(), two.end(), two.begin(), toupper);

    //Set the first string to be the shorter one
    if (one.size() > two.size())
    {
        string temp = one;
        one = two;
        two = temp;
    }

    //If nGram number is larger than the shortest string, set the nGram number to that length
    if (one.size() < count)
    {
        count = one.size();
    }

    //Add matches
    double weight = 0;
    double possibleMatches = (2 * two.size() - 2 * count + 2) / 2;
    for (int i = 0; i < (one.size() - count + 1); i++)
    {
        for (int j = 0; j < (two.size() - count + 1); j++)
        {
            if (one.substr(i, count) == two.substr(j, count))
            {
                weight += 1;
                break;
            }
        }
    }

    //Check for indivisible situations and otherwise calculate the weight
    if ((possibleMatches == 0) || (weight == 0))
    {
        weight = 0;
    }
    else
    {
        weight = weight / possibleMatches;
    }

    return weight;
}


//C#
void CompareColumn(int colNum)
{
    for(int i = 0; i < table.Rows.Count; i++)
    {
        for (int j = i + 1; j < table.Rows.Count; j++)
        {
            StringFunctions.nGram(table.Rows[i][colNum].ToString(), table.Rows[j][colNum].ToString(), 3);
        }
    }
}
public double nGram(string one, string two, int count)
{
    //Change to uppercase
    one = one.ToUpper();
    two = two.ToUpper();

    //Set the first string to be the shorter one
    if (one.Length > two.Length)
    {
        string temp = one;
        one = two;
        two = temp;
    }

    //If nGram number is larger than the shortest string, set the nGram number to that length
    if (one.Length < count)
    {
        count = one.Length;
    }

    //Add matches
    double doubleMatch = 0;
    double possibleMatches = (2 * two.Length - 2 * count + 2)/2;
    for (int i = 0; i < (one.Length - count + 1); i++)
    {
        for (int j = 0; j < (two.Length - count + 1); j++)
        {
            if (one.Substring(i, count) == two.Substring(j, count))
            {
                doubleMatch += 1;
                break;
            }
        }
    }

    //Check for indivisible situations and otherwise calculate the weight
    if ((possibleMatches == 0) || (doubleMatch == 0))
    {
        doubleMatch = 0;
    }
    else
    {
        doubleMatch = doubleMatch / possibleMatches;
    }
    return doubleMatch;
}

Answer 1

double nGram(string one, string 2, int count)

无需深入研究您的代码，上面的方法是我注意到的第一个问题。在 C++ 中，您可以通过复制、引用或指针传递值。您正在使用的方法是复制的，当您有一个方法被多次调用时会产生开销。

要说明，请参加以下类(class)。

class CopyMe
{

public:
    CopyMe();
    CopyMe(const CopyMe&m);
    ~CopyMe();
};


CopyMe::CopyMe()
{
    std::cout << "Created! Instance @ Location: " << this << std::endl;
}

CopyMe::CopyMe(const CopyMe& m)
{
    std::cout << "Copy! Instance @ Location: " << &m << " New Location: " << this << std::endl;
}

CopyMe::~CopyMe()
{
    std::cout << "Deleted! Instance @ Location: " << this << std::endl;
}

和以下简短的主要部分。

void SayHelloToMyLittleFriendViaCopy(CopyMe aCopy)
{
    std::cout << "Inside " << __PRETTY_FUNCTION__ << std::endl;
}

void SayHelloToMyLittleFriendViaReference(CopyMe& aReference)
{
    std::cout << "Inside " << __PRETTY_FUNCTION__ << std::endl;
}

int main(int argc, const char * argv[])
{
    CopyMe me;
    SayHelloToMyLittleFriendViaCopy(me);

    SayHelloToMyLittleFriendViaReference(me);
    return 0;
}

如果您运行上面的代码，您将获得以下输出。 注意您的内存位置会有所不同!

Created! Instance @ Location: 0x7fff5fbff7d8
Copy! Instance @ Location: 0x7fff5fbff7d8 New Location: 0x7fff5fbff7d0
Inside void SayHelloToMyLittleFriendViaCopy(CopyMe)
Deleted! Instance @ Location: 0x7fff5fbff7d0
Inside void SayHelloToMyLittleFriendViaReference(CopyMe &)
Deleted! Instance @ Location: 0x7fff5fbff7d8

如果比较这两个调用，您会注意到对 SayHelloToMyLittleFriendViaCopy 的调用有开销，因为它创建了一个拷贝，运行该方法，然后删除了它创建的临时对象。相比之下，调用 SayHelloToMyLittleFriendViaReference 不会产生这样的成本，因为调用函数时不会创建临时拷贝。上面的内容可能令人困惑，因为在示例的末尾调用了对象析构函数。然而，这不是由函数引起的，而是我们正在执行 main 方法并且我们的初始对象被销毁的事实。

如果这是您第一次听说按引用传递，您可以将其视为传递指针。但是，您不必取消引用该对象，编译器会为您添加糖分。

但是，如果您通过引用传递，则该方法可能会更改对象的状态。如果这是您想避免的事情，您仍然可以通过引用传递，但使用 const 引用。如果那是您想要的，那么您的签名应该是

double nGram(const string& one,const string& two, int count)