java - 选取相关对象的前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);

还有一点要记住:两个产品可以相互关联。这意味着产品 A 可以属于 RelatedProducts 产品列表 B 和 B 也可以属于 RelatedProducts 产品列表A。

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

想象一下，我有数百万个产品需要维护。我如何递归地导航所有相关产品并识别已经访问过的产品？

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

Answer 1

Imagine, I have millions of products to maintain. How can I navigate all related products recursively and recognize already visited ones?

它不需要是递归的。显式 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();
}

更新:为了完整起见，这里是相关集收集部分的其他可能实现:

使用显式堆栈:

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) 其中 height 是最大深度。

这两种迭代实现的好处当然是它们可以处理比递归解决方案更大的深度，递归解决方案可能导致 StackOverflowExpection。但是如果深度不期望这么大并且你更喜欢递归，那么这里有几个递归实现(他们需要访问 relatedSet 和 this) :

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

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 添加 - 递归 local function :

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 答案的范围。