30
\$\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\$
  • 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 '16 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 '16 at 15:02
  • \$\begingroup\$ @Johnbot thats a good catch you should make this an answer! \$\endgroup\$ – Heslacher Feb 16 '16 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\$ – Eric Lippert Feb 17 '16 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\$ – Matti Virkkunen Feb 17 '16 at 16:25
54
\$\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\$
  • 23
    \$\begingroup\$ This solution took 17 seconds. \$\endgroup\$ – HappyCoding Feb 16 '16 at 15:36
  • 1
    \$\begingroup\$ @HappyCoding - That's good to hear! :) \$\endgroup\$ – RobH Feb 16 '16 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\$ – Esben Skov Pedersen Feb 17 '16 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 '16 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 '16 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\$
  • 3
    \$\begingroup\$ This solution took 16 seconds. \$\endgroup\$ – HappyCoding Feb 16 '16 at 15:37
  • \$\begingroup\$ After execution, matchingRows only contains those rows that matched rather than the initial set of data. \$\endgroup\$ – HappyCoding Feb 16 '16 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\$
  • 4
    \$\begingroup\$ -1 for recommending naive csv parsing \$\endgroup\$ – Winston Ewert Feb 17 '16 at 1:23
  • \$\begingroup\$ @WinstonEwert Can you explain why that's a bad thing? \$\endgroup\$ – Josiah Feb 17 '16 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 '16 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 '16 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\$ – Winston Ewert Feb 18 '16 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\$
  • \$\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 '17 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 '17 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 '17 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.