Dynamic array
کمپیوٹر سائنس میں، ایک متحرک صف، قابل نمو صف، قابل تجدید صف، متحرک ٹیبل، متغیر صف، یا صف کی فہرست ایک بے ترتیب رسائی، متغیر سائز کی فہرست ڈیٹا ڈھانچہ ہے جو عناصر کو شامل کرنے یا ہٹانے کی اجازت دیتا ہے۔ اسے بہت سی جدید مرکزی دھارے کی پروگرامنگ زبانوں میں معیاری لائبریریوں کے ساتھ فراہم کیا جاتا ہے۔ متحرک صفیں جامد صفوں کی ایک حد پر قابو پا لیتی ہیں، جن کی ایک مقررہ صلاحیت ہوتی ہے جسے مختص کرنے پر متعین کرنے کی ضرورت ہوتی ہے۔ ایک متحرک صف متحرک طور پر مختص کردہ صف یا متغیر لمبائی کی صف جیسی چیز نہیں ہے، جن میں سے کوئی بھی ایک صف ہے جس کا سائز صف مختص ہونے پر طے ہوتا ہے، حالانکہ ایک متحرک صف اس طرح کے فکسڈ سائز کی صف کو بیک اینڈ کے طور پر استعمال کر سکتی ہے۔ باؤنڈ سائز متحرک صفوں اور صلاحیت ایک سادہ متحرک صف کو مقررہ سائز کی صف مختص کرکے بنایا جا سکتا ہے، جو عام طور پر فوری طور پر درکار عناصر کی تعداد سے بڑا ہوتا ہے۔ متحرک صف کے عناصر کو بنیادی صف کے آغاز میں مل کر محفوظ کیا جاتا ہے، اور بنیادی صف کے اختتام کی طرف باقی پوزیشنیں محفوظ، یا غیر استعمال شدہ ہوتی ہیں۔ عناصر کو متحرک صف کے آخر میں مستقل وقت میں مخصوص جگہ کا استعمال کرتے ہوئے شامل کیا جا سکتا ہے، جب تک کہ یہ جگہ مکمل طور پر استعمال نہ ہو جائے۔ جب تمام جگہ استعمال ہو جاتی ہے، اور ایک اضافی عنصر شامل کرنا ہوتا ہے، تو بنیادی فکسڈ سائز کی صف کو سائز میں بڑھانے کی ضرورت ہوتی ہے۔ عام طور پر سائز تبدیل کرنا مہنگا ہوتا ہے کیونکہ اس میں ایک نئی بنیادی صف مختص کرنا اور ہر عنصر کو اصل صف سے نقل کرنا شامل ہوتا ہے۔ عناصر کو متحرک صف کے آخر سے مستقل وقت میں ہٹایا جا سکتا ہے، کیونکہ کسی سائز تبدیل کرنے کی ضرورت نہیں ہے۔ متحرک صف کے مندرجات کے ذریعہ استعمال ہونے والے عناصر کی تعداد اس کا منطقی سائز یا سائز ہے، جبکہ بنیادی صف کے سائز کو متحرک صف کی صلاحیت یا جسمانی سائز کہا جاتا ہے، جو ڈیٹا کو منتقل کیے بغیر زیادہ سے زیادہ ممکنہ سائز ہے۔ ایک فکسڈ سائز کی صف ان ایپلی کیشنز میں کافی ہوگی جہاں زیادہ سے زیادہ منطقی سائز طے کیا جاتا ہے (جیسے۔ تفصیلات کے مطابق)، یا صف مختص ہونے سے پہلے حساب لگایا جا سکتا ہے۔ ایک متحرک صف کو ترجیح دی جا سکتی ہے اگر: زیادہ سے زیادہ منطقی سائز نامعلوم ہے، یا حساب لگانا مشکل ہے، اس سے پہلے کہ صف مختص کی جائے، یہ سمجھا جاتا ہے کہ ایک تفصیلات کے ذریعہ دیا گیا زیادہ سے زیادہ منطقی سائز ممکنہ طور پر ایک متحرک صف کو دوبارہ سائز دینے کی تخفیف شدہ لاگت کو تبدیل کر سکتا ہے کارکردگی یا ردعمل کو نمایاں طور پر متاثر نہیں کرتا ہے۔ ہندسی توسیع اور تخفیف شدہ لاگت کئی بار سائز تبدیل کرنے کی لاگت سے بچنے کے لیے، متحرک صفوں کا سائز بڑی مقدار میں تبدیل کریں، جیسے کہ سائز میں دوگنا ہونا، اور مستقبل کی توسیع کے لیے مخصوص جگہ کا استعمال کریں۔ آخر میں کسی عنصر کو شامل کرنے کا عمل مندرجہ ذیل کام کر سکتا ہے: فنکشن انسٹر اینڈ (ڈائناری a، عنصر e) اگر (a.size = = a.capacity)// a کا سائز اس کی موجودہ صلاحیت سے دوگنا کر دیں: a.capacity a.capacity * 2/(مواد کو یہاں میموری کے نئے مقام پر کاپی کریں) a [a.size] <e a.size a.size + 1 جیسے ہی n عناصر داخل کیے جاتے ہیں، صلاحیتیں ہندسی ترقی کی تشکیل کرتی ہیں۔ صف کو کسی بھی مستقل تناسب a سے بڑھانا اس بات کو یقینی بناتا ہے کہ n عناصر کو داخل کرنے میں مجموعی طور پر O (n) وقت لگتا ہے، جس کا مطلب ہے کہ ہر اندراج میں مستقل وقت لگتا ہے۔ بہت سی متحرک صفوں میں کچھ بنیادی اسٹوریج کو بھی خارج کر دیا جاتا ہے اگر اس کا سائز کسی خاص حد سے نیچے چلا جاتا ہے، جیسے کہ صلاحیت کا 30 فیصد۔ یہ حد ہسٹیریسیس فراہم کرنے کے لیے 1/اے سے سختی سے چھوٹی ہونی چاہیے (بار بار بڑھنے اور سکڑنے سے بچنے کے لیے ایک مستحکم بینڈ فراہم کریں) اور ادائیگی شدہ مستقل لاگت کے ساتھ اندراج اور ہٹانے کے مخلوط ترتیبات کی حمایت کریں۔ متحرک صف ایک عام مثال ہوتی ہے جب تخفیف شدہ تجزیہ سکھایا جاتا ہے۔ گروتھ فیکٹر متحرک صف کے لیے گروتھ فیکٹر کا انحصار کئی عوامل پر ہوتا ہے جن میں اسپیس ٹائم ٹریڈ آف اور خود میموری الاکیٹر میں استعمال ہونے والے الگورتھم شامل ہیں۔ گروتھ فیکٹر a کے لیے، فی اندراج آپریشن کا اوسط وقت ہے۔ اگر میموری الاکیٹر فرسٹ فٹ الاٹمنٹ الگورتھم کا استعمال کرتا ہے، تو گروتھ فیکٹر ویلیوز جیسے a = 2 متحرک صف کی توسیع کو میموری سے باہر کرنے کا سبب بن سکتے ہیں حالانکہ میموری کی ایک قابل ذکر مقدار اب بھی دستیاب ہو سکتی ہے۔ مثالی ترقی کے عوامل کی اقدار پر مختلف مباحثے ہوئے ہیں، جن میں سنہری تناسب کے ساتھ ساتھ قیمت 1.5 کی تجاویز بھی شامل ہیں۔ تاہم، بہت سی نصابی کتابیں سادگی اور تجزیہ کے مقاصد کے لیے a = 2 کا استعمال کرتی ہیں۔ ذیل میں کئی مقبول نفاذات کے ذریعہ استعمال ہونے والے ترقی کے عوامل ہیں: کارکردگی متحرک صف میں ایک صف کی طرح کارکردگی ہوتی ہے، عناصر کو شامل کرنے اور ہٹانے کے لیے نئے آپریشنز کے اضافے کے ساتھ: کسی خاص اشاریہ (مستقل وقت) پر قدر حاصل کرنا یا ترتیب دینا ترتیب میں عناصر پر تکرار کرنا (لکیری وقت، اچھی کیش کارکردگی) صف کے وسط میں کسی عنصر کو داخل کرنا یا حذف کرنا (لکیری وقت) صف کے آخر میں کسی عنصر کو داخل کرنا یا حذف کرنا (مستقل امورٹائزڈ وقت) متحرک صفوں کو صفوں کے بہت سے فوائد سے فائدہ ہوتا ہے، بشمول حوالہ کی اچھی جگہ اور ڈیٹا کیش کا استعمال، کمپیکٹنس (کم میموری استعمال)، اور بے ترتیب رسائی۔ ان کے پاس عام طور پر سائز اور صلاحیت کے بارے میں معلومات کو ذخیرہ کرنے کے لیے صرف ایک چھوٹا سا مقررہ اضافی اوور ہیڈ ہوتا ہے۔ یہ متحرک صفوں کو کیش دوستانہ ڈیٹا ڈھانچے کی تعمیر کے لیے ایک پرکشش ٹول بناتا ہے۔ تاہم، ازگر یا جاوا جیسی زبانوں میں جو حوالہ سیمنٹکس کو نافذ کرتی ہیں، متحرک صف عام طور پر اصل ڈیٹا کو محفوظ نہیں کرے گی، بلکہ یہ میموری کے دوسرے علاقوں میں رہنے والے ڈیٹا کے حوالہ جات کو محفوظ کرے گی۔ اس صورت میں، ترتیب وار صف میں آئٹمز تک رسائی میں دراصل میموری کے متعدد غیر متصل علاقوں تک رسائی شامل ہوگی، لہذا اس ڈیٹا ڈھانچے کی کیش دوستی کے بہت سے فوائد ختم ہو جاتے ہیں۔ منسلک فہرستوں کے مقابلے میں، متحرک صفوں میں تیز انڈیکسنگ (مستقل وقت بمقابلہ لکیری وقت) ہوتی ہے اور حوالہ کے بہتر مقام کی وجہ سے عام طور پر تیز تکرار ہوتی ہے۔ تاہم، متحرک صفوں کو صوابدیدی مقام پر داخل کرنے یا حذف کرنے کے لیے لکیری وقت کی ضرورت ہوتی ہے، کیونکہ مندرجہ ذیل تمام عناصر کو منتقل کرنا ضروری ہے، جبکہ منسلک فہرستیں مستقل وقت میں ایسا کر سکتی ہیں۔ اس نقصان کو ذیل میں متغیرات کے تحت زیر بحث گیپ بفر اور ٹائرڈ ویکٹر متغیرات سے کم کیا جاتا ہے۔ نیز، انتہائی بکھرے ہوئے میموری کے علاقے میں، ایک بڑی متحرک صف کے لیے ملحقہ جگہ تلاش کرنا مہنگا یا ناممکن ہو سکتا ہے، جبکہ منسلک فہرستوں میں پورے ڈیٹا ڈھانچے کو ملحقہ طور پر ذخیرہ کرنے کی ضرورت نہیں ہوتی ہے۔ ایک متوازن درخت متحرک صفوں اور منسلک فہرستوں دونوں کی تمام کارروائیوں کو معقول طور پر مؤثر طریقے سے فراہم کرتے ہوئے ایک فہرست کو ذخیرہ کر سکتا ہے، لیکن فہرست کے آخر میں اندراج اور فہرست پر تکرار دونوں ہی متحرک صف کے مقابلے میں سست ہوتے ہیں، نظریہ اور عملی طور پر، غیر متصل اسٹوریج اور ٹری ٹریورسل/ہیرا پھیری اوور ہیڈ کی وجہ سے۔ متغیر گیپ بفر متحرک صفوں سے ملتے جلتے ہیں لیکن ایک ہی صوابدیدی مقام کے قریب کلسٹر شدہ موثر اندراج اور حذف کرنے کی کارروائیوں کی اجازت دیتے ہیں۔ کچھ ڈیوک نفاذ صف ڈیوک کا استعمال کرتے ہیں، جو صرف ایک سرے کے بجائے دونوں سروں پر مستقل وقت داخل کرنے/ہٹانے کی اجازت دیتے ہیں۔ گڈریچ نے ایک متحرک صف الگورتھم پیش کیا جسے ٹائرڈ ویکٹر کہا جاتا ہے جو صف میں کہیں سے بھی اندراج اور حذف کرنے کے لیے O (n1/k) کارکردگی فراہم کرتا ہے، اور O (k) حاصل اور سیٹ کرتا ہے، جہاں k ± 2 ایک مستقل پیرامیٹر ہے۔ ہیشڈ ایرے ٹری (ایچ اے ٹی) ایک متحرک ایرے الگورتھم ہے جسے سیتارسکی نے 1996 میں شائع کیا تھا۔ ہیشڈ ایرے ٹری فضلہ اسٹوریج کی جگہ کی n1/2 مقدار کا آرڈر دیتا ہے، جہاں n صف میں عناصر کی تعداد ہے۔ ہیشڈ ایرے ٹری کے آخر میں اشیاء کی ایک سیریز کو شامل کرتے وقت الگورتھم میں O (1) امورٹائزڈ کارکردگی ہوتی ہے۔ 1999 کے ایک مقالے میں، بروڈنک اور دیگر۔ ایک ٹائرڈ ڈائنامک ایرے ڈیٹا اسٹرکچر کی وضاحت کریں، جو کسی بھی وقت n عناصر کے لیے صرف n1/2 جگہ ضائع کرتا ہے، اور وہ ایک نچلی حد ثابت کرتے ہیں جس سے یہ ظاہر ہوتا ہے کہ کسی بھی ڈائنامک ایرے کو اتنی جگہ ضائع کرنی ہوگی اگر آپریشنز کو مستقل وقت پر برقرار رکھنا ہے۔ مزید برآں، وہ ایک قسم پیش کرتے ہیں جہاں بفر کو بڑھانا اور سکڑنا نہ صرف ادائیگی کرتا ہے بلکہ بدترین صورت میں مستقل وقت ہوتا ہے۔ بیگ ویل (2002) نے وی لسٹ الگورتھم پیش کیا، جسے متحرک صف کو نافذ کرنے کے لیے ڈھالا جا سکتا ہے۔ نائیو ریزائز ایبل صفوں-جسے ریزائز ایبل صفوں کا "بدترین نفاذ" بھی کہا جاتا ہے-صف کے مختص کردہ سائز کو اس میں موجود تمام ڈیٹا کے لیے بالکل بڑا رکھیں، شاید صف میں شامل ہر آئٹم کے لیے ریاللوک کال کرکے۔ نائیو ریزائز ایبل صفوں کو سی میں ریزائز ایبل صف کو لاگو کرنے کا سب سے آسان طریقہ ہے۔ وہ کسی بھی میموری کو ضائع نہیں کرتے ہیں، لیکن صف کے آخر تک جوڑنے میں ہمیشہ θ (n) وقت لگتا ہے۔ لکیری طور پر بڑھتی ہوئی صفوں کو پہلے سے مختص کریں ("فضلہ") (1) جگہ ہر بار جب وہ صف کو دوبارہ سائز دیتے ہیں، تو انہیں سادہ قابل تجدید صفوں سے کئی گنا تیز بناتا ہے-صف کے آخر میں شامل کرنے میں اب بھی وقت لگتا ہے لیکن بہت چھوٹے مستقل کے ساتھ۔ جب جگہ سے محدود ایپلی کیشن کو بہت سی چھوٹی قابل تجدید صفوں کی ضرورت ہوتی ہے تو سادہ قابل تجدید صف اور لکیری طور پر بڑھتی ہوئی صف مفید ثابت ہوسکتی ہیں۔ انہیں عام طور پر ایک تعلیمی مثال کے طور پر بھی استعمال کیا جاتا ہے جس کی وجہ سے متحرک صفوں میں تیزی سے اضافہ ہوتا ہے۔ زبان کی حمایت سی + + کے ایس ٹی ڈی:: ویکٹر اور رسٹ کے ایس ٹی ڈی:: وی سی:: وی ای سی متحرک صفوں کے نفاذ ہیں، جیسا کہ جاوا اے پی آئی اور. NET فریم ورک کے ساتھ فراہم کردہ ارے لسٹ کلاسز ہیں۔ . NET فریم ورک کے ورژن 2 کے ساتھ فراہم کردہ عام فہرست کلاس کو متحرک صفوں کے ساتھ بھی لاگو کیا جاتا ہے۔ سمال ٹاک کا آرڈرڈ کلیکشن متحرک اسٹارٹ اور اینڈ انڈیکس کے ساتھ ایک متحرک صف ہے، جس سے پہلے عنصر کو بھی O (1) سے ہٹا دیا جاتا ہے۔ ازگر کی فہرست ڈیٹا ٹائپ کا نفاذ ایک متحرک صف ہے جس کا ترقی کا نمونہ ہے: 0، 4، 8، 16، 24، 32، 40، 52، 64، 76،۔ ڈیلفی اور ڈی زبان کے مرکز میں متحرک صفوں کو نافذ کرتے ہیں۔ اڈا کا Ada.Containers.Vectors عام پیکیج دی گئی ذیلی قسم کے لیے متحرک صف کا نفاذ فراہم کرتا ہے۔ بہت سی اسکرپٹنگ زبانیں جیسے پرل اور روبی متحرک صفوں کو بلٹ ان ابتدائی ڈیٹا ٹائپ کے طور پر پیش کرتی ہیں۔ کئی کراس پلیٹ فارم فریم ورک سی کے لیے متحرک صف کے نفاذ فراہم کرتے ہیں، بشمول کور فاؤنڈیشن میں سی ایف اے آرے اور سی ایف ایم ایبل آرے، اور جی ایل آئی بی میں جی آرے اور جی پی ٹی آر آرے۔ کامن لیسپ بلٹ ان ایرے کی قسم کو سایڈست اور فل پوائنٹر کے ذریعے اندراج کے مقام کے طور پر ترتیب دینے کی اجازت دے کر ریزائزبل ویکٹرز کے لیے ایک ابتدائی مدد فراہم کرتا ہے۔ حوالہ جات بیرونی روابط NIST ڈکشنری آف الگورتھم اینڈ ڈیٹا اسٹرکچرز: متحرک صف VPOOL-C زبان متحرک صف کا نفاذ۔ کلیکشن اسپائی-ایک جاوا پروفائلر جس میں ارے لسٹ اور ویکٹر سے متعلق مسائل کو ڈیبگ کرنے کے لیے واضح سپورٹ ہے۔ اوپن ڈیٹا اسٹرکچرز-باب 2-صف پر مبنی فہرستیں، پیٹ مورن مثال کے طور پر سیوڈو کوڈ کے ساتھ مضامین کو ترتیب دیتے ہیں۔