Massive speed up to QgsStringUtils::levenshteinDistance by using std::vector instead of QVector

nyalldawson · nyalldawson · commit e04aa7b1872d · 2023-03-20T16:06:24.000+10:00
diff --git a/src/core/qgsstringutils.cpp b/src/core/qgsstringutils.cpp
@@ -193,13 +193,12 @@ int QgsStringUtils::levenshteinDistance( const QString &string1, const QString &
   }
 
   //levenshtein algorithm begins here
-  QVector< int > col;
-  col.fill( 0, length2 + 1 );
-  QVector< int > prevCol;
+  std::vector< int > col( length2 + 1, 0 );
+  std::vector< int > prevCol;
   prevCol.reserve( length2 + 1 );
   for ( int i = 0; i < length2 + 1; ++i )
   {
-    prevCol << i;
+    prevCol.emplace_back( i );
   }
   const QChar *s2start = s2Char;
   for ( int i = 0; i < length1; ++i )

Original file line number	Diff line number	Diff line change
`@@ -193,13 +193,12 @@ int QgsStringUtils::levenshteinDistance( const QString &string1, const QString &`
`193`	`193`	`}`
`194`	`194`
`195`	`195`	`//levenshtein algorithm begins here`
`196`		`- QVector< int > col;`
`197`		`- col.fill( 0, length2 + 1 );`
`198`		`- QVector< int > prevCol;`
	`196`	`+ std::vector< int > col( length2 + 1, 0 );`
	`197`	`+ std::vector< int > prevCol;`
`199`	`198`	`prevCol.reserve( length2 + 1 );`
`200`	`199`	`for ( int i = 0; i < length2 + 1; ++i )`
`201`	`200`	`{`
`202`		`- prevCol << i;`
	`201`	`+ prevCol.emplace_back( i );`
`203`	`202`	`}`
`204`	`203`	`const QChar *s2start = s2Char;`
`205`	`204`	`for ( int i = 0; i < length1; ++i )`