Як швидко порівняти один набір логінів з багатьма іншими наборами булів (порядок)?

У мене виникає проблема з проектом, над яким я працюю у вільний час. Я використовую Google App Engine (версію Java), але це питання не стосується цієї платформи, і я б розглянув інші мови/платформи, якщо вони могли б вирішити цю проблему.

Наступна ілюструє проблему:

Припустимо, у мене є відгалуження з тисячами рецептів та інгредієнти для кожного рецепта. (Заради цієї ілюстрації забудьте про вимірювання.) Я хочу, щоб я міг увійти в список інгредієнтів, які я маю на руках, а потім швидко витягувати всі рецепти, для яких у мене є щонайменше ХХ% інгредієнтів (скажімо, 75%). Я готовий пожертвувати певною точністю та деякими результатами для швидкості, але хочу певну точність. Я можу зробити більш ретельне порівняння, після того як я отримаю "швидкі результати".

Моя спроба рішення: Аналізуючи базу даних рецептів, я складаю список, скажімо, 200 загальних харчових інгредієнтів (яйця, борошно, сіль, цукор, розмарин і т. Д.). Майже всі інгредієнти для рецептів містяться в цьому основному списку:

Common Food Ingredients: [ eggs , flour , salt , sugar , cinnamon ... ]

Потім я проходжу через кожен індивідуальний рецепт і порівнюючи інгредієнти з цим основним списком і закінчуючи набором 200 логінів для кожного рецепта:

Recipe #106: [ T , T , F , T , F ... ]
Recipe #107: [ F , T , T , T , F ... ]

Я б зберігав цю інформацію з рецептами. (До цього моменту це все підготовка даних, яку я маю в усьому світі робити.)

Тепер я ввожу свій список інгредієнтів під руку. Я б зробив те ж саме порівняння з основним списком:

My ingredients on hand: [ F , F , T , T , F ... ]

І ось тут я застряг. Як я можу швидко порівняти цей набір логінів з наборами для рецептів, щоб я міг визначити рецепти, для яких у мене є щонайменше 75% інгредієнтів?

Or (and this would be the holy grail), during the data preparation, instead of storing the set of booleans themselves with each recipe, is there a calculation I can perform that will give me a single value I can later filter off of? (E.g., "SELECT * FROM recipes WHERE master_list_boolean_metric <= 29")

Чи я йду про це неправильним шляхом? (Будь-які вказівки, загальні або конкретні, будуть вдячні.) Що я хочу уникнути, це робити повільне порівняння, інгредієнт за інгредієнтом, між кожним рецептом та моїм списком інгредієнтів "на руку".

Або ... можливо це неможливо зробити швидко?

0

1 Відповіді

використовуйте BitSet .

зберігайте кожен інгредієнт як один біт, виконуйте ІІ разом з інгредієнтами, а потім фільтруйте по потужності ()

1
додано
Труднощі зробити це, я б витягти зі сховища даних BITSET кожного рецепта (з яких у мене є тисячі і більше), а потім в циклі порівнюємо кожен з BitSet інгредієнтів у мене є. Я думаю, що це може бути інтенсивним, залежно від того, скільки рецептів я маю.
додано Автор coffee dude, джерело