c# - 如何从 O(1) 中匹配特定条件的数组中选择随机元素

Question

我有一个从数据库中获取的食谱列表，如下所示:

List<RecipeNode> _recipeList;

RecipeNode ，除其他外，具有引用一个或多个标签的属性(例如 Dinner、Breakfast、Side、Vegetarian、Holiday 和其他大约 60 个)。

   public sealed class RecipeNode
   {
      public Guid RecipeId;
      public Byte[] Tags; //Tags such as 1, 5, 6, 8, 43
      //... More stuff
   }

从 _recipeList 中寻找随机食谱在 O(1) 中当然很容易，但是我需要做的是在 Tags 中找到一个随机食谱，比如说，5在 O(1) 中。

现在，我唯一的想法是制作一个 List<RecipeNodes> 的数组, 由标签键控。例如:

List<RecipeNode>[] _recipeListByTag;

然后，_recipeListByTag[5]将包含所有在 Tags 中有 5 的食谱列表大批。然后我可以在 O(1) 中选择一个随机允许的标签和该标签内的一个随机食谱。

这种方法的缺点是这个多维数组的大小是 Recipes * Tags (例如，所有食谱中 Tags.length 的总和)，它开始占用大量内存，因为我在这个数组中存储了潜在的大量食谱。当然，因为 RecipeNode是引用类型，我只是重复指向食谱的 4 字节指针，所以这仍然可能是最好的方法。

是否有更有效的数据结构或算法可以让我找到包含特定允许标签的随机食谱？谢谢!

Answer 1

List<RecipeNode>[] _recipeListByTag可能是最适合您的方法，它的大小不是 Recipes * Tags因为数组中的每个列表将只包含与标签匹配的食谱，而不是更多。它的大小将变为 Recipes * Tags如果每个食谱都包含每个标签。

如果您的数据结构占用的内存量对您来说非常重要，请不要忘记在填充每个列表后调用 List.TrimExcess()。