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

Question

在以下场景中是否存在比较数据的模式或最佳实践:

每个字母代表一个数据 block ，在我的例子中是 XML。

a+b+c+d

这些被合并为一个并返回。如果我事先合并了 a+b+c，那么识别这个“包”然后添加 d 将非常简单。但是如果我已经缓存了呢

a+c+d

然后 a+b+c+d 的请求来了，遍历所有这些可能的组合以确定将 b 添加到 a+c+d 包中会得到所需结果的最佳方法是什么？

合并数据的顺序并不重要。虽然它可能不会对答案产生任何影响，但代码是用 C# 4.0 编写的。

编辑再举一个例子:

可能的元素:a,b,c,d,e,f

假设我收到一个请求:a + c + d + e 意思是一个包含 0=a,1=c,2=d,3=e 的数组>

在我的“缓存”中，我有以下内容:c + d + e already merged

然后根据要求我必须找到一种方法来做类似的事情:

if(cache.Contains(request.elements[0]+request.elements[1] etc...))
else(cache.Contains(request.elements[1] + request.elements[2] etc...))

它可能需要某种递归 for 循环，但由于在我的案例中可能的元素最终在 2-5000 范围内，因此它需要尽可能快速和高效。

Answer 1

据此:

“然后出现了对 a+b+c+d 的请求，运行所有这些可能的组合以确定将 b 添加到 a+c+d 包中的最佳方式是什么？想要的结果？”

我假设顺序无关紧要，所以如果您想要“abcd”，可以将“b”与“acd”合并。唯一重要的是包含哪些元素。

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

此外，例如当您正在寻找 a + b + c + d + e + f + g 时，缓存中的最佳匹配是 c + e + g + f，那么它还会在缓存中寻找余数的最佳匹配，a + b + d，以此类推，以进一步减少合并次数。如果你不想要这个(如果你的 xml，你不能将 a + b 与 c + d 合并到 a + 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, 3, 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, 1, 2, 3, 4, 5 }));

            Console.Read();
        }
    }
}