PDA

View Full Version : سوال: یک الگوریتم برای ذخیره سازی لیست مرتب



lord.t
دوشنبه 27 آبان 1387, 08:50 صبح
با سلام خدمت دوستان

من به دنبال یک الگوریتم برای ذخیره سازی لیست مرتب (لیستی که جایگاه عناصر مهم است) با مشخصات زیر هستم:

1- قابلیت Append, Insert داشته باشد
2- مشخصه ای همچون rank داشته باشد که:
rank[x-1] < rank[x] < rank[x+1]
3- محدود به گرفتن حافظه به صورت استاتیک نباشد

منتظر جواب دوستان هستم
موفق باشید

manager
دوشنبه 27 آبان 1387, 10:07 صبح
میانگین عناصر مورد انتظار در یک لیست، میزان عملیات درج و حذف نسبت به عملیات جستجو، فاکتورهای کارائی و نکات دیگه ای رو اگر بگید ساختمان داده کاراتری می شه انتخاب کرد....

lord.t
دوشنبه 27 آبان 1387, 11:40 صبح
با سلام و تشکر از پاسخ شما

هدف: استفاده از لیست به عنوان Container برای عناصر.
از لیست بیشتر برای ارجاع به عناصر و تشخیص جایگاه (rank) آنها نسبت به یکدیگر (پس و پیش بودن) استفاده میشود.

میانگین میزان عناصر: 25000 (بازه 0 تا 50000)
میزان عملیات درج+حذف به جستجو: تنها جستجوی مد نظر، جستجوی ترتیبی است. تمرکز بیشتر بر روی درج و حذف در زمان مناسب و حافظه مناسب و به هنگام بودن rank است.
البته نرخ خواندن (ارجاع به عناصر و در پاره ای از مواقع جستجوی ترتیبی) خیلی بیشتر از درج+حذف است.

نکته: به عنوان یک راه حل سیستمی استفاده خواهد شد.

پارامترهای کارآیی:
1- مدیریت حافظه مناسب. جلوگیری از پارگی حافظه و همچنین تمهیداتی در مورد استفاده مناسب از کش سیستم در جستجوی ترتیبی.
2- برای عناصر با تعداد کم نیز کارآیی حافظه مناسب داشته باشد.
3- با توجه به وضعیت یک نویسنده و چندین خواننده، مدت زمان تغییر در ساختمان داده برای درج و حذف (منطقه بحرانی) حداقل ممکن باشد.

موفق باشید

lord.t
پنج شنبه 30 آبان 1387, 08:11 صبح
با سلام
به نظر این سوال مصداق این مصرع شده: آن را که خبر شد، خبری باز نیامد

دوستان محترم برنامه نویس نظری ندارند...

نکته دیگه ای که شاید به جواب کمک کنه اینه که این الگوریتم قرار است برای بهبود پروژه متن باز IPtablestng که در آدرس http://sourceforge.net/projects/iptablestng/ قرار دارد استفاده شود.

اولا خیلی خوشحال خواهم شد تا دوستان در یافتن الگوریتم کمک کنند.
دوما خیلی خوشحال خواهم شد که دوستان برنامه نویس در گسترش این پروژه کمک کنند.

موفق باشید

whitehat
پنج شنبه 30 آبان 1387, 10:18 صبح
معمولا برای نگهداری IPtablestng از یک جدول درهم سازی استفاده می شود و لزوما یک جدول مرتب به کارایی شما کمکی نمی کند
در مورد جدولی که نوشتید باید یک Rank داشه باشه ، شاید یک راه حل استفاده از یک درخت Heap باشه که بتونه عناصر شما را در خود ذخیره کند.

lord.t
پنج شنبه 30 آبان 1387, 11:55 صبح
با سلام مجدد

IPtablestng از یک لیست پیوندی برای ذخیره سازی قانونها استفاده میکند و همچنین از Classifierها مانند tuple (که از hash برای ذخیره سازی داده ها استفاده میکند) برای جستجوی قانونها استفاده میکند.

نکته مهم در مورد rank این است که وقتی قانونی مثلا در مکان 2 بخواهد درج شود وضعیتی اینچنین اتفاق می افتد:
وضعیت لیست قبل از درج:
e1 e2 e3 e4 ...
که وضعیت rankها اینگونه خواهد بود:
rank[e1]< rank[e2]< rank[e3]<rank[e4] < ...

حال هنگامیکه عنصر جدید وارد میشود دو عملیات باید انجام شود:
1- انتصاب مقدار rank مناسب به قانون جدید
2- به هنگام سازی قانونهای قبل (ویا شاید هم بعد) از عنصر به گونه ای که رابطه زیر برقرار باشد:
rank[e1] < rank[e2] < rank[new_element] < rank[e3] < ...

بنابراین heep فکر میکنم در مورد درج عناصر مشکل جدی خواهد داشت.
یک راه حل دیگر هم استفاده از درخت جستجوی دودویی است همراه با عضو ایندکس.. اما وقتی عناصر به صورت Append در لیست درج شوند، راه حل با لیست پیوندی تفاوتی نخواهد داشت.
راه حلی که الان استفاده میشود، پیمایش لیست پیوندی و به هنگام کردن رنکها تا رسیدن به مکان درج میباشد. که راه حل کارآیی نیست.

نکته 1: مقدار rank برای تشخیص جایگاه عناصر در لیست است (پس و پیش بودن) بنابراین اگر با روش دیگری غیر از rank هم بشود جایگاه عناصر را تشخیص داد میتوان از rank چشم پوشی کرد.
نکته 2: تشخیص جایگاه نیز برای تشخیص اولویت در اعمال قانونها به بسته های شبکه میباشد

لطفا راهنمایی فرمایید
موفق باشید

lord.t
یک شنبه 03 آذر 1387, 10:00 صبح
با سلام
دوباره فکر میکنم موضوع ما شده قضیه: نیست نگرد، گشتیم نبود

دوستان اگر فارومی رو میشناسند که بتونه به مسائل طراحی الگوریتم به صورت علمی تر پاسخگو باشه معرفی کنند.. (زبان اصلی یا فارسی )

منتظر راهنمایی دوستان هستم
موفق باشید