C++與n-Gram最快的文本行比較？使用字符串，char *，矢量？

Question

所以我目前正在寫一些比較數據表中的列的東西。所以我基本上需要行，列，並且所有文本都是從.csv文件讀入的。

這個問題目前是需要多長時間來處理。我在C＃中複製代碼，在行和列中使用'DataTable'，需要大約13秒來處理1500行文本。 我的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 two, int count)

沒有深入到你的代碼太多，上面的方法是我首先注意到的問題之一。在C++中，你可以通過通過複製，引用或指針的值。您正在使用的方法是通過複製並創建開銷當你有一個方法被稱爲很多。

讓病人蔘加下列課程。

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的呼叫不會產生這樣的成本，因爲該功能被稱爲不創建臨時副本。上面可能會令人困惑，因爲在示例結束時調用了對象析構函數。然而，這不是由函數引起的，而是我們正在發揮主要方法和我們最初的對象的事實被破壞了。

如果這是您第一次聽說通過引用傳遞，您可以將其視爲傳遞指針。但是，不是你不得不解除引用這個對象，編譯器會爲你添加糖。

但是，如果通過引用傳遞，那麼該方法可能會更改對象的狀態。如果這是你想避免的事情，你仍然可以通過引用傳遞，但帶有const引用。如果這是你以後在做什麼，然後你的簽名應該是

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

Answer 2

我做的東西相結合，以解決這一點，我肯定會嘗試測試了幾個方案。

我正在使用優化構建，但事實是我的字符串值複製到我的函數可能是主要問題。 我目前正在使用一個字符數組，它可以讓我加快n-Gram過程的速度。由於我在比較部分中逐字逐句地檢查，所以我只需要檢查第一個字符，當整個n-Gram不匹配時。例如，比較「ABC」和「BBC」，我知道我不必看第二個或第三個字符來查看三元組是否匹配。

此外，主要問題似乎一直沒有利用指針。傳遞char *指針似乎會增加最多的進程。我會嘗試回到字符串指針而不是字符指針，但是我仍然猜測字符是要走的路。

感謝大家的幫助！