{"id":16022,"date":"2022-10-13T22:49:58","date_gmt":"2022-10-13T17:19:58","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/"},"modified":"2022-10-13T22:49:58","modified_gmt":"2022-10-13T17:19:58","slug":"solved-fastest-way-to-compare-string-elements-with-each-other","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/","title":{"rendered":"[Solved] fastest way to compare string elements with each other"},"content":{"rendered":"<p> [ad_1]<br \/>\n<\/p>\n<div id=\"answer-30024728\" class=\"answer js-answer accepted-answer js-accepted-answer\" data-answerid=\"30024728\" data-parentid=\"30019523\" data-score=\"0\" data-position-on-page=\"2\" data-highest-scored=\"0\" data-question-has-accepted-highest-score=\"0\" itemprop=\"suggestedAnswer\" itemscope itemtype=\"https:\/\/schema.org\/Answer\">\n<div class=\"post-layout\">\n<div class=\"votecell post-layout--left\"><\/div>\n<div class=\"answercell post-layout--right\">\n<div class=\"s-prose js-post-body\" itemprop=\"text\">\n<p>The amount of downvotes is crazy but oh well&#8230; I found the reason for my performance issue \/ bottleneck thanks to the comments.<\/p>\n<p>The second for loop inside <code>StartSimilarityCheck()<\/code> iterates over all entries, which in itself is no problem but when viewed under performance issues and efficient, is bad. The solution is to only check strings which are in the neighborhood but how do we know if they are?<\/p>\n<p>First, we get a list which is ordered by ascension. That gives us a rough overview of similar strings. Now we define a <code>threshold<\/code> of Levenshtein score (smaller score is higher similarity between two strings). If the score is higher than the threshold it means they are not too similar, thus we can break out of the inner loop. That saves time and the program can finish really fast. Notice that that way is not bullet proof, IMHO because if the first string is <code>0Directory<\/code> it will be at the beginning part of the list but a string like <code>zDirectory<\/code> will be further down and could be missed. Correct me if I am wrong..<\/p>\n<pre><code>    private static void StartSimilarityCheck(List&lt;string&gt; whiteList)\n    {\n        var watch = Stopwatch.StartNew();\n        for (int j = 0; j &lt; whiteList.Count - 1; j++)\n        {\n            string dirName = whiteList[j];\n            bool insertDirName = true;\n            int threshold = 2;\n            if (!IsBlackList(dirName))\n            {\n                \/\/ start the next element\n                for (int i = j + 1; i &lt; whiteList.Count; i++)\n                {\n                    \/\/ end of index reached\n                    if (i == whiteList.Count)\n                    {\n                        break;\n                    }\n\n                    int similiarity = LevenshteinDistance.Compute(dirName, whiteList[i]);\n                    if (similiarity &gt;= threshold)\n                    {\n                        break;\n                    }\n                    \/\/ low score means high similarity\n                    if (similiarity &lt;= threshold)\n                    {\n                        if (insertDirName)\n                        {\n                            AddSimilarEntry(dirName);\n                            AddSimilarEntry(whiteList[i]);\n                            AddBlackListEntry(whiteList[i]);\n                            insertDirName = false;\n                        }\n                        else\n                        {\n                            AddBlackListEntry(whiteList[i]);\n                        }\n                    }\n                }\n            }\n            Console.WriteLine(j);\n        }\n        watch.Stop();\n        Console.WriteLine(\"Ms: \" + watch.ElapsedMilliseconds);\n        Console.WriteLine(\"Similar entries: \" + similar.Count);\n    }\n<\/code><\/pre>\n<\/p><\/div>\n<div class=\"mt24\"><\/div>\n<\/div>\n<p>            <span class=\"d-none\" itemprop=\"commentCount\"><\/span> <\/p><\/div>\n<\/div>\n<p>[ad_2]<\/p>\n<p>solved fastest way to compare string elements with each other <\/p>\n","protected":false},"excerpt":{"rendered":"<p>[ad_1] The amount of downvotes is crazy but oh well&#8230; I found the reason for my performance issue \/ bottleneck thanks to the comments. The second for loop inside StartSimilarityCheck() iterates over all entries, which in itself is no problem but when viewed under performance issues and efficient, is bad. The solution is to only &#8230; <a title=\"[Solved] fastest way to compare string elements with each other\" class=\"read-more\" href=\"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/\" aria-label=\"More on [Solved] fastest way to compare string elements with each other\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[324,325,362,2556],"class_list":["post-16022","post","type-post","status-publish","format-standard","hentry","category-solved","tag-c","tag-performance","tag-string","tag-string-comparison"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.5 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>[Solved] fastest way to compare string elements with each other - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] fastest way to compare string elements with each other - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] The amount of downvotes is crazy but oh well&#8230; I found the reason for my performance issue \/ bottleneck thanks to the comments. The second for loop inside StartSimilarityCheck() iterates over all entries, which in itself is no problem but when viewed under performance issues and efficient, is bad. The solution is to only ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-10-13T17:19:58+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] fastest way to compare string elements with each other\",\"datePublished\":\"2022-10-13T17:19:58+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/\"},\"wordCount\":200,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"c++\",\"performance\",\"string\",\"string-comparison\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/\",\"name\":\"[Solved] fastest way to compare string elements with each other - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2022-10-13T17:19:58+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] fastest way to compare string elements with each other\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] fastest way to compare string elements with each other - JassWeb","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] fastest way to compare string elements with each other - JassWeb","og_description":"[ad_1] The amount of downvotes is crazy but oh well&#8230; I found the reason for my performance issue \/ bottleneck thanks to the comments. The second for loop inside StartSimilarityCheck() iterates over all entries, which in itself is no problem but when viewed under performance issues and efficient, is bad. The solution is to only ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/","og_site_name":"JassWeb","article_published_time":"2022-10-13T17:19:58+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] fastest way to compare string elements with each other","datePublished":"2022-10-13T17:19:58+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/"},"wordCount":200,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["c++","performance","string","string-comparison"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/","url":"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/","name":"[Solved] fastest way to compare string elements with each other - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-10-13T17:19:58+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-fastest-way-to-compare-string-elements-with-each-other\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] fastest way to compare string elements with each other"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/16022","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=16022"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/16022\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=16022"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=16022"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=16022"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}