The Fastest DataStructure to Filter with in C#

Question

Currently we are filtering and sorting data with a datatable.

    /// <summary>
    /// Filters the data table and returns a new data table with only the filtered rows.
    /// </summary>
    /// <param name="dtInput">The dt input.</param>
    /// <param name="filterExpression">The filter expression.</param>
    /// <returns></returns>
    protected virtual DataTable FilterDataTable(DataTable dtInput, string filterExpression)
    {
            DataTable t1 = dtInput.Clone();
            if(!string.IsNullOrEmpty(filterExpression) && filterExpression.Trim().Length > 0)
            {
                t1.BeginLoadData();
                foreach (DataRow r in dtInput.Select(filterExpression))
                {
                    t1.Rows.Add(r.ItemArray);
                }
                t1.EndLoadData();
            }
            else
            {
                t1 = dtInput;
            }

        return t1;
    }

Is there another Collection/Container that is optimized to do this type of filtering/sorting ? We are looking at the SortedList or a Dictionary. It's currently taking 15 to 25 seconds to sort and filter on a DataTable.

Data Sample

HierarchyNodeId ParentHierarchyNodeId NodeName  ExternalIdentifier
    71 57 Skin Care Preparations - 3400 3400
    72 56 UNKNOWN - 1110 1110
    73 57 Sanitary Protection - 3380 3380
    74 57 Kitchen Gadgets - 2890 2890
    75 45 Seasonal GM - 2970 2970
    76 52 UNKNOWN - 2500 2500
    77 45 Juices & Drinks-Refrig - 2100 2100
    78 56 Housewares, Appliances - 2870 2870
    79 45 Condiments/Gravies/Sauce - 1170 1170
    80 63 UNKNOWN - 2325 2325

Filter Sample

HierarchyNodeId in (288,217,503,426,497,211,317,603,612,549,311,526,125,449,520,3071,2919,2624,85,111,3025,297,397,2833,2653,532,194,171,480,380,403,3105,271,457,134,205,632,420,2959,446,105,626,2641,2988,234,334,357,148,572,463,71,509,165,489,303,277,377,483,248,589,197,185,291,583,191,2707,477,500,340,240,552,546,623,2567,523,2773,363,2696,469,177,228,2982,2796,2690,506,320,220,606,114,609,323,2813,394,108,91,383,406,2713,615,268,563,168,560,300,88,2787,374,274,423,82,400,294,188,580,529,137,2942,2601,146,169,432,455,2902,540,440,122,360,145,74,3062,569,2661,460,2685,355,2971,564,2579,461,561,538,3079,351,592,2899,94,586,486,2825,352,275,326,140,246,123,624,547,223,2877,2668,409,2771,117,2897,2659,429,172,381,452,567,272,2582,558,458,166,3003,2791,249,3077,349,484,226,232,252,152,2951,332,354,174,466,2956,280,378,143,243,535,2858,156,182,251,543,331,386,437,3040,100,2646,628,371,159,76,3093,262,368,474,3090,2961,3067,365,471,577,153,130,259,236,2964,574,362,339,127,233,445,342,551,256,2784,77,2616,595,524,601,209,315,309,415,395,545,439,79,2569,548,2781,2910,2672,2993,336,442,438,338,2636,335,97,2851,358,3060,149,126,621,306,2665,183,418,2908,203,389,495,283,464,120,2822,412,2719,229,515,441,255,289,312,527,3014,2805,598,521,103,498,318,212,604,2887,413,625,2820,3034,200,329,541,435,3050,348,454,608,242,139,3114,3120,206,492,421,180,106,129,235,245,2543,2735,2732,136,3032,201,522,307,95,519,416,92,198,304,410,516,3006,133,110,322,216,428,534,345,557,451,239,2835,319,425,301,407,387,493,281,175,622,2643,513,3112,2723,596,490,278,593,2743,2849,384,487,2746,333,227,627,392,286,2699,2681,213,554,531,107,316,210,422,448,2764,222,93,585,2818,2924,328,199,116,225,113,219,2815,631,502,162,525,419,2864,2655,2588,121,98,204,101,2717,230,124,590,2932,537,325,408,87,196,620,514,90,431,302,2638,634,528,2867,142,2986,284,178,617,3001,402,299,511,190,273,614,193,508,296,393,287,181,3095,75,499,605,2880,3118,496,155,602,473,261,405,482,588,2632,505,485,119,379,2847,599,258,2620,364,470,367,2915,361,467,573,576,104,444,2912,78,290,2694,184,313,293,81,187,2591,570,207,128,260,517,414,314,2862,157,417,443,208,131,2936,231,343,629,237,337,2650,478,501,611,399,582,267,370,158,138,479,2860,2754,161,476,264,373,135,244,347,453,132,241,450,344,556,2683,3046,238,553,447,2892,530,550,2571,167,424,84,633,376,164,2889,3098,270,472,555,401,163,269,2917,263,610,607,346,109,160,3074,369,83,375,2808,2702,481,89,581,587,189,2991,504,2711,80,366,2628,266,2885,372,86,398,298,3103,186,292,192,584,285,2692,305,2904,308,202,73,391,179,96,2586,565,411,388,176,279,600,173,2875,494,282,385,276,170,2978,150,253,465,594,491,382,359,488,571,597,2801,99,356,568,2612,462,2560,562,118,221,433,350,436,542,330,3052,224,115,456,327,539,324,112,536,2769,2663,195,218,430,321,510,404,2766,427,2869,147,2657,2554,507,533,616,141,2843,144,247,2634,613,250,3055,2740,353)AND ParentHierarchyNodeId in(44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70)`

And I know this would be much faster in the DB. Currently that's not an option. We are looking at moving this into the database, but the effort and the timeline don't jive. It's a plan for the future.

Answer 1

What about using a HashSet for your SET and testing if a HierarchyModelId is found in the set?

Answer 2

Is LINQ an option for you? (.NET 3.5)

I think you could accomplish this with a LINQ query. The problem is LINQ does not support the IN clause directly. LINQ uses Contains which is sort like a backwards IN clause.

Here is a link that explains Contains and how is can be used like an "IN" http://blog.ninethsense.com/sql-in-clause-in-linq/

Here is a link that gets in specifics about using LINQ with a data table. http://dotnetarchitect.wordpress.com/2009/03/18/using-linq-to-manipulate-data-in-datasetdatatable/