The problem isn't eliminating
for loops, at least in the way that you're thinking of it. Rewriting this in LINQ is just going to hide the
for loops but they'll still be there. And that's the fundamental problem. Your algorithm, as written, is
O(n^2) and that's why you see a ridiculous explosion in time as you go from 20,000 elements to 300,000 elements. You're doing 400,000,000 comparisons in the first case, and 90,000,000,000 in the second case and it will continue to grow like
So, the question you really want to ask is: is there an algorithm with time complexity better than
O(n^2) for this problem?
Frankly, I don't know the answer to that question. I suspect that the answer is no: you can't know if a point is contained in some rectangle without comparing it to all the rectangles, and you have to inspect all the points. But maybe there's a clever way to do it such as computing the convex hull of all the rectangles and use that somehow?
This problem is an example of the field of computational geometry.
- List Operations without ForLoops
- List or Array of String Contain specific word in Html Source Code
- c# Linq or code to extract groups from a single list of source data
- How to count the number of code lines in a C# solution, without comments and empty lines, and other redundant stuff, etc?
- Check if IEnumerable has ANY rows without enumerating over the entire list
- How to implement SkipWhile with Linq to Sql without first loading the whole list into memory?
- Generating the Shortest Regex Dynamically from a source List of Strings
- List operations related to another list's conditions
- Is there any way to create a LINQ query as a variable without having the data source (yet)?
- LINQ Source Code Available
- Convert list of of objects to list of tuple without iterating
- Is it possible to ignore a list item using the Skip method of the LINQ then apply skip on the list without losing that item?
- Entity Framework Code First without app.config
- .NET 4 Code Contracts: "requires unproven: source != null"
- Updating single Column of List without Foreach Loop
- Grouping a list into sublists by key/attribute without changing the list order (just chop into lists by attrib)
- LINQ query over a list of Bool+String pairs. How to join strings without foreach?
- Merge duplicate data without affecting others in LINQ code
- C# List to Dictionary without Foreach [ERROR]
- How to find first occurrence in c# list without going over entire list with LINQ?
- LINQ query returns old results when source list is re-initialized
- Copy a list of objects to another typed list in one line of code
- How to get the last value from a model list without looping it in MVC?
- C# - Linq optimize code with List and Where clause
- How do I compare items from a list to all others without repetition?
- creating Linq to sqlite dbml from DbLinq source code
- Mixing local list operations with linq to entities database operations
- Group a sorted list without affecting the sorting in linq
- ef code first: get entity table name without dataannotations
- How can i copy data table records of different field name based on mapping list evaluating condition on source data table?
- LINQ Many to Many With In or Contains Clause (and a twist)
- Linq, where entity property contains another list
- Can my two linq lines of code be combined?
- EF.Functions.Like in a compiled query could not be translated to SQL equivalent
- finding last saved id using NHibernate LINQ
- extract generic list from generic list using linq
- Group by multiple enumerables in LINQ
- Linq query for top parents by number of childs, including this number
- How to remove Distinct values from a list?
- Linq is producing unintended sql with left outer join
- Need help in converting SQL query to LINQ
- Convert Entity data model to Data Transfer Object
- ASP.NET MVC Search Page - Integer StartsWith On Linq + EF4
- Linq Passing table as an object to Table<t>
- Using List.Find or LINQ on lists of enums in .NET 3.5
- linq nested list contains
- Convert object to KeyValuePair
- linq to sql join result
- EF4.1 LINQ, selecting all results
- How to retrieve the specific indexes from array?