Booleanların bir setini diğer birçok boole (hızlı sipariş) kümesine hızlı bir şekilde nasıl karşılaştırırsınız?

Boş zamanlarımda üzerinde çalıştığım bir projeyle ilgili bir sorunla karşılaşıyorum. Google App Engine'i (Java sürümü) kullanıyorum, ancak bu soru o platforma özgü değil ve sorunu çözebileceklerse diğer dilleri/platformları düşünürdüm.

Aşağıdaki problemi göstermektedir:

Binlerce reçete ve her reçete için malzemeler içeren bir veri depom var. (Bu örnek için, ölçümleri unutun.) Elimde olan bir malzemenin listesini girebilmek ve daha sonra en az% XX'lik malzemelere sahip olduğum tüm tarifleri hızlıca alabilmek istiyorum. % 75). Bazı doğruluktan ve hız için bazı sonuçlardan fedakarlık yapmaya razıyım, ama kesin bir doğruluk derecesi istiyorum. "Hızlı sonuçlar" elde ettikten sonra daha kapsamlı bir karşılaştırma yapabilirim.

Bir çözüm girişiminde bulunma: Tariflerin veritabanını analiz ederek, 200 ortak gıda maddesinin (yumurta, un, tuz, şeker, biberiye, vb.) Bir listesini derledim. Tarifler için hemen hemen tüm malzemeler bu ana listede yer almaktadır:

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

Daha sonra, her bir reçeteyi incelerim ve malzemeleri bu ana listeye göre karşılaştırır ve her tarif için 200 boolean seti ile sonuçlanır:

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

Bu bilgiyi tariflerle saklarım. (Bu noktaya kadar, dünyanın her yerinde yapmam gereken tüm veri hazırlama işi.)

Şimdi, malzemeler listeme giriyorum. Ana listeyle aynı karşılaştırmayı yapardım:

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

Ve burası sıkıştığım yer. Tarifler için setlere karşı bu boole dizisini hızlı bir şekilde nasıl karşılaştırabilirim, böylece malzemelerin en az% 75'ine sahip olduğum tarifleri tanımlayabilirim?

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

Yoksa yanlış yöne mi gidiyorum? (Genel veya özel herhangi bir rehberlik takdir edilecektir.) Önlemek istediğim, her tarifi ve "eldeki" içerikler listemi arasında yavaş bir karşılaştırma, içerik bileşenini yapıyor.

Ya da ... belki bunu hızlı bir şekilde yapmak mümkün değil mi?

0

1 cevap

BitSet 'i kullanın.

Her bir bileşeni bir bit olarak depolayın, sahip olduğunuz bileşenlerle birlikte bir AND yapın ve ardından kardinalite filtreleyin ()

1
katma
Bunu yapmanın zorluğu, her bir tarifin BitSet'i (ki bunlardan binlerce ve büyüğüm var) veri tabanından almak zorunda kalırdım, o zaman bir döngüde herbiri, sahip olduğum malzemelerin BitSet'iyle karşılaştırırdım. Bu, kaç tane tarif ettiğime bağlı olarak, performans açısından yoğun olabileceğini düşünüyorum.
katma yazar coffee dude, kaynak