وقتی ما در درهم سازی برای حل تصادم از روش زنجیری استفاده میکنیم ، این لیست زنجیری که میسازیم همون لیست پیوندی هست یا فرق داره ؟
یعنی اگر این لیست مرتب بود میشه جستجوی دودویی روش انجام داد. یا برای حذف احتیاج به شیفت دادن عناصر در لیست داریم یا اینکه نیاز به شیفت نیست و فقط با تغییر اشاره گر (شبیه لیست پیوندی) میشه کلید را حذف کرد ؟
(۰۸ بهمن ۱۳۹۲ ۰۴:۳۶ ب.ظ)masoud67 نوشته شده توسط: وقتی ما در درهم سازی برای حل تصادم از روش زنجیری استفاده میکنیم ، این لیست زنجیری که میسازیم همون لیست پیوندی هست یا فرق داره ؟
یعنی اگر این لیست مرتب بود میشه جستجوی دودویی روش انجام داد. یا برای حذف احتیاج به شیفت دادن عناصر در لیست داریم یا اینکه نیاز به شیفت نیست و فقط با تغییر اشاره گر (شبیه لیست پیوندی) میشه کلید را حذف کرد ؟
-بله این لیست یک لیست خطی یک سویه(همان لیست پیوندی) هست.هزینه جستجو در بدترین حالت (O(n است و در حالت میانگین (O(1.
-اتفاقا این یه مسئله است که پیشنهاد شده جهت بهبود کارایی از جمله برای جستجو و حذف. چون وقتی لیست پیوندی مرتب باشه هزینه جستجو به طور چشم گیری کاهش پیدا می کنه.
(۰۸ بهمن ۱۳۹۲ ۰۵:۴۱ ب.ظ)fulgent نوشته شده توسط: -بله این لیست یک لیست خطی یک سویه(همان لیست پیوندی) هست.هزینه جستجو در بدترین حالت (O(n است و در حالت میانگین (O(1.لیست پیوندی مرتب چه جوری زمان جستجو را کاهش میده ؟ با لیست پیوندی معمولی اصلا جستجوی دودویی نداریم مگه اینکه از skip list استفاده کنیم که زمان جستجو را logn کنه
-اتفاقا این یه مسئله است که پیشنهاد شده جهت بهبود کارایی از جمله برای جستجو و حذف. چون وقتی لیست پیوندی مرتب باشه هزینه جستجو به طور چشم گیری کاهش پیدا می کنه.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
که اینم تو این قسمت استفاده نمیشه
(۰۸ بهمن ۱۳۹۲ ۰۵:۴۹ ب.ظ)masoud67 نوشته شده توسط:(08 بهمن ۱۳۹۲ ۰۵:۴۱ ب.ظ)fulgent نوشته شده توسط: -بله این لیست یک لیست خطی یک سویه(همان لیست پیوندی) هست.هزینه جستجو در بدترین حالت (O(n است و در حالت میانگین (O(1.لیست پیوندی مرتب چه جوری زمان جستجو را کاهش میده ؟ با لیست پیوندی معمولی اصلا جستجوی دودویی نداریم مگه اینکه از skip list استفاده کنیم که زمان جستجو را logn کنه
-اتفاقا این یه مسئله است که پیشنهاد شده جهت بهبود کارایی از جمله برای جستجو و حذف. چون وقتی لیست پیوندی مرتب باشه هزینه جستجو به طور چشم گیری کاهش پیدا می کنه.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
که اینم تو این قسمت استفاده نمیشه
خب شما از دیتای هر نود اطلاع داری پس با لیست مرتب زمان جستجو کاهش پیدا می کنه. اینکه چجوری منظورتون چیه؟
خب بله با لیست معمولی جستجوی دودویی نداریم...
الان مشکل کجاست؟
(۰۸ بهمن ۱۳۹۲ ۰۵:۵۵ ب.ظ)fulgent نوشته شده توسط: خب شما از دیتای هر نود اطلاع داری پس با لیست مرتب زمان جستجو کاهش پیدا می کنه. اینکه چجوری منظورتون چیه؟مشکل من اینه که ما اگر مقدار نود را هم بدونیم آخرش نیاز به جلو رفتن ترتیبی در لیست داریم . حس میکنم با دونستن مقدار نود آخرش ما نمیدونیم نود ما کجای لیست قرار داره.
الان مشکل کجاست؟
یه کم مبهمه این موضوع.
(۰۸ بهمن ۱۳۹۲ ۰۶:۰۱ ب.ظ)masoud67 نوشته شده توسط:(08 بهمن ۱۳۹۲ ۰۵:۵۵ ب.ظ)fulgent نوشته شده توسط: خب شما از دیتای هر نود اطلاع داری پس با لیست مرتب زمان جستجو کاهش پیدا می کنه. اینکه چجوری منظورتون چیه؟مشکل من اینه که ما اگر مقدار نود را هم بدونیم آخرش نیاز به جلو رفتن ترتیبی در لیست داریم . حس میکنم با دونستن مقدار نود آخرش ما نمیدونیم نود ما کجای لیست قرار داره.
الان مشکل کجاست؟
یه کم مبهمه این موضوع.
پس تابع Hash این وسط چیکاره است؟
گفتیم که اگه لیست پیوندی عادی باشه در بدترین حالت باید کل لیست پیوندی رو جستجو کنیم و به قول شما نیاز به جلو رفتن ترتیبی هست.
اما در مورد اینکه لیست پیوندی مرتب باشه در کتاب دکتر قدسی به عنوان یه سوال مطرح شده که از نظر پروفسور مارلی اگر مرتب باشه تاثیر زیادی بر کارایی داره و اینکه بر جستجو و درج و حذف چه تاثیری داره بر عهده دانشجو گذاشته شده...
اما به نظر من با مرتب کردن لیست و البته تغییراتی در نگاشت ها و تابع درهم ساز می شه هزینه جستجو در بدترین حالت رو کاهش داد اما هزینه update کردن لیست این مزیت رو کم رنگ میکنه و یه جور trade off اتفاق می افته!
(۰۸ بهمن ۱۳۹۲ ۰۶:۱۰ ب.ظ)fulgent نوشته شده توسط:تابع هش که فقط هش میکنه. اونکه مربوط به جدول هش میشه و ذخیره کلید ها. ولی من تو یه لیست پیوندی که حاصل تصادم یه سری کلید هست را بحث کردم .(08 بهمن ۱۳۹۲ ۰۶:۰۱ ب.ظ)masoud67 نوشته شده توسط:(08 بهمن ۱۳۹۲ ۰۵:۵۵ ب.ظ)fulgent نوشته شده توسط: خب شما از دیتای هر نود اطلاع داری پس با لیست مرتب زمان جستجو کاهش پیدا می کنه. اینکه چجوری منظورتون چیه؟مشکل من اینه که ما اگر مقدار نود را هم بدونیم آخرش نیاز به جلو رفتن ترتیبی در لیست داریم . حس میکنم با دونستن مقدار نود آخرش ما نمیدونیم نود ما کجای لیست قرار داره.
الان مشکل کجاست؟
یه کم مبهمه این موضوع.
پس تابع Hash این وسط چیکاره است؟
گفتیم که اگه لیست پیوندی عادی باشه در بدترین حالت باید کل لیست پیوندی رو جستجو کنیم و به قول شما نیاز به جلو رفتن ترتیبی هست.
اما در مورد اینکه لیست پیوندی مرتب باشه در کتاب دکتر قدسی به عنوان یه سوال مطرح شده که از نظر پروفسور مارلی اگر مرتب باشه تاثیر زیادی بر کارایی داره و اینکه بر جستجو و درج و حذف چه تاثیری داره بر عهده دانشجو گذاشته شده...
اما به نظر من با مرتب کردن لیست و البته تغییراتی در نگاشت ها و تابع درهم ساز می شه هزینه جستجو در بدترین حالت رو کاهش داد اما هزینه update کردن لیست این مزیت رو کم رنگ میکنه و یه جور trade off اتفاق می افته!
آخه تو آزمون مدرسان گفته تو لیست مرتب، جستجو دودویی میزنیم که عجیب بود واسم.
فکر کنم باید یه سری به مراجع علمی بزنم تا موضوع برام بهتر جا بیافته
تشکر
(۰۸ بهمن ۱۳۹۲ ۰۶:۱۷ ب.ظ)masoud67 نوشته شده توسط:(08 بهمن ۱۳۹۲ ۰۶:۱۰ ب.ظ)fulgent نوشته شده توسط:تابع هش که فقط هش میکنه. اونکه مربوط به جدول هش میشه و ذخیره کلید ها. ولی من تو یه لیست پیوندی که حاصل تصادم یه سری کلید هست را بحث کردم .(08 بهمن ۱۳۹۲ ۰۶:۰۱ ب.ظ)masoud67 نوشته شده توسط:(08 بهمن ۱۳۹۲ ۰۵:۵۵ ب.ظ)fulgent نوشته شده توسط: خب شما از دیتای هر نود اطلاع داری پس با لیست مرتب زمان جستجو کاهش پیدا می کنه. اینکه چجوری منظورتون چیه؟مشکل من اینه که ما اگر مقدار نود را هم بدونیم آخرش نیاز به جلو رفتن ترتیبی در لیست داریم . حس میکنم با دونستن مقدار نود آخرش ما نمیدونیم نود ما کجای لیست قرار داره.
الان مشکل کجاست؟
یه کم مبهمه این موضوع.
پس تابع Hash این وسط چیکاره است؟
گفتیم که اگه لیست پیوندی عادی باشه در بدترین حالت باید کل لیست پیوندی رو جستجو کنیم و به قول شما نیاز به جلو رفتن ترتیبی هست.
اما در مورد اینکه لیست پیوندی مرتب باشه در کتاب دکتر قدسی به عنوان یه سوال مطرح شده که از نظر پروفسور مارلی اگر مرتب باشه تاثیر زیادی بر کارایی داره و اینکه بر جستجو و درج و حذف چه تاثیری داره بر عهده دانشجو گذاشته شده...
اما به نظر من با مرتب کردن لیست و البته تغییراتی در نگاشت ها و تابع درهم ساز می شه هزینه جستجو در بدترین حالت رو کاهش داد اما هزینه update کردن لیست این مزیت رو کم رنگ میکنه و یه جور trade off اتفاق می افته!
آخه تو آزمون مدرسان گفته تو لیست مرتب، جستجو دودویی میزنیم که عجیب بود واسم.
فکر کنم باید یه سری به مراجع علمی بزنم تا موضوع برام بهتر جا بیافته
تشکر
اینکه اسم تابع hash رو اوردم واسه فقط حالت تصادم منظورم نبود.اهان اون سوال رو می گید؟ در اون سوال داده های لیست پیوندی رو به صورت یک ارایه مرتب در نظر گرفته و از جستجوی دودویی استفاده کرده....به نظر من اینکار غیر ممکن نیست!
خواهش می کنم...
امیدوارم جواب رو پیدا کنید.
(۰۸ بهمن ۱۳۹۲ ۰۶:۱۷ ب.ظ)masoud67 نوشته شده توسط: آخه تو آزمون مدرسان گفته تو لیست مرتب، جستجو دودویی میزنیم که عجیب بود واسم.
فکر کنم باید یه سری به مراجع علمی بزنم تا موضوع برام بهتر جا بیافته
نتیجه گرفتید ؟
میشه در لیست مرتب جستجوی دودویی انجام داد ؟
(۱۰ بهمن ۱۳۹۲ ۱۲:۱۷ ب.ظ)tayebe68 نوشته شده توسط:من یه جستجویی تو اینترنت کردم جایی نگفته بودن که تو لیست پیوندی معمولی بشه جستجوی دودویی انجام داد(08 بهمن ۱۳۹۲ ۰۶:۱۷ ب.ظ)masoud67 نوشته شده توسط: آخه تو آزمون مدرسان گفته تو لیست مرتب، جستجو دودویی میزنیم که عجیب بود واسم.
فکر کنم باید یه سری به مراجع علمی بزنم تا موضوع برام بهتر جا بیافته
نتیجه گرفتید ؟
میشه در لیست مرتب جستجوی دودویی انجام داد ؟
ولی حالتهایی مثل skip list یا با تغییر دادن ساختار لیست پیوندی میشه که بعید میدونم نظر مدرسان این باشه چون توی جدول درهم سازی از این لیستهای عجیب و غریب استفاده نمیشه .
حالا منظورشون چی بوده نمیدونم
(۱۰ بهمن ۱۳۹۲ ۰۲:۱۸ ب.ظ)masoud67 نوشته شده توسط: من یه جستجویی تو اینترنت کردم جایی نگفته بودن که تو لیست پیوندی معمولی بشه جستجوی دودویی انجام داد
ولی حالتهایی مثل skip list یا با تغییر دادن ساختار لیست پیوندی میشه که بعید میدونم نظر مدرسان این باشه چون توی جدول درهم سازی از این لیستهای عجیب و غریب استفاده نمیشه .
حالا منظورشون چی بوده نمیدونم
شاید اصلا منظوری نداشتن !
اشتباهات طراحی سوال و پاسخ های تشریحی در موسسات و کنکور کم نیست ...