Working on a list takes too much time

Question

Here is my class:

public class Record
{
   public string PersonName {get; set;}
   public string RequestID {get; set;}
}

I have a db table related to this class And I'm pulling all of it to memory at start. And I'm trying to find a relation between two people with the following algorithm :

1. I pick two people(I mean records from that list, there can be multiple records of both properties)
2. I list first person's RequestIDs
3. For each RequestID, I list users with the same RequestID
4. For each user, I check if that user has the same RequestID with the second user.
5. If found, break and do stuff.

Here is my implementation of above algorithm :

foreach(var elem in listofFirstPerson)
{
  List<Record> listofRelatedPeople = RecordList.Where(r => r. RequestID == elem.RequestID).ToList(); //I actually get distinct records from actual list and the distinct version count is about 100k

  foreach(var relatedPerson in listofRelatedPeople )
  {
    List<Record> listofRecordsforRelatedPerson = RecordList.Where(r => r. PersonName ==  relatedPerson.PersonName).ToList();

    for(int i = 0; i < listofRecordsforRelatedPerson.Count; i++)
    {
      for(int j = 0; j < listofSecondPerson.Count; j++)
      {
       if(listofRecordsforRelatedPerson[i].RequestID ==listofSecondPerson[j].RequestID)
        //break all loops and do stuff
      }
    }
  }
}

This algorithm works. But it is incredibly slow. As I mentioned listofRelatedPeople is about 100k and it iterates only a few hundreds of records in about 20 seconds. How can I make this algorithm faster? Is there a faster approach? Thanks in advance.

EDIT :

In my list there are records like this :

• Name : "Jason" RequestID : "1"
• Name : "Larry" RequestID : "1"
• Name : "Kevin" RequestID : "7"
• Name : "Joshua" RequestID : "4"
• Name : "Tom" RequestID : "1"
• Name : "Tom" RequestID : "7"
• Name : "Ben" RequestID :"7"

Suppose I pick Jason and Kevin, as you see their Request IDs are not same so I need to find a relation between them. So I list users with the same RequestID and they are Larry and Tom. Then I get all records with Larry and I see that he doesn't have a record with the same RequestID with Kevin. Therefore I go to Tom, I see that Tom has the same RequestID with Kevin, so I pick Tom and it is done.

Answer 1

The way I understand it, your current algorithm can be expressed in LINQ as follows:

static Record FirstRelated(List<Record> records, string firstName, string secondName)
{
    var listofFirstPerson = records.Where(r => r.PersonName == firstName).ToList();
    var listofSecondPerson = records.Where(r => r.PersonName == secondName).ToList();
    var result = (
        from r1 in listofFirstPerson // (1)
        from r2 in records //(2)
        where r2.RequestID == r1.RequestID
        from r3 in records // (3)
        where r3.PersonName == r2.PersonName
        from r4 in listofSecondPerson // (4)
        where r4.RequestID == r3.RequestID
        select r2
    ).FirstOrDefault();
    return result;
}

So basically you have 4 nested loops. If we designate

N = records.Count
M1 = listofFirstPerson.Count
M2 = listofSecondPerson.Count

then the time complexity of the algorithm will be O(M1 * N * N * M2), which with big N is normal to cause performance issues.

Looking at the above implementation, it can be noticed that the same result can be achieved by consolidating (1) with (2), (3) with (4) and correlating the resulting sets by PersonName:

var firstRelated =
    from r1 in listofFirstPerson
    from r2 in records
    where r2.RequestID == r1.RequestID
    select r2;
var secondRelated =
    from r4 in listofSecondPerson
    from r3 in records
    where r3.RequestID == r4.RequestID
    select r3;
var result = (
    from r1 in firstRelated
    from r2 in secondRelated
    where r2.PersonName == r1.PersonName
    select r1
).FirstOrDefault();

So far we didn't improve anything - the algorithm is still the same quadratic time complexity. But it gives us the idea - since now the firstRelated and secondRelated are independent, there is no need to execute secondRelated for each record of the firstRelated, so instead we can prepare a fast hash lookup data structure from secondRelated in advance (with average O(1) lookup time complexity), and use it when iterating once the firstRelated, leading to much better O(M1 * N) time complexity (almost like eliminating the cost of the last two inner loops in your code which are causing the slowness).

Also note that we don't need to build the two initial lists anymore because we are going to process the firstRelated and secondRelated only once.

So the final solution would be something like this:

var firstRelated =
    from r1 in records
    where r1.PersonName == firstName
    from r2 in records
    where r2.RequestID == r1.RequestID
    select r2;
var secondRelated =
    from r4 in records
    where r4.PersonName == secondName
    from r3 in records
    where r3.RequestID == r4.RequestID
    select r3;

and now either use the LINQ join operator to do the efficient correlation for us:

var result = (
    from r1 in firstRelated
    from r2 in secondRelated
    where r2.PersonName == r1.PersonName
    select r1
).FirstOrDefault();

or do it manually by preparing and using a HashSet with PersonName from the secondRelated:

var secondRelatedNames = new HashSet<string>(secondRelated.Select(r => r.PersonName));
var result = firstRelated.FirstOrDefault(r => secondRelatedNames.Contains(r.PersonName));

Answer 2

Both ".Where()" and ".ToList()" are quite slow operations.

You can map your "RecordList" to a two dictionaries one with "RequestID" as key another with "PersonName". Do it before forech. This should run much faster.

var dictionary1 = RecordList.GroupBy(f => f.RequestID).ToDictionary(f => f.Key, v => v.ToArray());
var dictionary2 = RecordList.GroupBy(f => f.PersonName).ToDictionary(f => f.Key, v => v.ToArray()); 

and then inside foreach you can use them as

var listofRelatedPeople = dictionary1[elem.RequestID];
var listofRecordsforRelatedPerson= dictionary2[relatedPerson.PersonName];

Of course, if there is a possibility that key will not exist, better to use dictionary1.TryGetValue()

UPDATE

If you need it C# way, one of the solution could be:

var recordList = new Record[]
{
    new Record() {RequestID = "1", PersonName = "User1"},
    new Record() {RequestID = "2", PersonName = "User1"},
    new Record() {RequestID = "3", PersonName = "User2"},
    new Record() {RequestID = "1", PersonName = "User2"},
    new Record() {RequestID = "4", PersonName = "User3"},
    new Record() {RequestID = "5", PersonName = "User3"},
    new Record() {RequestID = "1", PersonName = "User4"},
    new Record() {RequestID = "6", PersonName = "User4"},
    new Record() {RequestID = "7", PersonName = "User5"},
    new Record() {RequestID = "1", PersonName = "User5"},

};
var dictionary1 = recordList.GroupBy(f => f.RequestID).ToDictionary(f => f.Key, v => v.Select(z=>z.PersonName).ToArray());
var dictionary2 = recordList.GroupBy(f => f.PersonName).ToDictionary(f => f.Key, v => v.Select(z => z.RequestID).ToArray());

var rec1 = dictionary2["User1"]; //all requestsIds for User1
var rec2 = dictionary2["User2"]; //all requestsIds for User2

var ids = rec1.Intersect(rec2).Distinct();  //only request ids exists for both users in same time

foreach (var id in ids)
{
    var users = dictionary1[id];
    if (users.Length > 2)
        break;
    //users = User1, User2, User4, User5
}

UPDATE 2

SQL version (MSSQL) this will work a WAY much faster then C#

CREATE TABLE #tmp (ID varchar(max), Name varchar(max))
INSERT INTO #tmp (ID, Name) 
SELECT '1', 'User1' UNION ALL
SELECT '2', 'User1' UNION ALL
SELECT '3', 'User2' UNION ALL 
SELECT '1', 'User2' UNION ALL 
SELECT '4', 'User3' UNION ALL 
SELECT '5', 'User3' UNION ALL 
SELECT '1', 'User4' UNION ALL 
SELECT '6', 'User4' 


SELECT C.Name 
FROM #tmp A
INNER JOIN #tmp B ON A.ID = B.ID
INNER JOIN #tmp C ON A.ID = C.ID
WHERE A.Name = 'User1' and B.Name = 'User2' AND C.Name NOT IN ('User1', 'User2')

Response will be "User4"

Answer 3

I think you should let the database do the work, it will be much faster.

The query would look something like this:

SELECT
    r2.*
FROM
    record r1 INNER JOIN
    record r2 ON
        r2.requestId = r1.requestId AND
        r2.personName = 'NAME 2'
WHERE
    r1.personName = 'NAME 1'

We request all the requestIds of person 1 and see if it matches any of those from person 2.

Answer 4

The grouping could be done in one pass. The advantage of this is not only that it is faster because it's a single pass, but if you are doing LINQ to DB then it will be executed on the server by the DB, reducing the amount of data sent to your client and speeding up the process by using indexes etc.

        var source = new List<Record> { };
        var grouped = source
            .GroupBy(x => x.RequestID)
            //Only groups with more than one entry
            .Where(x => x.Count() > 1);

        //Loop through the data like so
        foreach(var group in grouped)
        {
            Console.WriteLine("Request: " + group.Key);
            foreach(Record record in group)
                Console.WriteLine("  " + record.PersonName);
        }

If you want the PersonName property to be some kind of unique identifier so that you can eliminate cases where the same person exists more than once per RequestID you can do this

        var source = new List<Record> { };
        var grouped = source
            .GroupBy(x => x.RequestID)
            //Select a key + only unique names
            .Select(x => new { Key = x.Key, Data = x.Select(r => r.PersonName).Distinct()})
            //Only groups with more than 1 entry
            .Where(x => x.Data.Count() > 1);

        //To loop through the data
        foreach(var group in grouped)
        {
            Console.WriteLine("Group: " + group.Key);
            foreach(var item in group.Data)
            {
                Console.WriteLine("  " + item.PersonName);
            }
        }

Answer 5

ums maybe a little thing but, u create use recordlist to much. you have created new objects but didn't use it. so you didn't do anything with your where clause.

List<Record> listofRecordsforRelatedPerson = RecordList.Where(r => r. PersonName  

--> change recordlist to relatedPeople and in your two for loops use:

for(int j = 0; j <= listofSecondPerson.Count; j++)
{...} 

otherwise for example if your count is 25 anj = 25 it will do nothing lol