32
\$\begingroup\$

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);
}
\$\endgroup\$
11
  • 7
    \$\begingroup\$ 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. \$\endgroup\$
    – RobH
    Feb 16, 2016 at 14:57
  • 1
    \$\begingroup\$ This looks like it's broken. You're not break;ing after finding a match so all records will likely have row[12] == "N". \$\endgroup\$
    – Johnbot
    Feb 16, 2016 at 15:02
  • \$\begingroup\$ @Johnbot thats a good catch you should make this an answer! \$\endgroup\$
    – Heslacher
    Feb 16, 2016 at 15:04
  • 6
    \$\begingroup\$ 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. \$\endgroup\$ Feb 17, 2016 at 0:32
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ Feb 17, 2016 at 16:25

6 Answers 6

53
\$\begingroup\$

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.

\$\endgroup\$
6
  • 23
    \$\begingroup\$ This solution took 17 seconds. \$\endgroup\$ Feb 16, 2016 at 15:36
  • 1
    \$\begingroup\$ @HappyCoding - That's good to hear! :) \$\endgroup\$
    – RobH
    Feb 16, 2016 at 15:48
  • \$\begingroup\$ knownAccountNumbers are lazily evaluated each time Contains is called. There should really be a .ToList() or .ToDictionary() at the end. \$\endgroup\$ Feb 17, 2016 at 14:27
  • 5
    \$\begingroup\$ @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. \$\endgroup\$
    – RobH
    Feb 17, 2016 at 15:04
  • 4
    \$\begingroup\$ @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. \$\endgroup\$
    – RobH
    Feb 17, 2016 at 20:01
14
\$\begingroup\$

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.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ This solution took 16 seconds. \$\endgroup\$ Feb 16, 2016 at 15:37
  • \$\begingroup\$ After execution, matchingRows only contains those rows that matched rather than the initial set of data. \$\endgroup\$ Feb 16, 2016 at 15:45
8
\$\begingroup\$

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

\$\endgroup\$
8
  • 4
    \$\begingroup\$ -1 for recommending naive csv parsing \$\endgroup\$ Feb 17, 2016 at 1:23
  • \$\begingroup\$ @WinstonEwert Can you explain why that's a bad thing? \$\endgroup\$
    – Josiah
    Feb 17, 2016 at 13:47
  • \$\begingroup\$ 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 \$\endgroup\$
    – Zack
    Feb 17, 2016 at 15:04
  • \$\begingroup\$ 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. \$\endgroup\$
    – Falco
    Feb 17, 2016 at 17:12
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 18, 2016 at 3:42
5
\$\begingroup\$

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;
            }

        }
    }
\$\endgroup\$
3
\$\begingroup\$

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).

\$\endgroup\$
0
\$\begingroup\$

Thanks for @RobH's answer and on top of it Micro-Level Code Optimization, such as:

  • use String Constant
  • in String.Replace use char datatype instead of string datatype
  • knownAccountNumbers value has been added while retrieving itself

var knownAccountNumbers = new HashSet<string>();

//// If AccountData DataTable used only for condition then 
//// Delete Code Related to AccountData DataTable and Use knownAccountNumbers HashSet alone.
DataTable accountDt = dataStructure.Tables["AccountData"];

while (readFile.Read())
{
    string accountNumber = readFile.GetString(0).Trim();

    knownAccountNumbers.Add(accountNumber);

    DataRow dr = accountDt.NewRow();

    dr[AppConst.AccountNumber] = accountNumber;
    dr[AppConst.LegalStatus] = readFile.GetString(1);

    accountDt.Rows.Add(dr);
}

/* ----------------------------------------------------------------------------------------------- */

foreach (DataRow row in dt.Rows)
{
    //// For single char string replace use data type as char instead of string.
    //// Gives more perfromance
    //// var accountNumber = row[0].ToString().Replace(AppConst.BackSlashChar, AppConst.EmptyChar);
    var accountNumber = row[0].ToString().Replace(AppConst.BackSlash, string.Empty);

    //// Use Constant String will not create unnecessary memory allocation.
    row[12] = knownAccountNumbers.Contains(accountNumber) ? AppConst.Yes : AppConst.No;
}

/*------------------------------------------------------------------------------------------------ */

public static class AppConst
{
    public const string Yes      = "Y";
    public const string No       = "N";
    //// public const char   BackSlashChar = '\"';
    //// public const char   EmptyChar = '\0';
    public const string BackSlash = "\"";

    public const string AccountNumber = "AccountNumber";
    public const string LegalStatus   = "LegalStatus";
}
\$\endgroup\$
3
  • \$\begingroup\$ The performance benefit of your code is almost certainly from initialising the Hashset at the same time as building the DataTable. My answer adds an extra loop through all the data to build it which your code doesn't do. \$\endgroup\$
    – RobH
    Jul 5, 2017 at 11:17
  • \$\begingroup\$ @RobH : It is Just Micro Level Code Optimization done on Top of your Answer. Cast Type Coversion, Unboxing, Select Loop are Avoided and String Constant are used for Reducing Memory Consumption and Few Seconds Save.... :-0) \$\endgroup\$
    – Thulasiram
    Jul 5, 2017 at 13:05
  • \$\begingroup\$ The string constants will make no difference to performance - especially memory consumption because C# interns string literals. I don't know what you think you're not boxing that you were before. The only difference I can see is the one I said before: saving an entire iteration through the DataTable. \$\endgroup\$
    – RobH
    Jul 5, 2017 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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