فهرست خودسازمان دهنده یا لیست خودسازمان دهنده ( به انگلیسی: self - organizing list ) فهرستی است که ترتیب عناصر خود را مطابق با جستجوهای صورت گرفته برای پیدا کردن عناصر تغییر می دهد تا زمان دسترسی میانگین برای هر عنصر را بهبود بخشد. هدف فهرست خودسازمان دهنده افزایش سرعت جستجوی خطی است؛ به این صورت که عناصری را که احتمال دسترسی به آن ها بیشتر است ( یعنی تعداد دفعات درخواست شده برای دستیابی به آن ها نسبت به بقیهٔ عناصر بیشتر است ) را در ابتدای فهرست قرار می دهد.
ریشهٔ مفهوم «فهرست خودسازمان دهنده» یا «لیست خودسازمان دهنده» به سازمان دهی پرونده های ذخیره شده در نوارها و دیسک ها برمی گردد. استراتژی انتقال رو به جلو، که هر عنصر پس از آن که جستجو می شود در ابتدای فهرست قرار می گیرد، برای نخستین بار در سال ۱۹۶۵ و توسط شخصی به نام McCabe مطرح شد. [ ۱] او زمان متوسط مورد نیاز برای جستجو، در فهرستی با آرایش تصادفی عناصر را بررسی کرد تا به حالتی بهینه برای ترتیب عناصر دست یابد. ترتیب بهینه در این فهرست در حالتی روی می داد که عناصر هریک بر اساس احتمال دسترسی خود مرتب شوند به صورتی که عنصری با بیشترین میزان دسترسی در سر فهرست قرار بگیرد. ترتیب بهینه ترتیبی از پیش تعیین شده نبود و در طول زمان می توانست تغییر کند. پس از آن McCabe استراتژی جابه جایی را ارائه داد که در آن هر عنصر در هنگام جستجو به جای انتقال به سر فهرست با عنصر ماقبلش در فهرست جابه جا می شود، او حدس زد که محدودهٔ زمان جستجوی میانگین در استراتژی جابه جایی، با فرض استقلال جستجوها، از همین زمان در استراتژی انتقال رو به جلو بیشتر نمی شود. این حدس او بعدها توسط شخصی به نام Rivest اثبات گردید. [ ۲] علاوه بر موارد فوق McCabe توانست نشان دهد که هر دو روش انتقال رو به جلو و نیز جابه جایی در نهایت به ترتیب بهینه منجر می شوند. با دستیابی به پیشرفت های بیشتر، الگوریتم های دیگری توسط محققانی همچون ریوِست، تِنِنباوم، نیمز، کنوت، بنتلی، و McGeoch ارائه شد.
یکی از ساده ترین روش های پیاده سازی فهرست خودسازمان دهنده، استفاده از لیست پیوندی است. از این رو اگرچه این پیاده سازی برای درج یک عنصر به صورت تصادفی و از لحاظ تخصیص حافظه کارآمد است، دسترسی تصادفی به یک عنصر را به سادگی ممکن نمی سازد. یک فهرست خودسازمان دهنده این ناکارآمدی را با بازآرایی عناصر برپایهٔ تعداد دسترسی ها کاهش می دهد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفریشهٔ مفهوم «فهرست خودسازمان دهنده» یا «لیست خودسازمان دهنده» به سازمان دهی پرونده های ذخیره شده در نوارها و دیسک ها برمی گردد. استراتژی انتقال رو به جلو، که هر عنصر پس از آن که جستجو می شود در ابتدای فهرست قرار می گیرد، برای نخستین بار در سال ۱۹۶۵ و توسط شخصی به نام McCabe مطرح شد. [ ۱] او زمان متوسط مورد نیاز برای جستجو، در فهرستی با آرایش تصادفی عناصر را بررسی کرد تا به حالتی بهینه برای ترتیب عناصر دست یابد. ترتیب بهینه در این فهرست در حالتی روی می داد که عناصر هریک بر اساس احتمال دسترسی خود مرتب شوند به صورتی که عنصری با بیشترین میزان دسترسی در سر فهرست قرار بگیرد. ترتیب بهینه ترتیبی از پیش تعیین شده نبود و در طول زمان می توانست تغییر کند. پس از آن McCabe استراتژی جابه جایی را ارائه داد که در آن هر عنصر در هنگام جستجو به جای انتقال به سر فهرست با عنصر ماقبلش در فهرست جابه جا می شود، او حدس زد که محدودهٔ زمان جستجوی میانگین در استراتژی جابه جایی، با فرض استقلال جستجوها، از همین زمان در استراتژی انتقال رو به جلو بیشتر نمی شود. این حدس او بعدها توسط شخصی به نام Rivest اثبات گردید. [ ۲] علاوه بر موارد فوق McCabe توانست نشان دهد که هر دو روش انتقال رو به جلو و نیز جابه جایی در نهایت به ترتیب بهینه منجر می شوند. با دستیابی به پیشرفت های بیشتر، الگوریتم های دیگری توسط محققانی همچون ریوِست، تِنِنباوم، نیمز، کنوت، بنتلی، و McGeoch ارائه شد.
یکی از ساده ترین روش های پیاده سازی فهرست خودسازمان دهنده، استفاده از لیست پیوندی است. از این رو اگرچه این پیاده سازی برای درج یک عنصر به صورت تصادفی و از لحاظ تخصیص حافظه کارآمد است، دسترسی تصادفی به یک عنصر را به سادگی ممکن نمی سازد. یک فهرست خودسازمان دهنده این ناکارآمدی را با بازآرایی عناصر برپایهٔ تعداد دسترسی ها کاهش می دهد.
