The Fastest DataStructure to Filter with in C#

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,23开发者_JAVA百科4,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.

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

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/