Hoe kan een set booleans snel worden vergeleken met vele andere booleansets (orderafhandeling)?

Ik kom een ​​probleem tegen met een project waar ik in mijn vrije tijd aan werk. Ik gebruik Google App Engine (Java-versie), maar deze vraag is niet specifiek voor dat platform en ik zou andere talen/platforms overwegen als ze het probleem zouden kunnen oplossen.

Het volgende illustreert het probleem:

Stel dat ik een datastore heb met duizenden recepten en de ingrediënten voor elk recept. (Vergeet omwille van deze illustratie de metingen niet.) Ik wil een lijst met ingrediënten kunnen invoeren die ik bij de hand heb en dan snel alle recepten ophalen waarvoor ik ten minste XX% van de ingrediënten heb (laten we zeggen 75%). Ik ben bereid om wat nauwkeurigheid en wat resultaten op te offeren voor snelheid, maar wil wel een zekere mate van nauwkeurigheid. Ik kan een grondiger vergelijking maken nadat ik de 'snelle resultaten' heb gekregen.

Mijn poging tot een oplossing: analyse van de database met recepten, ik stel een lijst samen van, zeg, 200 gemeenschappelijke voedselingrediënten (eieren, meel, zout, suiker, rozemarijn, enz.). Bijna alle ingrediënten voor de recepten staan ​​in deze hoofdlijst:

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

Vervolgens doorloop ik elk individueel recept en vergelijk ik de ingrediënten met deze hoofdlijst en eindig ik met een set van 200 booleans voor elk recept:

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

Ik zou deze informatie opslaan bij de recepten. (Tot nu toe gaat het allemaal om gegevensverwerking, waar ik de hele tijd de tijd voor heb.)

Nu kom ik mijn ingrediëntenlijst binnen handbereik. Ik zou dezelfde vergelijking met de hoofdlijst willen maken:

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

En hier zit ik vast. Hoe kan ik deze set booleans snel vergelijken met de sets voor de recepten zodat ik recepten kan identificeren waarvoor ik ten minste 75% van de ingrediënten heb?

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")

Of ga ik hier op de verkeerde manier over? (Elke begeleiding, algemeen of specifiek, zou op prijs worden gesteld.) Wat ik wil voorkomen, is een langzame vergelijking, ingrediënt per ingrediënt, tussen elk recept en mijn lijst van "bij de hand" ingrediënten.

Of ... misschien is het niet mogelijk om dit snel te doen?

0

1 antwoord

gebruik BitSet .

bewaar elk ingrediënt als één bit, doe een AND met de ingrediënten die je hebt en filter vervolgens op cardinaliteit ()

1
toegevoegd
De moeilijkheid om dit te doen is dat ik uit de datastore de BitSet van elk recept (waarvan ik er duizenden en groeiend) zou moeten halen, en dan in een lus elk vergelijkt met de BitSet van ingrediënten die ik heb. Ik denk dat dit prestatie-intensief kan zijn, afhankelijk van hoeveel recepten ik heb.
toegevoegd de auteur coffee dude, de bron