Как выбрать случайный элемент из массива, который соответствует определенным критериям в 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
   }

Найти случайный рецепт из _recipeList в O (1), конечно, было бы легко, однако мне нужно найти случайный рецепт, который имеет, скажем, 5 в Tags в O (1).

Прямо сейчас, моя единственная идея - создать массив List<RecipeNodes> с ключом по тегу. Например:

List<RecipeNode>[] _recipeListByTag;

Тогда _recipeListByTag[5] будет содержать список всех рецептов, которые имеют 5 в массиве Tags. Затем я могу выбрать случайный разрешенный тег и случайный рецепт внутри этого тега в O (1).

Недостатком этого подхода является то, что размер этого многомерного массива будет Recipes * Tags (например, сумма Tags.length по всем рецептам), что начинает занимать много памяти, так как я храню потенциально Огромное количество рецептов в этом массиве. Конечно, поскольку RecipeNode является ссылочным типом, я повторяю только 4-байтовые указатели на рецепты, так что это может быть лучшим способом.

Существует ли более эффективная структура данных или алгоритм, который я мог бы использовать, чтобы позволить мне найти случайный рецепт, который содержит определенный разрешенный тег? Спасибо!

Answer 1

List<RecipeNode>[] _recipeListByTag, вероятно, является лучшим подходом для вас, и его размер равен , а не Recipes * Tags, поскольку каждый список в массиве будет содержать столько же рецептов, сколько соответствует тегу, но не больше.Его размер станет Recipes * Tags, если каждый рецепт будет содержать каждый тег.

Если объем памяти, занимаемый вашими структурами данных, очень дорог для вас, не забудьте вызвать List.TrimExcess () послеВы заполнили каждый список.

Answer 2

Это домашняя работа? Я сомневаюсь, что любая реальная программа рецептов потребует O (1) доступа к тегам и будет слишком медленной для использования базы данных. Я также сомневаюсь, что у любого реального рецепта были бы числовые теги. Понимание реального домена может помочь дать лучший ответ.

Однако, если речь идет о рецептах и ​​числовых тегах, и если у вас есть только 256 тегов, почему бы вам просто не выбрать случайный рецепт 1 миллион раз? Шансы не найти рецепт с обязательным тегом минимальны, а сложность все равно O (1). Если вам не нравятся шансы, выберите случайный рецепт 10 ^ 20 раз. Сложность составляет до сих пор O (1).

UPDATE:

Поскольку вас беспокоит не O (1), а время, затрачиваемое на выбор случайного рецепта, я предлагаю вам позволить вашей базе данных обработать это для вас - той же базе данных, которая в любом случае содержит все рецепты, и та же база данных, к которой вы собираетесь получить доступ, чтобы показать случайный рецепт.

Вы можете SELECT случайную запись в SQL Server следующим образом: Произвольная сортировка SQL Server . Если вы используете другую базу данных, есть и другие способы: http://www.petefreitag.com/item/466.cfm. Просто убедитесь, что в вашем предложении WHERE есть Tag=17.

Answer 3

Если вы хотите сохранить данные в памяти, вы не добьетесь большего успеха, чем список (4 байта) указателей для каждого тега.Если вы можете использовать БД ... ну, другие уже писали об этом.В зависимости от того, насколько «огромен», вы можете просто выделить $$$, чтобы добавить ОЗУ на целевой компьютер.

Если вы хотите сохранить данные в памяти, но хотите быть смехотворно экономными спамяти, вы можете попытаться сжать 4 байта на комбинацию тег-рецепт.Например, храните все рецепты в большом массиве и (при условии, что у вас не будет более миллиона) храните индексы массива по 3 байта каждый.

Чтобы пойти еще дальше, вы можете разделить рецептыс заданным тегом в «сегменты» одинакового размера (каждый из которых занимает непрерывную область большого массива), сохраните начальный индекс для каждого «сегмента» (в 3-4 байта), а затем сохраните список значений дельты между индексамипоследовательных рецептов с заданным тегом.Кодируйте значения дельты, используя массив байтов, таким образом, чтобы одно значение дельты могло использовать что угодно от 1-4 байтов, как требуется.

Поскольку количество рецептов в «корзине» будет ограниченок постоянному числу, поиск с использованием этого подхода по-прежнему равен O (1).

(я занимался встроенным программированием на микросхемах всего с 256 байтами оперативной памяти ... когда вы это делаете, вы начинаете думатькреативные способы сохранения байтов или даже битов. Я уверен, что в вашем приложении переход на такие длины не понадобится, но я подумал, что это интересная идея.)

Answer 4

В этом случае я бы лично выбрал решение SQlite (поскольку я лично знаю, что оно лучше, чем другие). Я вижу, что вас беспокоит пространство, а не производительность с точки зрения скорости, но с точки зрения постоянного времени восстановления вы также беспокоитесь о гибкости доступа к данным. Имо, в этом случае, SQlite это путь.

Создайте свою маленькую БД так, как вам нравится, и выполняйте запросы и объединения так, как вы хотите.

Этот старый, но всегда верный пример того, как вы можете его использовать. Естественно, есть и решение ORM (например, драйвер LINQ), но лично мне это кажется чем-то вроде накладных расходов.

Надеюсь, это поможет.

Answer 5

Я бы сделал экспорт из списка источников в другой со ссылками на все элементы, которые вам подходят. Там делают случайный выбор и берут элемент из списка источников, согласно ссылке. Если есть вероятность, что вы снова сможете использовать тот же производный список, поместите такие списки в больший список. (Конечно, выбранный алгоритм зависит от реальной статистики вашего списка.)

Если вы используете только один параметр, вы можете упорядочить свой список по этому параметру и запомнить в другом списке B его ссылки на места, где начинаются элементы с одинаковым значением параметра. Позже вы можете просто взять случайный интервал (B [4]; b [5] -1). Это сделало бы скорость случайного выбора равной O (const).