如何从符合O(1)中某个条件的数组中选择一个随机元素

Question

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

List<RecipeNode> _recipeList;

RecipeNode除其他外,有一个属性引用一个或多个标签(如晚餐,早餐,边,素食,假日,和其他约60个).

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

从_recipeListO(1)中查找随机配方当然很容易,但我需要做的是找到一个随机配方,例如Tags在O(1)中有5个.

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

List<RecipeNode>[] _recipeListByTag;

然后,_recipeListByTag[5]将包含Tags数组中具有5的所有配方的列表.然后,我可以在O(1)中的该标签内选择随机允许的标签和随机配方.

这种方法的缺点是这个多维数组的大小Recipes * Tags(例如,所有配方中的Tags.length的总和),由于我在这里存储了大量的食谱,因此开始占用大量的内存.阵列.当然,既然RecipeNode是一个引用类型,我只重复4byte指向配方的指针,所以这仍然是最好的方法.

是否有更高效的数据结构或算法可以让我找到包含某个允许标签的随机配方？谢谢!

Answer 1

List<RecipeNode>[] _recipeListByTag对你来说可能是最好的方法,它的大小不是 Recipes * Tags因为数组中的每个列表只包含与匹配标记一样多的食谱,而不是更多.Recipes * Tags如果每个食谱包含每个标签,它的大小就会变大.

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