هزینهٔ اجرای کد؛ پیچیدگی زمانی و فضایی در JavaScript و Node.js

فرض کنید گزارش هزینهٔ یک کلاس برای صد ردیف سریع باز می‌شود، اما وقتی دادهٔ یک دانشکده را وارد می‌کنید، همان صفحه کند می‌شود. پیش از تعویض حلقه یا خرید سرور، باید بپرسیم با بزرگ شدن ورودی، چه مقدار کار و حافظه اضافه می‌شود. پیچیدگی زمانی و فضایی زبان پاسخ دادن به همین پرسش است. این آموزش پیش‌نیاز تحلیل آرایه‌هاست: مفهوم‌ها را با کد کوتاه و شمارش قابل مشاهده یاد می‌گیریم، سپس تفاوت این مدل با زمان واقعی دستگاه را مشخص می‌کنیم. هدف، حفظ کردن چند علامت برای مصاحبه نیست؛ می‌خواهیم یک تصمیم برنامه‌نویسی را با دلیل توضیح دهیم.

برای دنبال کردن درس، باید تابع، شرط، حلقه و آرایهٔ ساده را بشناسید. فایل‌های مثال را در پوشه‌ای آزمایشی با پسوند mjs ذخیره کنید و با Node.js ۲۴ یا بالاتر اجرا کنید؛ نصب بسته لازم نیست. مثال‌های بدون import در کنسول مرورگر جدید هم اجرا می‌شوند. هر بلوک مستقل است و نام فایل پیشنهادی خودش را دارد. داده‌ها ساختگی و کوچک‌اند؛ برای یادگیری، اجرای میلیاردها تکرار یا پر کردن حافظه لازم نداریم. پیش از اجرا، خروجی را روی کاغذ حدس بزنید و سپس دلیل اختلاف را بررسی کنید.

۱. اندازهٔ ورودی و واحد کار را اول تعریف کنید

در گزارش هزینه، n را تعداد ردیف‌ها می‌گیریم. واحد کارِ انتخابی ما «بررسی یک ردیف» است؛ در مسئلهٔ دیگری ممکن است تعداد مقایسه، بایت خوانده‌شده یا پیام شبکه مهم باشد. این واحدها را نباید بی‌اعلام جابه‌جا کرد. اگر هر ردیف متنی با طول نامحدود داشته باشد و متن را نیز جست‌وجو کنیم، تعداد ردیف به‌تنهایی اندازهٔ ورودی را کامل توصیف نمی‌کند؛ طول متن هم مهم می‌شود. در مثال‌های عددی این درس، ردیف‌ها ساده‌اند و خواندن یک مقدار عددی و جمع معمولی را در مدل، کار ثابت فرض می‌کنیم.

مدل هزینه، ساده‌سازی آگاهانهٔ اجراست. شمارندهٔ visits فقط تعداد عبور از ردیف را ثبت می‌کند؛ تعداد دستورهای پردازنده یا زمان دقیق را نمی‌شمارد. دسترسی‌ها در مثال‌ها روی آرایهٔ معمولی و شیءهای ساده‌اند، بدون Proxy، getter یا callback با کار پنهان. این شرط مهم است، چون خواندن ظاهراً سادهٔ یک ویژگی می‌تواند در برنامه‌ای دیگر کد کاربر را اجرا کند. مفهوم #validation-contracts اینجا هم کاربرد دارد: فرض داده و مرز تحلیل را بنویسید تا نتیجه را به ورودی و رفتار متفاوت تعمیم ندهید.

۲. هزینهٔ ثابت O(1) و هزینهٔ خطی O(n)

O(1) را «مرتبهٔ ثابت» می‌خوانیم: با زیاد شدن n، تعداد کارهای انتخابی رشد وابسته به n ندارد. ثابت بودن به معنی رایگان بودن یا دقیقاً یک دستور نیست. بررسی یک پرچم یا خواندن نخستین مبلغ، در مدل سادهٔ ما چنین رفتاری دارد. O(n) یا خطی یعنی تعداد کارها متناسب با اندازهٔ ورودی رشد می‌کند؛ جمع همهٔ مبلغ‌ها باید هر ردیف را بخواند. در فایل linear-report.mjs کد زیر را اجرا کنید. تعداد visits برای چهار ردیف چهار است و با دو برابر کردن تعداد ردیف، دو برابر می‌شود.

const rows = [
  { id: 'e1', amount: 100 }, { id: 'e2', amount: 200 },
  { id: 'e3', amount: 300 }, { id: 'e4', amount: 400 }
];
function summarize(items) {
  let total = 0;
  let visits = 0;
  for (const item of items) { total += item.amount; visits++; }
  return { total, visits };
}
console.log(rows[0].amount); // 100; one selected field read
console.log(JSON.stringify(summarize(rows))); // {"total":1000,"visits":4}
console.log(JSON.stringify(summarize([...rows, ...rows])));
// {"total":2000,"visits":8}

این شمارش، هزینهٔ ساخت دادهٔ نمونه را جزو summarize نگرفته است. عبارت spread برای ورودی دوم خودش کپی می‌سازد؛ اگر هزینهٔ کل برنامه را می‌سنجید، آن را هم حساب کنید. دو حلقهٔ پشت سر هم روی n ردیف، حدود 2n کار ردیفی دارند و همچنان در ردهٔ O(n) قرار می‌گیرند. حذف ضریب ثابت برای توصیف رشد مفید است، ولی تفاوت یک و دو بار پیمایش می‌تواند در اندازهٔ واقعی اثر داشته باشد. بنابراین برابر بودن مرتبه، به معنی برابر بودن سرعت یا تخصیص حافظه نیست.

Big O یک کران بالا برای رشد است، نه شمارهٔ ثانیه و نه الزاماً شمارش دقیق. معمولاً تنگ‌ترین ردهٔ مناسب را می‌نویسیم تا توضیح مفید باشد؛ گفتن O(n²) برای یک پیمایش خطی، هرچند کران بالای بسیار شلی است، اطلاعات مسئله را پنهان می‌کند. در تحلیل دقیق‌تر، نماد Θ برای کران هم‌مرتبه نیز به کار می‌رود. اینجا تمرکز روی انتخاب مدل و شناخت رشد است. وقتی می‌گوییم خطی، منظور رفتار این الگوریتم با فرض‌های نوشته‌شده است؛ استاندارد زبان را به جدول تضمین زمان تمام متدها تبدیل نمی‌کنیم.

۳. بهترین، بدترین و حالت مورد انتظار

جست‌وجوی ترتیبی ممکن است در نخستین ردیف به پاسخ برسد یا تا انتها ادامه یابد. تابع زیر را در search-count.mjs اجرا کنید. برای وجود شناسه در اول، یک مقایسه داریم؛ برای آخر یا نبودن شناسه، چهار مقایسه. پس بهترین حالت این جست‌وجو ثابت و بدترین حالت خطی است. Big O ذاتاً به معنی «بدترین حالت» نیست؛ باید بنویسید کدام تابع هزینه را توصیف می‌کنید. عبارت «این کد همیشه n بار اجرا می‌شود» با وجود return زودهنگام، نتیجهٔ درستی از یک حلقه نیست.

function findId(rows, id) {
  let comparisons = 0;
  for (const row of rows) {
    comparisons++;
    if (row.id === id) return { found: true, comparisons };
  }
  return { found: false, comparisons };
}
const rows = [{ id: 'a' }, { id: 'b' }, { id: 'c' }, { id: 'd' }];
for (const id of ['a', 'd', 'missing']) {
  console.log(id, JSON.stringify(findId(rows, id)));
}
// a {"found":true,"comparisons":1}
// d {"found":true,"comparisons":4}
// missing {"found":false,"comparisons":4}

هزینهٔ مورد انتظار به فرض احتمالی نیاز دارد. اگر تضمین کنیم پاسخ موجود است و جای آن با احتمال برابر یکی از n خانه است، میانگین تعداد مقایسه‌ها (n+1)/2 می‌شود؛ برای چهار خانه، ۲٫۵ است. این عدد بدون همان فرض معتبر نیست. اگر بیشتر جست‌وجوها بی‌پاسخ باشند، میانگین تجربه‌شده به n نزدیک می‌شود. «میانگین چند اجرای دستگاه من» هم خودبه‌خود اثبات هزینهٔ مورد انتظار برای همهٔ ورودی‌ها نیست. توزیع درخواست واقعی را باید بشناسیم و جدا از بهترین یا بدترین نمونه گزارش کنیم.

۴. دو حلقهٔ تو در تو همیشه O(n²) نیست

اگر برای هر ردیف، تمام ردیف‌های دیگر را بررسی کنیم، تعداد جفت‌ها می‌تواند با مربع اندازه رشد کند. برای ساخت همهٔ جفت‌های بدون تکرار، تعداد دقیق n(n−1)/2 است؛ حذف ضریب و جملهٔ کوچک‌تر، رشد درجهٔ دو را نشان می‌دهد. اما اگر حلقهٔ داخلی همیشه سه بار بچرخد، مجموع 3n و خطی است. در loop-counts.mjs سه شکل را کنار هم ببینید. مورد سوم تعداد گروه‌ها و مجموع اعضا را جدا می‌بیند؛ طول گروه‌ها ثابت یا برابر هم فرض نشده است.

function pairChecks(n) {
  let count = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) count++;
  }
  return count;
}
function threeChecksPerRow(n) {
  let count = 0;
  for (let i = 0; i < n; i++) {
    for (let k = 0; k < 3; k++) count++;
  }
  return count;
}
function countMembers(groups) {
  let members = 0;
  for (const group of groups) {
    for (const member of group) members++;
  }
  return { groups: groups.length, members };
}
console.log(pairChecks(4), pairChecks(8)); // 6 28
console.log(threeChecksPerRow(4), threeChecksPerRow(8)); // 12 24
console.log(JSON.stringify(countMembers([[1, 2], [], [3, 4, 5]])));
// {"groups":3,"members":5}

در پیمایش گروه‌ها، اگر g گروه و m عضو در مجموع داشته باشیم، کار O(g+m) است؛ عضوها دوباره برای هر گروه از ابتدا پیمایش نشده‌اند. اگر دو ورودی مستقل با اندازهٔ n و m را با همهٔ جفت‌ها مقایسه کنیم، مدل O(nm) مناسب است، نه نوشتن بی‌دلیل n². برای تشخیص، تعداد واقعی اجرای بدنه را بنویسید و دامنهٔ هر شمارنده را بررسی کنید. #for-loop نحو حلقه را یادآوری می‌کند؛ این درس از روی فاصله‌گذاری و تعداد واژهٔ for دربارهٔ هزینه حکم نمی‌دهد.

۵. نصف کردن، O(log n) و کار مرحله‌ای O(n log n)

اگر در هر مرحله اندازهٔ مسئله تقریباً نصف شود، تعداد مرحله‌ها آهسته رشد می‌کند. جست‌وجوی دودویی روی دادهٔ مرتب، نمونهٔ آشنای آن است؛ برای استفاده باید از قبل ترتیب مناسب داشته باشیم. ساخت آن ترتیب رایگان نیست. لگاریتم پایهٔ دو می‌پرسد چند بار نصف کنیم تا به یک برسیم. تغییر پایهٔ لگاریتم یک ضریب ثابت ایجاد می‌کند و ردهٔ رشد را عوض نمی‌کند. در مدل مرحله‌ای فایل growth-model.mjs، ورودی توان دو است تا تعداد مرحله دقیق و ساده بماند؛ این کد مرتب‌ساز نیست و زمان Array.sort را اندازه نمی‌گیرد.

function growthModel(n) {
  if (!Number.isSafeInteger(n) || n < 1 || n > 1024 || !Number.isInteger(Math.log2(n))) {
    throw new RangeError('Use a power of two from 1 to 1024');
  }
  let levels = 0;
  for (let size = n; size > 1; size /= 2) levels++;
  return { n, constant: 1, linear: n, levels,
    layered: n * levels, quadratic: n * n };
}
console.log(JSON.stringify(growthModel(8)));
// {"n":8,"constant":1,"linear":8,"levels":3,"layered":24,"quadratic":64}
console.log(JSON.stringify(growthModel(16)));
// {"n":16,"constant":1,"linear":16,"levels":4,"layered":64,"quadratic":256}

اگر در هر یک از حدود log n مرحله، مجموعاً n کار انجام شود، هزینهٔ کلی O(n log n) است. در مرتب‌سازی ادغامی، شکستن مسئله و ترکیب مرتب بخش‌ها چنین الگویی می‌سازد؛ جزئیات الگوریتم را اینجا پیاده نکرده‌ایم. برای n برابر هشت و شانزده، مدل کار مرحله‌ای از ۲۴ به ۶۴ و مدل درجهٔ دو از ۶۴ به ۲۵۶ می‌رود. این عددها «واحد مدل» هستند و نباید کنارشان میلی‌ثانیه نوشت. کوچک بودن ورودی، هزینهٔ آماده‌سازی و مقایسه‌گر می‌تواند نتیجهٔ زمان واقعی را متفاوت کند.

به‌ویژه از این توضیح نتیجه نگیرید هر sort در همهٔ موتورهای جاوااسکریپت، برای هر نوع داده و مقایسه‌گر، زمان و حافظهٔ یکسان دارد. تابع مقایسه می‌تواند خودش متن طولانی پردازش کند یا کار دیگری انجام دهد. #function-expression-callback یادآوری می‌کند هزینهٔ callback جزئی از عملیات است؛ یک فراخوانی متد، لزوماً یک کار ثابت نیست. تحلیل الگوریتم مرحله‌ای و قرارداد زبان دو موضوع مرتبط ولی جدا هستند. در آموزش بعدی، رفتار واقعی آرایه و سنجش نسخهٔ مشخص محیط را دقیق‌تر دنبال می‌کنیم.

۶. تحلیل سرشکن؛ یک عملیات گران در میان عملیات ارزان

فرض کنید ساختاری داریم که هنگام پر شدن، ظرفیتش را دو برابر می‌کند و مقدارهای قبلی را منتقل می‌کند. بعضی افزودن‌ها فقط یک نوشتن دارند و بعضی علاوه بر آن، همهٔ مقدارهای قبلی را کپی می‌کنند. هزینهٔ یک افزودن خاص می‌تواند خطی باشد، ولی جمع هزینهٔ تعداد زیادی افزودن، خطی باقی بماند؛ تقسیم آن مجموع بر تعداد، هزینهٔ سرشکن ثابت می‌دهد. این amortized است و به فرض تصادفی دربارهٔ ورودی نیاز ندارد. پس آن را با میانگین احتمالی جست‌وجو یا تضمین ارزان بودن تک‌تک افزودن‌ها یکی ندانید.

// A counted model of doubling capacity, not the JavaScript engine's allocator.
function doublingModel(insertions) {
  if (!Number.isSafeInteger(insertions) || insertions < 0 || insertions > 1024) {
    throw new RangeError('Use an integer from 0 to 1024');
  }
  let size = 0, capacity = 0, copied = 0, writes = 0;
  for (let i = 0; i < insertions; i++) {
    if (size === capacity) {
      copied += size;
      capacity = capacity === 0 ? 1 : capacity * 2;
    }
    size++; writes++;
  }
  return { insertions, writes, copied, total: writes + copied };
}
console.log(JSON.stringify(doublingModel(16)));
// {"insertions":16,"writes":16,"copied":15,"total":31}
console.log(JSON.stringify(doublingModel(17)));
// {"insertions":17,"writes":17,"copied":31,"total":48}

کد capacity-model.mjs فقط هزینهٔ مدل را می‌شمارد و حافظهٔ ظرفیت‌دار واقعی تخصیص نمی‌دهد. در افزودن هفدهم، شانزده کپی تازه لازم است؛ با این حال مجموع کپی‌های قبلی جمع ۱، ۲، ۴ و ۸ بوده است. رشد هندسی اجازه می‌دهد هزینه در کل توزیع شود. این مثال، اثبات سیاست رشد داخلی Array.push در همهٔ موتورهای جاوااسکریپت نیست. موتور و نوع داده می‌توانند مسیرهای متفاوت داشته باشند. هنگام نیاز به تأخیر حداکثری هر درخواست، دانستن هزینهٔ سرشکن به‌تنهایی کافی نیست و تک‌عملیات گران نیز باید بررسی شود.

۷. پیچیدگی فضایی؛ خروجی را از حافظهٔ کمکی جدا کنید

فضا یعنی داده‌ای که هنگام اجرا باید نگه داریم. ورودی از قبل موجود، خروجی تولیدشده و حافظهٔ کمکی را جدا گزارش کنید. جمع مبلغ‌ها فقط چند متغیر اضافی می‌خواهد و در مدل ما حافظهٔ کمکی O(1) دارد. اگر شناسهٔ همهٔ ردیف‌های پذیرفته‌شده را در آرایهٔ نتیجه نگه دارید، خروجی k خانه می‌خواهد و در بدترین حالت k برابر n است. ثابت بودن تعداد متغیرهای محلی، خروجی خطی را حذف نمی‌کند. عبارت «حافظهٔ ثابت» بدون توضیح اینکه خروجی حساب شده یا نه، می‌تواند خواننده را گمراه کند.

function sumAccepted(rows, minimum) {
  let total = 0;
  for (const row of rows) if (row.amount >= minimum) total += row.amount;
  return total;
}
function acceptedIds(rows, minimum) {
  const output = [];
  for (const row of rows) if (row.amount >= minimum) output.push(row.id);
  return output;
}
const rows = [
  { id: 'e1', amount: 100 }, { id: 'e2', amount: 300 }, { id: 'e3', amount: 200 }
];
console.log(sumAccepted(rows, 200)); // 500
console.log(JSON.stringify(acceptedIds(rows, 200))); // ["e2","e3"]

این کد را در memory-output.mjs اجرا کنید. هر دو تابع همهٔ ردیف‌ها را بررسی می‌کنند، اما شکل نتیجه و حافظهٔ لازم یکسان نیست. ساخت یک کپی کم‌عمق از n ردیف نیز معمولاً به n جای ارجاع تازه نیاز دارد، حتی اگر شیءهای درون آن مشترک باشند. رشتهٔ ساخته‌شده، پشتهٔ فراخوانی بازگشتی و صف پیام‌های نگهداری‌شده را هم فراموش نکنید. شمار دقیق بایت به نمایش موتور و داده وابسته است؛ O(n) برای حافظه، عدد بایت ثابت برای هر شیء تعیین نمی‌کند. آزادشدن ارجاع هم وعدهٔ جمع‌آوری فوری حافظه نیست.

۸. هزینهٔ CPU، انتظار I/O و زمان دیده‌شده

حلقهٔ محاسبه روی پردازنده کار می‌کند؛ خواندن فایل یا پاسخ شبکه می‌تواند بخش زیادی انتظار داشته باشد. مدت دیده‌شده توسط کاربر از هر دو و زمان‌بندی اثر می‌گیرد. در Node.js، حلقهٔ هم‌زمان طولانی روی مسیر اصلی می‌تواند نوبت رسیدگی به درخواست‌های دیگر را عقب بیندازد. افزودن async به نام تابع، همان حلقه را خودکار به پردازندهٔ دیگری منتقل نمی‌کند. #async-basics برای تفکیک Promise و اجرای هم‌زمان داخل تابع مفید است. API ناهم‌زمان I/O نیز هزینهٔ پردازش متن، اعتبارسنجی و ساخت خروجی بعد از دریافت را از بین نمی‌برد.

تحلیل رشد با اندازه‌گیری واقعی کامل می‌شود. performance.now برای فاصلهٔ زمانی مفید است، اما اختلاف دو مقدار آن زمان سپری‌شده است و به‌تنهایی مصرف CPU را گزارش نمی‌کند. نسخهٔ Node و موتور، دستگاه، شکل داده، گرم شدن کد، تخصیص و جمع‌آوری حافظه بر نتیجه اثر دارند. چاپ کنسول درون حلقه نیز کاری جدا وارد آزمایش می‌کند. شمارنده‌های این درس برای فهم تعداد کارند و نباید آن‌ها را بدون تغییر با نسخهٔ بدون شمارنده مقایسهٔ سرعت کرد. روش سنجش تکرارشونده و بررسی درستی، موضوع آموزش بعدی است.

۹. تمرین، پاسخ و معیار آمادگی

تمرین اول: دو پیمایش کامل پشت سر هم را با دو حلقهٔ تو در تو مقایسه کنید و برای n برابر ده و بیست، شمار کار را بنویسید. پاسخ راهنما برای دو پیمایش، ۲۰ و ۴۰ است؛ برای همهٔ جفت‌های مرتب، ۱۰۰ و ۴۰۰. اگر جفت بدون تکرار بسازید، پاسخ به ۴۵ و ۱۹۰ تغییر می‌کند، اما ردهٔ درجهٔ دو باقی می‌ماند. تمرین دوم: در جست‌وجو، احتمال نبودن پاسخ را به مدل اضافه کنید؛ بدون تعیین آن احتمال، یک عدد میانگین عمومی اعلام نکنید.

تمرین سوم: acceptedIds را طوری تغییر دهید که فقط تعداد ردیف‌های پذیرفته‌شده را برگرداند. پاسخ راهنما استفاده از شمارندهٔ عددی به‌جای آرایهٔ خروجی است؛ زمان خطی می‌ماند و حافظهٔ اضافی مدل ثابت می‌شود. تمرین چهارم: برای ۹ افزودن در مدل دو برابر کردن ظرفیت، تعداد کپی را حدس بزنید؛ پاسخ ۱۵ کپی و ۹ نوشتن، یعنی مجموع ۲۴ است. معیار آمادگی، توضیح فرض‌ها و تفکیک تک‌عملیات از هزینهٔ کل است؛ حفظ کردن علامت O بدون گفتن اندازهٔ ورودی، تحلیل کامل محسوب نمی‌شود.

برای مرور گزارش‌گیری با آرایه و انتخاب ساختار داده، این درس متوسط را بخوانید: https://www.darsavand.com/courses/javascript-project-lab?lesson=6b314ebc-2e12-443e-b0bf-cdb27d3abb96
برای حلقهٔ رویداد و هزینهٔ کار هم‌زمان در Node.js، به این درس برگردید: https://www.darsavand.com/courses/nodejs-windows-backend-start?lesson=852c12c3-e66d-4c16-91b3-166f3d5d6ae2
واژه‌نامهٔ #array نیز برای یادآوری قرارداد پایه در دسترس است. پس از اجرای مثال‌ها و نوشتن پاسخ تمرین‌ها، به آموزش بعد بروید؛ آنجا رفتار آرایه، درستی تبدیل‌ها و سنجش را با جزئیات بررسی می‌کنیم:
https://www.darsavand.com/resources/javascript-nodejs-arrays-performance

منابع رسمی انگلیسی برای مطالعهٔ تکمیلی:
MIT OpenCourseWare — Data Structures and Dynamic Arrays: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/79a07dc1cb47d76dae2ffedc701e3d2b_MIT6_006S20_lec2.pdf
MIT OpenCourseWare — Merge Sort: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/1869dbf640ded6b31f1bd369d2001ef5_MIT6_006S20_r03.pdf
Node.js — Don't Block the Event Loop: https://nodejs.org/learn/asynchronous-work/dont-block-the-event-loop
Node.js — Performance measurement APIs: https://nodejs.org/api/perf_hooks.html
MDN — Array.prototype.sort: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

تألیف فارسی، مدل‌های شمارشی و تمرین‌های مستقل: تحریریه درس‌آوند. منابع، مبنای مفاهیم‌اند؛ مثال‌ها ترجمهٔ سطر‌به‌سطر مقاله‌ای دیگر نیستند.

برای تمرین مرحلهٔ بعد، فایل آزمایشگاه آرایه‌ها و راهنمای اجرای آن را دریافت کنید:
https://www.darsavand.com/resources/javascript-arrays-performance-lab