How to speed up binary search? or pass 400 thousand items

Question

In general, 700 thousand lines (xxx.xxx.xxx.xxx - ip) in the database A text file comes from ~ 400 thousand actual ones, you need to go through and save 400 thousand actual ones in the database, the remaining 300 to mark that they are not relevant. Everything would be fine, everything works, but this sort of search takes 11 minutes on a 4 GHz stone. I do this:

//Тут сортирую по ip, строки из БД 700 тысяч ListCurrentBD.Sort((x, y) => x["ipWorld"].CompareTo(y["ipWorld"])); for(int i=0; i < ipList.Count; i++) { //находим индекс по компарер ipWorld int indS = ListCurrentBD.BinarySearch(ipList[i], new CompareripWorld()); if (!(indS<0)) { //Заносим данные, позже по этому листу обновим актуальные ip ListUpdateBD.Add(ipList[i]); //добавляем идентификатор по которому будем обновлять актуальность ListUpdateBD[ListUpdateBD.Count-1]["id"] = ListCurrentBD[indS]["id"]; } }

The beginning of the question How to create an associative array with sorting, quick search and deletion of elements

var ListCurrentBD = new List <Dictionary <string, string >> ();

tym32167 tym32167 14.7k one 15 35 · Accepted Answer · 2018-09-28T15:35:08

We will generate 700k + 400k random IP

 Random r = new Random(); var ipAddresses = Enumerable.Range(0, 700000) .Select(x => $"{r.Next(256)}.{r.Next(256)}.{r.Next(256)}.{r.Next(256)}") .ToArray(); var validAddresses = new HashSet<string>(Enumerable.Range(0, 400000) .Select(x => $"{r.Next(256)}.{r.Next(256)}.{r.Next(256)}.{r.Next(256)}"));

We will add the result to the lists (it would be possible to write a LINQ query, but so more clearly)

 var valids = new List<string>(); var inValids = new List<string>();

Processing the inclusion of 700k addresses in 400k valid

 foreach(var ip in ipAddresses) { if(validAddresses.Contains(ip)) valids.Add(ip); else inValids.Add(ip); }

Output of the result

 Console.WriteLine($"vailds: {valids.Count}, inValids: {inValids.Count}");

Result

 vailds: 73, inValids: 699927

On my not very powerful pc - 1.5 seconds.

and if before a cycle it is preliminary to sort these 700 000 lines?
before the cycle, but including the sorting time in the final
@Grundy together with useless sorting 700k entries on my machine - 7 seconds
@ tym32167, there was an assumption that sorting of the vehicle just slows down everything :-)

How to speed up binary search? or pass 400 thousand items

1 answer 1

More articles: