{"id":122,"date":"2011-01-28T18:04:54","date_gmt":"2011-01-29T01:04:54","guid":{"rendered":"http:\/\/ryan.witschger.net\/?p=122"},"modified":"2011-01-28T18:04:54","modified_gmt":"2011-01-29T01:04:54","slug":"finding-the-fastest-method-to-search-a-large-list","status":"publish","type":"post","link":"http:\/\/www.Get-Blog.com\/?p=122","title":{"rendered":"Finding the Fastest Method to Search a Large List"},"content":{"rendered":"

Recently, a challenge came across my desk which included comparing very large sets of data against one another. Specifically, a list of all computers in our domain compared to a list of all computers registered with a specific application. This posed an interesting question to me, \u201cWhat would be the fastest way to accomplish this?\u201d<\/p>\n

I set out to look for different ways of comparing lists. I can think of three. The first two would be to load all of the items into an array and then search the array, item by item, for the value using either the \u2013match operator or the \u2013contains operator. The third method would be to load all the items into a hash table with empty values and then search the keys to see if they exist. Now since I know that loading up a hash table should take more time than loading an array, so I want to time the entire process not just the searches.<\/p>\n

To actually do the timing, I will use the measure-command cmdlet. If you haven\u2019t ever used this, you should really play with it. It\u2019s a great tool for figuring out how long any given code block takes to run. That can be useful for things like filling in a time on you write-progress applet, or reporting the time to execute back to a user. Really you can look at it as a way to avoid setting a variable to get-date and then creating a new-timespan after the command completes. It is essentially rolling it all into one.<\/p>\n

So, it\u2019s a race between searching Hash Tables, and Searching arrays using both \u2013match and \u2013contains. Here is the code I used:<\/p>\n

 $Checks<\/span> =<\/span> Get-Content<\/span> u:scriptworkstations.txt
\n
\n$ArrayContainsTime<\/span> =<\/span> Measure-Command<\/span> {<\/span>
\n    $Array<\/span> =<\/span> @<\/span>(<\/span>Get-Content<\/span> u:scriptworkstations.txt)<\/span>
\n    $Found<\/span> =<\/span> 0<\/span>
\n    foreach<\/span> (<\/span>$Name<\/span> in<\/span> $Checks<\/span>)<\/span>{<\/span>
\n        If<\/span> (<\/span>$Array<\/span> -contains<\/span> $Name<\/span>)<\/span>{<\/span>$found<\/span>++<\/span>}<\/span>
\n    }<\/span>
\n}<\/span>
\n"Array Contains Count: t$($Array.Count)"<\/span>
\n"Array Contains Found: t$($found)"<\/span>
\n
\n$ArrayMatchTime<\/span> =<\/span> Measure-Command<\/span> {<\/span>
\n    $Array<\/span> =<\/span> @<\/span>(<\/span>Get-Content<\/span> u:scriptworkstations.txt)<\/span>
\n    $Found<\/span> =<\/span> 0<\/span>
\n    foreach<\/span> (<\/span>$Name<\/span> in<\/span> $Checks<\/span>)<\/span>{<\/span>
\n        If<\/span> (<\/span>$Array<\/span> -match<\/span> $Name<\/span>)<\/span>{<\/span>$found<\/span>++<\/span>}<\/span>
\n    }<\/span>
\n}<\/span>
\n"Array Matches Count: t$($Array.Count)"<\/span>
\n"Array Matches found: t$($found)"<\/span>
\n
\n$HashTime<\/span> =<\/span> Measure-Command<\/span> {<\/span>
\n    $HashTable<\/span> =<\/span> @<\/span>{<\/span>}<\/span>
\n
\n    ForEach<\/span> (<\/span>$Line<\/span> in<\/span> Get-Content<\/span> u:scriptworkstations.txt)<\/span>{<\/span>
\n        $HashTable<\/span>.Add(<\/span>$Line<\/span>,<\/span>"1"<\/span>)<\/span>
\n    }<\/span>
\n    $Found<\/span> =<\/span> 0<\/span>
\n    foreach<\/span> (<\/span>$Name<\/span> in<\/span> $Checks<\/span>)<\/span>{<\/span>
\n        If<\/span> (<\/span>$Hashtable<\/span>.ContainsKey(<\/span>$Name<\/span>)<\/span>)<\/span>{<\/span>$found<\/span>++<\/span>}<\/span>
\n    }<\/span>
\n}<\/span>
\n"Hash Table Count: t$($HashTable.Count)"<\/span>
\n"Hash Table Found: t$($found)"<\/span>
\n
\n
\n"Milliseconds for Array Contains:t$($ArrayContainsTime.TotalMilliseconds)"<\/span>
\n"Milliseconds for Array Matches:t$($ArrayMatchTime.TotalMilliseconds)"<\/span>
\n"Milliseconds for Hast Table Contains:t$($HashTime.TotalMilliseconds)"<\/span><\/div><\/div>\n

I have loaded up the text file with 2,000 entries, so we are basically comparing 2,000 items to 2,000 items. Every single one will be a match, so we can see that it\u2019s working by making sure that the found and count values are the same. If you wanted to take this code and load two different lists, then you would see a difference there. So, without further delay, it\u2019s off to the races!<\/p>\n

Array Contains Count:   2000<\/span>
\nArray Contains Found:   2000<\/span>
\nArray Matches Count:    2000<\/span>
\nArray Matches found:    2000<\/span>
\nHash Table Count:   2000<\/span>
\nHash Table Found:   2000<\/span>
\nMilliseconds for<\/span> Array Contains:    532.6136<\/span>
\nMilliseconds for<\/span> Array Matches: 9839.4498<\/span>
\nMilliseconds for<\/span> Hast Table Contains:   51.2049<\/span><\/div><\/div>\n

So we have a winner! As you can see all the methods work, but the hash table is substantially faster than the other two, array based methods searching through all 2,000 items in under one tenth of a second! I think array using the \u2013contains operator is still a very reasonable time, and is probably easier and more comfortable for the average scripter to use. As well, it should be said that the array with the \u2013match operator isn\u2019t insanely slow by any means, and is by far the most robust method for searching as it can match any portion of the name in the array. This should be used with caution, though, as it can actually create false positives. Let\u2019s say you are looking for \u201cComputer\u201d in a list that contains \u201cComputer1\u201d. You may not expect this to be a match, but it will.<\/p>\n

So, there you have it. If you need to search a massive list for some reason and speed is top on your mind, use a hash table!<\/p>\n","protected":false},"excerpt":{"rendered":"

Recently, a challenge came across my desk which included comparing very large sets of data against one another. Specifically, a list of all computers in our domain compared to a list of all computers registered with a specific application. This posed an interesting question to me, \u201cWhat would be the fastest way to accomplish this?\u201d<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[4],"tags":[],"_links":{"self":[{"href":"http:\/\/www.Get-Blog.com\/index.php?rest_route=\/wp\/v2\/posts\/122"}],"collection":[{"href":"http:\/\/www.Get-Blog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.Get-Blog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.Get-Blog.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.Get-Blog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=122"}],"version-history":[{"count":0,"href":"http:\/\/www.Get-Blog.com\/index.php?rest_route=\/wp\/v2\/posts\/122\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.Get-Blog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=122"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.Get-Blog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=122"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.Get-Blog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=122"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}