选择相关对象的前N个元素

Question

我有一个类Product来保存给定产品的特定实例.此类包含与主要产品类似的相关产品列表.

class Product
{
    public string Name;
    public double Rating;
    public List<Product> RelatedProducts;
    //...
    public List<Product> GetTopRelatedProducts(int N)
    {
        // How to implement this method
        // What I did so far(Bad code)
        //     1- INFINITE RECURSION
        //     2- Can not remember visited objects
        var myList = new List<Product>();
        foreach(Product prod in RelatedProducts)
        {
             myList.AddRange(prod.GetTopRelatedProducts(N));
        }
        return myList.Distinct().OrderByDescending(x => x.Rating).Take(N).ToList();
    }
}

我想在Product课堂上定义一种方法来获得最佳N(评价最高)的相关产品.此方法应考虑RelatedProducts列表中的元素是类型,Product并且它们也有自己的RelatedProducts列表.因此,我应该继续导航嵌套对象,直到达到所有相关产品,然后取出前N个产品.我的意思是,解决方案不会简单this.RelatedProducts.OrderByDescending(x => x.Rating).Take(N);

还有一点要记住:两种产品可以相互关联.这意味着一个产品一个可以属于RelatedProducts列出产品的乙和乙也可以属于RelatedProducts产品的列表一个.

有什么建议如何以最佳方式解决这个问题？

想象一下,我有数以百万计的产品需要维护.如何递归浏览所有相关产品并识别已访问过的产品？

我将其标记为C#和Java,因为相同的逻辑可以应用于两种语言

Answer 1

想象一下,我有数以百万计的产品需要维护.如何递归浏览所有相关产品并识别已访问过的产品？

它不需要递归.明确Stack或Queue可以为导航部分服务.为了收集结果,HashSet可以使用而不是List.它有两个目的 - 允许您跳过已经访问过的元素,并且Distinct最终消除了需要.

以下是基于示例Queue的实现:

public List<Product> GetTopRelatedProducts(int N)
{
    var relatedSet = new HashSet<Product>();
    var relatedListQueue = new Queue<List<Product>>();
    if (RelatedProducts != null && RelatedProducts.Count > 0)
        relatedListQueue.Enqueue(RelatedProducts);
    while (relatedListQueue.Count > 0)
    {
        var relatedList = relatedListQueue.Dequeue();
        foreach (var product in relatedList)
        {
            if (product != this && relatedSet.Add(product) && product.RelatedProducts != null && product.RelatedProducts.Count > 0)
                relatedListQueue.Enqueue(product.RelatedProducts);
        }
    }
    return relatedSet.OrderByDescending(x => x.Rating).Take(N).ToList();
}

更新:为了完整性,以下是相关集合收集部分的其他可能实现:

明确Stack:

public List<Product> GetTopRelatedProducts(int N)
{
    if (RelatedProducts == null || RelatedProducts.Count == 0)
        return new List<Product>();
    var relatedSet = new HashSet<Product>();
    var pendingStack = new Stack<List<Product>.Enumerator>();
    var relatedList = RelatedProducts.GetEnumerator(); 
    while (true)
    {
        while (relatedList.MoveNext())
        {
            var product = relatedList.Current;
            if (product != this && relatedSet.Add(product) && product.RelatedProducts != null && product.RelatedProducts.Count > 0)
            {
                pendingStack.Push(relatedList);
                relatedList = product.RelatedProducts.GetEnumerator();
            }
        }
        if (pendingStack.Count == 0) break;
        relatedList = pendingStack.Pop();
    } 
    return relatedSet.OrderByDescending(x => x.Rating).Take(N).ToList();
}

虽然比Queue基于显式的实现更冗长,但此方法具有更少的空间要求 - O(高度),其中height是最大深度.

迭代实现的好处当然是它们可以处理比可能导致的递归解决方案更大的深度StackOverflowExpection.但是如果预计深度不会那么大并且您更喜欢递归,那么这里有一些递归实现(他们只需要访问relatedSet和this):

使用经典的私有递归方法:

public List<Product> GetTopRelatedProducts(int N)
{
    var relatedSet = new HashSet<Product>();
    GetRelatedProducts(this, relatedSet);
    return relatedSet.OrderByDescending(x => x.Rating).Take(N).ToList();
}

private void GetRelatedProducts(Product product, HashSet<Product> relatedSet)
{
    if (product.RelatedProducts == null) return;
    foreach (var item in product.RelatedProducts)
        if (item != this && relatedSet.Add(item))
            GetRelatedProducts(item, relatedSet);
}

使用递归lambda:

public List<Product> GetTopRelatedProductsD(int N)
{
    var relatedSet = new HashSet<Product>();
    Action<Product> GetRelatedProducts = null;
    GetRelatedProducts = product =>
    {
        if (product.RelatedProducts == null) return;
        foreach (var item in product.RelatedProducts)
            if (item != this && relatedSet.Add(item))
                GetRelatedProducts(item);
    };
    GetRelatedProducts(this);
    return relatedSet.OrderByDescending(x => x.Rating).Take(N).ToList();
}

最后,但并非最不重要的是,添加了最新的C#7.0 - 递归本地函数:

public List<Product> GetTopRelatedProducts(int N)
{
    var relatedSet = new HashSet<Product>();
    GetRelatedProducts(this);
    return relatedSet.OrderByDescending(x => x.Rating).Take(N).ToList();

    void GetRelatedProducts(Product product)
    {
        if (product.RelatedProducts == null) return;
        foreach (var item in product.RelatedProducts)
            if (item != this && relatedSet.Add(item))
                GetRelatedProducts(item);
    }
}

所有这些方法最佳地处理(IMO)收集部分.前N部分当然不是最优的 - O(N*log(N))并且可以如@Amit Kumar的答案中所述进行优化,但它需要实现缺少的标准数据结构,这超出了SO的范围回答.