What is the order of AND NOT and OR NOT queries?
We can approach this by applying NOT on the second posting list and then applying the AND-OR queries which will have the following order of complexity:
O(NUM_OF_DOCS + len(posting2)) + O(len(posting1) +(NUM_OF_DOCS-len(posting2))) = O(NUM_OF_DOCS)
However we can apply AND NOT differently which will result in a faster program. In order to apply AND NOT faster we can compare first and second posting lists but in order for an item to appear in the final posting list it should appear in first posting list and not on the second which can be done by iterating each list once which will have the fallowing order of complexity:
O(len(posting1) +len(posting2))
Unfortunately we can’t do the same for OR NOT and we will have to iterate the complete list of documents and executing NOT on the second posting list which will result in the following order of complexity:
O(NUM_OF_DOCS + len(posting2)) + O(len(posting1) +(NUM_OF_DOCS-len(posting2))) = O(NUM_OF_DOCS)
I hope it was helpful.
سلام
ممنون
(برای نمایش بهتر متن میتونید متن رو کپی کنید و تو برنامه ای مثل word بخونیدش فقط بعد پیست متن رو انتخاب کنید و از راست به چپش کنید یا از chrome extension Medium right to left support استفاده کنید)
میتونید ابتدا نقیض هر لیست رو پیدا کنید و سپس عملیات مورد نظر رو انجام بدید که مرتبه زمانیش میشه:
O(NUM_OF_DOCS + len(posting2)) + O(len(posting1) +(NUM_OF_DOCS-len(posting2))) = O(NUM_OF_DOCS)
به عبارتی یکبار هزینه یافتن نقیص رو میدید و بعد عملیات مورد نظر رو با لیست جدید اجرا میکنید.
ولی برای یافتن AND NOT روش دیگه هم وجود داره میتونید لیست اول رو با لیست دوم مقایسه کنید با این تفاوت که اگر موردی در لیست اول باشد باید در لیست دوم نباشد. که با یکبار پیمایش هر لیست میتونیم اینکار رو انجام بدیم. پس مرتبه زمانی برابر میشه با:
O(len(posting1) +len(posting2))
برای OR NOT نمیتونیم بدون هزینه پیمایش کل سند ها عملیات رو انجام بدیم پس مرتبه زمانی میشه:
O(NUM_OF_DOCS + len(posting2)) + O(len(posting1) +(NUM_OF_DOCS-len(posting2))) = O(NUM_OF_DOCS)
امیدوارم مفید بوده باشه.
