تكرار السؤال: …
الإجابة المختصرة
بسبب التموضع المكاني في الذاكرة (Spatial Locality) ومواءمتها مع خطوط التخزين المؤقت للمعالج (CPU Cache Lines)، بينما تتوزع عقد القائمة المترابطة عشوائياً في الـ Heap.
الشرح
تُخزن عناصر المصفوفة في كتل متجاورة فيزيائياً في الذاكرة (Contiguous Memory). عندما يقرأ المعالج عنصراً، يقوم تلقائياً بجلب الكتلة المحيطة بالكامل (Cache Line عادة 64 بايت) إلى الـ L1/L2 Cache، فتكون العناصر التالية جاهزة بسرعة نانو ثانية دون التوجه للـ RAM. في المقابل، كل عقدة (Node) في Linked List تُخصص في مكان عشوائي في الذاكرة وتتطلب مؤشراً إضافياً، مما يسبب إخفاقات مستمرة في التخزين المؤقت (Cache Misses).
مثال بالكود
import time
N = 1_000_000
array = list(range(N)) # contiguous: elements share cache lines
class Node:
__slots__ = ("value", "next")
def __init__(self, value, next=None):
self.value, self.next = value, next
head = None
for v in reversed(range(N)):
head = Node(v, head) # nodes are scattered across the heap
def sum_array():
return sum(array)
def sum_linked_list():
total, node = 0, head
while node:
total += node.value
node = node.next # pointer chasing → frequent cache misses
return total
for fn in (sum_array, sum_linked_list):
start = time.perf_counter()
fn()
print(fn.__name__, f"{time.perf_counter() - start:.3f}s")أخطاء شائعة
- الاعتقاد بأن Linked List أفضل دائماً من Array للإدراج في البداية O(1)، متجاهلين أن كلفة تخصيص الذاكرة للعقدة والـ Cache Misses تجعل المصفوفة الديناميكية أسرع في معظم الحالات العملية الصغيرة.