Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have two DataTables:

  • dt: is populated from a CSV file with over 1.7 million rows
  • dataStructure.Tables["AccountData"]: is populated from a database query also roughly a million rows

I use the following code to iterate through and compare the data from each set of rows. The code takes over 48 hours to complete. I have changed the properties of the application to x64 to allow it to use more Process Memory. It now uses roughly 2.5GB.

My question is, is there a more efficient way of doing this that would decrease run time?

//set is_legal column value for each row
foreach (DataRow row in dt.Rows)
{
    var acctNum = row[0].ToString().Replace("\"", "");
    foreach (DataRow queryRow in dataStructure.Tables["AccountData"].Rows)
    {
        var queryAcctNum = queryRow[0].ToString();
        if (acctNum.Equals(queryAcctNum))
        {
            row[12] = "Y";
            Console.WriteLine("Yes count: " + cnt);
        }
        else
        {
            row[12] = "N";
        }
    }
    cnt++;
};

How dataStructure.Tables["AccountData"] is being populated:

//Read each row from the table and output the results into the data set
while (readFile.Read())
{
    //Create a row to hold data
    DataRow datarow = dataStructure.Tables["AccountData"].NewRow();

    datarow["AccountNumber"] = readFile.GetString(0).Trim();
    datarow["LegalStatus"] = readFile.GetString(1);

    //add the row to the data table AccountData
    dataStructure.Tables["AccountData"].Rows.Add(datarow);
}
share|improve this question
7  
Is the Console.WriteLine in your real code? You'll have to run a profiler to find what is taking the time but that's where I'd put my money. – RobH Feb 16 at 14:57
1  
This looks like it's broken. You're not break;ing after finding a match so all records will likely have row[12] == "N". – Johnbot Feb 16 at 15:02
    
@Johnbot thats a good catch you should make this an answer! – Heslacher Feb 16 at 15:04
6  
Why are you doing this operation in memory in the first place? Pour all the data into a database, add the appropriate indices, write the query you want to write in SQL, and make the database optimize the query; that's what it's good at. – Eric Lippert Feb 17 at 0:32
3  
I'm amazed is that you had the patience to wait for 48 hours to see how long it takes. I mean, this code is horribly inefficient, but that sort of patience has to count for something. – Matti Virkkunen Feb 17 at 16:25
up vote 51 down vote accepted

Your inner loop appears to be unnecessary. Why not create a lookup:

var knownAccountNumbers = new HashSet<string>(
    dataStructure.Tables["AccountData"].Rows
        .Cast<DataRow>()
        .Select(row => row[0].ToString()));

Now your loop is simply:

foreach (DataRow row in dt.Rows)
{
    var accountNumber = row[0].ToString().Replace("\"", "");
    row[12] = knownAccountNumbers.Contains(accountNumber) ? "Y" : "N";
}

I think I remember reading once that the memory usage of a HashSet is 12 bytes per entry + size of the entry. So you're looking at 12MB + 1,000,000 * (2 * accountNumber.Length). So basically nothing in the grand scheme of things. However, you are gaining constant time lookups which should be a huge benefit to this kind of work.


You should take more care when naming things. Don't abbreviate e.g. acctNum -> accountNumber.

share|improve this answer
23  
This solution took 17 seconds. – HappyCoding Feb 16 at 15:36
1  
@HappyCoding - That's good to hear! :) – RobH Feb 16 at 15:48
    
knownAccountNumbers are lazily evaluated each time Contains is called. There should really be a .ToList() or .ToDictionary() at the end. – Esben Skov Pedersen Feb 17 at 14:27
3  
@EsbenSkovPedersen - That's not how it works. The enumerable is evaluated in HashSet's constructor. You can confirm yourself using the reference source. It ends up calling UnionWith which enumerates the enumerable. – RobH Feb 17 at 15:04
2  
@EsbenSkovPedersen - I'm going to have to disagree again. I don't want a dictionary (key -> value) I just need a simple fast lookup based on key - i.e. the hashset. – RobH Feb 17 at 20:01

The code appears to be broken, you're not break;ing after finding a match so all records will likely have row[12] == "N".

You should really be doing a join on accountNumber:

var matchingRows =
    from DataRow row in dt.Rows
    let rowKey = row[0].ToString().Replace("\"", "")
    join DataRow queryRow in dataStructure.Tables["AccountData"].Rows
    on rowKey equals queryRow[0]
    select row;

foreach(var row in matchingRows)
{
    row[12] = "Y";
}

This way you'll stop searching at the first match and only update the matching rows.

share|improve this answer
3  
This solution took 16 seconds. – HappyCoding Feb 16 at 15:37
    
After execution, matchingRows only contains those rows that matched rather than the initial set of data. – HappyCoding Feb 16 at 15:45

A few comments:

Avoid memory intensive data types

Instead of using a DataTable for dt, just read from the csv directly, one line at a time (readLine() and then split(','). This will greatly cut down on your memory usage, rather than loading all 1.7 million rows at once, when you only use one at a time.

Sorted data is faster

Sort dataStructure by account number. After that you can do a binary search to find the account number(s) and break after you have iterated over it/them. This will greatly cut down your loop time. If you can get the database to sort the data before you read it into dataStructure, even better.

Alternative Idea

You could also try loading all of dt into a temporary table in the same database that dataStructure came run, and then used a stored procedure to do the update. The database will be able to do this update much more efficiently than looping in C# can

share|improve this answer
3  
-1 for recommending naive csv parsing – Winston Ewert Feb 17 at 1:23
    
@WinstonEwert Can you explain why that's a bad thing? – Sam Cousins Feb 17 at 13:47
    
If the CSV has lots of escaping (commas that are part of text, which then get quoted, and then the quoting needs escaping), then splitting could be problematic. If the csv data is "safe" then I don't see any disadvantages to the suggestion – Zack Feb 17 at 15:04
    
Depending on the database you can even declare the CSV file as an external table and run a single UPDATE statement, which will BULK Update all rows with an optimized query, without any worries about IO. – Falco Feb 17 at 17:12
    
If the CSV has a single escaped cell, splitting will give you the incorrect results. When you can guarantee that none of the cells will be escaped, you can get away with it. But suggesting a naive parsing strategy with regards to a 1.7 million line CSV file you know nothing about, I think is bad advice. – Winston Ewert Feb 18 at 3:42

Based on @Johnbot comment

Right know you are iterating through all the records of dataStructure.Tables["AccountData"] regardless if you have found a match. You really should break out of this loop if acctNum.Equals(queryAcctNum). This should speed up your task a lot (at least if the data could be found).


Another possible enhancement could be to sort the rows of the tables and storing the last found "index" of the inner loop to use it as the start of the next iteration. This would need to change the loops from foreach to a normal for loop which could be faster anyway.

Assuming first column of dt is named "AccountNumber" as well this should speed up the process

    dt.DefaultView.Sort = "AccountNumber";

    var accountDataTable = dataStructure.Tables["AccountData"];
    accountDataTable.DefaultView.Sort  = "AccountNumber";
    int numberOfAccountDataRows = accountDataTable.Rows.Count;
    int currentIndex = 0;

    foreach (DataRow row in dt.Rows)
    {
        var acctNum = row[0].ToString().Replace("\"", "");
        for(int i = currentIndex; i < numberOfAccountDataRows; i++) 
        {

            var queryAcctNum = accountDataTable.Rows[i][0].ToString();
            if (acctNum.Equals(queryAcctNum))
            {
                row[12] = "Y";
                currentIndex = i;
                break;
            }

        }
    }
share|improve this answer

Disclaimer: I do not code in C#, so you might be disappointed. If anyone is willing to port this to C#, please do, it'll probably help the OP more.

Comparing two data-sets for inclusion/exclusion can be done on streams provided that they are sorted.

The algorithm is close to the merge pass of a Merge Sort; in pseudo-code

left = /*sorted stream 1*/
right = /*sorted stream 2*/
while not left.empty() and not right.empty():
    if left.current() == right.current():
        print "Common item", left.current()
        left.moveToNext()
        right.moveToNext()
        continue
    if left.current() < right.current():
        print "Left specific item", left.current()
        left.moveToNext()
        continue
    if left.current() > right.current():
        print "Right specific item", right.current()
        right.moveToNext()
        continue

while not left.empty()
    print "Left specific item", left.current()
    left.moveToNext()

while not right.empty()
    print "Right specific item", right.current()
    right.moveToNext()

Advantages:

  • constant memory
  • fast

Disadvantages:

  • requires both streams to be sorted beforehand

If you can easily obtain both streams in sorted order, it would probably wins hands down.

If you have to prepare a dataset (sorting it), then it is still advantageous for very large datasets (that barely fit in memory).

If both datasets easily fit in memory and one is not sorted, then use another solution (pull the smaller one in a hash-map and look-up into it while iterating over the larger one).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.