2

I need the best way to do prefix based operations in c#.

I have the following data.

prefix  price   parent_id   
1       0.0031  6   
1201    0.0021  29
1201555 0.0061  6
1204    0.0014  29
12045   0.0020  6
1205    0.0021  6

Resultant should look like

prefix  price   parent_id   
1       0.0031  6   
1201    0.0021  29
1204    0.0014  29
1205    0.0021  6

So result should avoid a prefix with more cost than its sub-prefix, but if bigger prefix belongs to same parent of sub prefix that has lowest cost then it should consider it as well.

I have made it work using following code, but it is taking too much time. It takes around 1 minute to process 5000 prefixes but I have around 150000.

public class Prefixes
    {
        public string prefix { get; set; }
        public decimal price { get; set; }
        public int i_parent { get; set; }
    }

C# code : (objList has all the prefixes)

        List<Prefixes> templist = new List<Prefixes>();
        List<Prefixes> toAvoidList = new List<Prefixes>();

        foreach (var item in objList.OrderByDescending(x => x.prefix.Length))
        {
            if (templist.Contains(item))
                continue;

            var temp = objList.Where(s => item.prefix.StartsWith(s.prefix)).ToList();

            if (temp.Count > 0)
            {
                var lowerPricesPrefixes = temp.Where(x => x.price < item.price).Except(templist).ToList();
                templist.AddRange(lowerPricesPrefixes);
            }
            else
            {
                templist.Add(item);
            }
        }

Please help and advise what could be optimized.

Thanks

Jitender Sharma
  • 119
  • 3
  • 13
  • Try to not use LINQ, see this: https://stackoverflow.com/questions/4044400/linq-performance-faq – AsfK Feb 19 '18 at 07:30
  • @AsfK no amount of replacing LINQ with raw loops will speed up O(n^2) to O(n)... Usually what would happen is people rewrite code like `Distinct` from O(n) LINQ version to O(n^2) "optimized" version with loops :) – Alexei Levenkov Feb 19 '18 at 07:39
  • Check if "trie" is data structure you've learnt prior this assignment as it feels like what you should be practicing... – Alexei Levenkov Feb 19 '18 at 07:42
  • @AsfK - I was able to achieve this using LINQ only and I was thinking If I could somehow optimize it. But like Alexei said - may be Trie is the way to go but I never had used it earlier would give it a try. – Jitender Sharma Feb 19 '18 at 07:53
  • Not sure about LINQ performance, anyway please try use hashmap instead `list` for `tempList` and `toAvoidList` (`Dictionary`) – AsfK Feb 19 '18 at 15:32

0 Answers0