What is the best data structure to use when adding elements to list based on comparisons c#

Question

  List<string> allApps = new List<string>();
        roster = MURLEngine.GetUserFriendDetails(token, userId);
        var usersfriends = from elements in roster.RosterEntries
                           where elements[0] == 'm' && elements[1] >= '0' && elements[1] <= '9'
                           select elements;
        foreach (string userid in usersfriends)
        {
            roster = MURLEngine.GetUserFriendDetails(token, userid);
            var usersapps = from elements in roster.RosterEntries
                            where elements[0] != 'm'
                            select elements;
            allApps.AddRange(usersapps);

            allApps = allApps.Distinct().ToList();
        }



        int countapps = 0;
        List<string> Appname = new List<string>();
        countapps = appList.Count();

        for (int y = 0; y < countapps; y++)
        {
            foreach (string li in allApps)  // 
            {
                bool istrueapp = appList.ElementAt(y).AppName.Equals(li);
                if (istrueapp == true)
                {
                    Appname.Add(appList.ElementAt(y).AppName);
                }
            }
        }

In the code above i am first getting a list of strings i.e. usersfriends then based on those id's i am getting the list of apps for the user and then adding all the apps of all users to another List i.e. allApps hence the whole process is slow it takes around 20 seconds to perform this using Lists. tried using a HashSet and a SortedSet also but it was even more slower.

My questions is what datastructure should i be using for this scenario ??

Would really help me

Answer 1

My favorite thing about LINQ is that it lets you describe what you want to do, rather than making you write a bunch of loops which obscure your goals. Here's a refactored version of your code which I think is pretty clear, and which runs faster in my testbed (0.5s vs ~15s).

// create a hashset for fast confirmation of app names
var realAppNames = new HashSet<string>(appList.Select(a => a.AppName));

var roster = MURLEngine.GetUserFriendDetails(token, userId);

// get the ids of all friends
var friendIds = roster.RosterEntries
                      .Where (e => e[0] == 'm' && e[1] >= '0' && e[1] <= '9');

var apps = 
    friendIds 
    // get the rosters for all friends
    .SelectMany (friendId => MURLEngine.GetUserFriendDetails(token, friendId)).RosterEntries)
    // include the original user's roster so we get their apps too
    .Concat(roster.RosterEntries) 
    // filter down to apps only
    .Where (name => name[0] != 'm' && realAppNames.Contains(name)) 
    // remove duplicates
    .Distinct()
    // we're done!
    .ToList();

Answer 2

Ok, what can I suggest so far.

Firstly: you've got a lot of Add's.
In general default List<T> is not the best datastructure for lot of Add's, because internally it's implemented as array which is destroyed and copied to larger one when it's full.
Two options are possible:
- create list with predefined capacity: List<string> allApps = new List<string>(countOfApps);. This one is good if you can roughly calculate count of items that are to be added to list in advance.
- use LinkedList<string> allApps = new LinkedList<string>(). LinkedList does adding new items pretty fast.

Same stuff is true for List<string> Appname = new List<string>(); list.

Secondly: at the beginning you've got list which is distinct-ed and then converted to list on each iteration of foreach-loop, while the newly constructed list is not used in that loop. So here you can move that distinct->tolist code out of the loop, the code logic won't change, but performance will increase.

So far I can suggest the following code:

 LinkedList<string> allApps2 = new LinkedList<string>();// linkedlist here
        roster = MURLEngine.GetUserFriendDetails(token, userId);
        var usersfriends = from elements in roster.RosterEntries
                           where elements[0] == 'm' && elements[1] >= '0' && elements[1] <= '9'
                           select elements;
        foreach (string userid in usersfriends)
        {
            roster = MURLEngine.GetUserFriendDetails(token, userid);
            var usersapps = from elements in roster.RosterEntries
                            where elements[0] != 'm'
                            select elements;
            foreach(var userapp in usersapps)// add _all the apps_ to list. Will be distinct-ed later
            {
                allApps2.AddLast(userapp);// don't worry, it works for O(1)
            }

        }

        var allApps = allApps2.Distinct().ToList();

        int countapps = 0;
        LinkedList<string> Appname2 = new LinkedList<string>();// linkedlist here
        countapps = appList.Count();

        for (int y = 0; y < countapps; y++)
        {
            foreach (string li in allApps)  // 
            {
                bool istrueapp = appList.ElementAt(y).AppName.Equals(li);
                if (istrueapp == true)
                {
                    Appname2.AddLast(appList.ElementAt(y).AppName);// and here
                }
            }
        }

        var AppName = Appname2.ToList();// and you've got you List<string> as the result

Please, try this code and let me know how it works(though I think it should work considerably faster). Hope this helps.

UPDATE
Finally I'm home, sorry for delay. I played with code a bit and made it faster by rewriting last for into this:

foreach (var app in appList)
            {
                foreach (string li in allApps) 
                {
                    bool istrueapp = app.AppName.Equals(li);
                    if (istrueapp)
                    {
                        Appname2.AddLast(app.AppName);
                    }
                }
            }

That gave great speed-up, at least on my machine(r).
Please check whether it's faster on your environment.
Hope that helps.

Answer 3

You should keep allApps inside a dictionary keyed by the appname. To check if the app exists in appList simply look for allApps.Contains(li).

The problem most likely originates from the last for loop, its complexity seems like O(n^2). Using a dictinoary should reduced complexity to O(n*logn) and thus solve the problem.

Answer 4

As already commented in another answer, a List is not too efficient while dealing with a high number of elements and performing simple actions. Simpler collections (e.g., Array) represent a more efficient solution under these conditions. Sample code (adapted to deal with "plain" arrays; you can use it with the current lists or with arrays in case of start using them):

List<string> Appname = new List<string>();
roster = MURLEngine.GetUserFriendDetails(token, userId);
foreach (string item in roster.RosterEntries)
{
    if(item == null || item.Trim().Length < 1) continue;
    if (item[0] == 'm' && Convert.ToInt32(item[1]) >= 0 && Convert.ToInt32(item[1]) <= 9)
    {
        var roster2 = MURLEngine.GetUserFriendDetails(token, item);
        foreach (string item2 in roster2.RosterEntries)
        {
            if(item2 == null || item2.Trim().Length < 1) continue;
            if (item2[0] != 'm')
            {
                bool found = false;
                foreach (string app in appList)
                {
                    if(app == null || app.Trim().Length < 1) continue;
                    if (app.AppName == item2)
                    {
                        found = true;
                        break;
                    }
                }
                if (found) Appname.Add(item2);
            }
        }
    }
}

As you can see, I have ignored the intermediate storage to allApps (can also be done in your version via query).

This code should deliver a noticiable improvement with respect to the original version (mainly when you will convert the list into arrays). In case of being interested in speeding this code even further, you should consider the option of re-designing the way in which the inputs are provided (and thus avoiding what, presumably, is the most time consuming bit: calling MURLEngine.GetUserFriendDetails twice). Finally, bear in mind that you can replace the (string app in appList) loop with a simple condition (AppNames.Contains(item2)), by storing the AppNames in a List/Array.