c# – 数据设计模式的可比较合并

“然后对b c d的请求出现了,通过所有这些可能的组合来确定将b添加到a c d包中会得到所需结果的最佳方法是什么？”

我假设订单无关紧要,因此如果你想要“abcd”,可以将“b”与“acd”合并.唯一重要的是包含哪些元素.

现在,我不知道你使用什么XML或者你如何合并它,所以我用合并字符串编写了这个,并通过简单地连接它们来合并.您将不得不重写Merge方法来执行您想要执行的任何操作(并将字符串更改为您正在使用的任何内容).我也使用整数而不是a,c因为我假设你会比字母表中的字母更多.

此外,例如,当您正在寻找abcdefg,并且缓存中的最佳匹配是cegf时,它还将在缓存中查找余数,abd等的最佳匹配,以便进一步减少数量合并如果您不想这样(如果使用您的xml,则无法将b与c d合并到b c d中),您可以轻松地重写它而不会这样做,但它会平均进行更多合并.

这应该非常快.查看main函数中的注释,了解它的作用.

using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication17
{
    class CachedMerger
    {
        private Dictionary<HashSet<int>,string> _cache = new Dictionary<HashSet<int>,string>();
        private Dictionary<int,string> _items = new Dictionary<int,string>();

        public void AddItem(int index,string item)
        {
            _items[index] = item;
        }

        public void RemoveItem(int index)
        {
            _items.Remove(index);
        }

        private string Merge(string a,string b)
        {
            return a + b;
        }

        private string Merge(HashSet<int> list)
        {
            var sb = new StringBuilder();
            foreach (var index in list)
            {
                if (!_items.ContainsKey(index))
                    return null;
                else
                    sb.Append(_items[index]);
            }

            return sb.ToString();         
        }

        public string Get(HashSet<int> query)
        {
            var bestMatchKey = BestMatchKey(query);
            if (bestMatchKey == null)
            {
                var result = Merge(query);

                if (result == null)
                    throw new Exception("Requested item not found in the item list.");

                _cache[query] = result;
                return result;
            }
            else
            {
                if (bestMatchKey.Count == query.Count)
                    return _cache[bestMatchKey];

                var missing = new HashSet<int>();
                foreach (var index in query)
                    if (!bestMatchKey.Contains(index))
                        missing.Add(index);

                return Merge(_cache[bestMatchKey],Get(missing));
            }
        }

        private HashSet<int> BestMatchKey(HashSet<int> set)
        {
            int bestCount = 0;
            HashSet<int> bestKey = null;
            foreach (var entry in _cache)
            {
                var key = entry.Key;
                int count = 0;
                bool fail = false;
                foreach (var i in key)
                {
                    if (set.Contains(i))
                    {
                        count++;
                    }
                    else
                    {
                        fail = true;
                        break;
                    }
                }

                if (!fail && count > bestCount)
                {
                    bestKey = key;
                    bestCount = count;
                }
            }
            return bestKey;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var cm = new CachedMerger();
            // Add all the base parts
            cm.AddItem(0,"sjkdlajkld");
            cm.AddItem(1,"dffdfdfdf");
            cm.AddItem(2,"qwqwqw");
            cm.AddItem(3,"yuyuyuyy");
            cm.AddItem(4,"kjkjkjkjkj");
            cm.AddItem(5,"oioyuyiyui");

            // This will merge 0 + 1 + 3 + 4 since the cache is empty
            Console.WriteLine(cm.Get(new HashSet<int> { 0,1,3,4 }));
            // This will merge 2 + 5 as there is no match in the cache
            Console.WriteLine(cm.Get(new HashSet<int> { 2,5 }));
            // This will merge (2 + 5) from the cache with 3
            Console.WriteLine(cm.Get(new HashSet<int> { 2,5 }));
            // This will merge (0 + 1 + 3 + 4) from the cache with (2 + 5) from the cache
            Console.WriteLine(cm.Get(new HashSet<int> { 0,2,4,5 }));

            Console.Read();
        }
    }
}