آشنایی با Heap و مقایسه آن در یک شبیه سازی

هیپ چیه؟ خلاصه بخوایم بگیم یک درخت باینری تقریبا کامل. چه کمکی بهمون میکنه؟ فرض کنید یک لیست از اعداد داریم و میخوایم دنبال minimum ها بگردیم. توی این مقاله در مورد راه حل معمولی و مقایسش با Heap میپردازیم و با شبیه سازی و بنچ مارک نتیجه و تاثیر رو به چشم می بینیم.

بیاید یک مسئله ساده حل کنیم. یک لیست از اعداد داریم. میخوایم دنبال کوچیکترین عدد توی اون لیست بگردیم. چطور این کارو انجام میدیم؟ یک دور تک تک عددا رو چک میکنیم و کوچیکترین عدد رو نگه میداریم. یعنی اگر N تا عدد داشته باشیم با N بار مقایسه ما کوچیکترین عدد رو پیدا میکنیم. (توی این مثال ها فرض میکنیم تمام عدد ها از 0 بزرگتر هستند)

// FindMin returns minimum number or -1 if numbers is empty
func FindMin(numbers []int) int {
   min := -1
   for _, number := range numbers {
      if min == -1 || number < min {
         min = number
      }
   }
   return min
}

خوب حالا یکم مسئله رو متفاوت کنیم. فرض کنید یک جریانی از ورودی ها داریم طوری که در ثانیه K عدد جدید باید به لیستمون اضافه کنیم و M بار مینیمم رو از لیست بگیریم و حذف کنیم (عملیات pop). با این الگوریتمی که داریم چقدر قراره ازمون وقت بگیره؟

برای اضافه کردن یک آیتم به لیستمون با یک عملیات o(1) - اضافه کردن یک عدد به آخر آرایه - این کار رو انجام میدیم. اما عملیات pop چقدر طول میکشه؟ اول باید عدد مینیمم رو پیدا کنیم که توی N عملیات (N طول آرایه هست) پیداش میکنیم و بعد از حذفش بازم باید در بدترین حالت N عملیات انجام بدیم (اینطور که یک عدد وسط ارایه رو بخوایم حذف کنیم باید تمام عدد های سمت راستش رو یکی بیاریم سمت چپ)

پیچیدگی زمانی این کار ما o(1)*K + o(N)*M هست که میتونیم بگیم o(N)*M. شاید بگید M*o(N) بد نیست؛ اگه عدد های N و M کم باشن چون سرورها خیلی قوی هستن طبیعتا فشاری روشون نمیاد. اما اگر این عدد ها زیاد شن چی؟

فرض کنید لیست ما یک میلیون عدد داشته باشه و M (چند بار مینیمم بگیریم) هم 100 باشه. اون موقع برای این سیستم باید در ثانیه 100 میلیون عملیات انجام بدیم.

توی الگوریتم ها خیلی سعی میشه اون O(N) تبدیل بشه به O(logN). تاثیر بسیار بسیار زیادی روی سیستم میذاره. چطور حالا؟ فرض کنید پیچیدگی زمانی مون M*O(logN) بود. اون موقع هرثانیه کافی بود 1900 عملیات انجام بدیم! یعنی 52هزار برابر سریع تر! اگر بتونیم چنین کاری بکنیم سیستم ما مقیاس پذیر هم خواهد بود. تاثیر افزایش مقدار دیتا روی پرفورمنس سیستم کمتر میشه.

اما چطور O(N) رو به O(LogN) تبدیل کنیم؟

یکی از ساختمان داده های جذاب دنیای کامپیوتر درخت Heap هست. هیپ یک درخت باینری و تقریبا کامله. حالا این یعنی چی؟

درخت باینری یعنی درختی که هر نود اش حداکثر 2 فرزند داره. یعنی میتونه هیچ فرزندی نداشته باشه؛ میتونه یک فرزند داشته باشه یا 2 فرزند. دیگه سه تا نمیتونه. مثل:

حالا هیپ یک درخت تقریبا کامل و باینری ایی هست که توش هر ند از فرزنداش یا حتما کوچیک تره یا حتما بزرگ تره. اگر یک هیپ هر نود از فرزنداش کوچیکتر باشه بهش میگیم min-heap و اگر بزرگتر باشه بهش میگیم max-heap.

حالا اگر یک درخت min-heap داشته باشیم همیشه ریشه مینیمم داده هامون هست. ولی اگر بخوایم یک داده جدید بهش اضافه کنیم چقدر قراره ازمون وقت بگیره؟ بهتره الگوریتمش رو ببینیم.

اضافه کردن داده به Heap

الگوریتم این کار اینطوره که به آخرین برگ درخت داده جدیدمون رو اضافه میکنیم. حالا اون Node رو با پدرش مقایسه میکنیم؛ اگر کوچیکتر باشه یعنی جاش اونجا نیست چون هر node باید از فرزنداش کوچیک تر باشه، پس جای پدر و فرزند رو عوض میکنیم. این عملیات رو اونقدر تکرار میکنیم تا دیگه برسیم به جایی که منطق درخت حفظ بشه و نیاز به Swap کردن نداشته باشیم.

خب این کار چقدر طول میکشه؟ بیاید ساده یه حساب کتاب کنیم. یک درخت کامل به عمق K توش 2^k-1 عدد داریم. یعنی اگر N تا عدد داشته باشیم نیازه در بدترین حالت log(N) بار جا به جایی انجام بدیم ( چون اگه log(N) بار انجام بدیم میرسیم به ریشه ی درخت و اون عدد قطعا مینیمم هست).

بخوایم جمع بندی کنیم تا الان فهمیدیم اگر بخوایم یک عدد به درختمون اضافه کنیم log(N) بار طول میکشه. اما اگه یادتون باشه توی حالت ساده با O(1) یعنی یک عملیات این کار انجام میشد! اینکه داره بیشتر طول میکشه؟ اره ولی نه :) چون قراره توی pop جبران کنه.

پیدا کردن مینیمم در min-heap

توضیح خاصی نداره :) ریشه ما همیشه مینیمم هست. یعنی O(1). حالت ساده این کار O(N) بود. یعنی جای N عملیات داریم یک عملیات انجام میدیم.

برداشت (pop) عدد مینیمم از min-heap

حالا فرض کنید میخوایم مینیمم رو از درخت حذف کنیم. برای این کار کافیه عدد مینیمم رو حذف کنیم و جاش آخرین عددی که به درخت اضافه کردیم رو بذاریم. حالا اون عدد احتمالا از فرزنداش بزرگ تره. اون رو اونقدر میاریم پایین تا برسه به جایی که منطق درخت حفظ بشه.

پیچیدگی زمانی این عملیات چقدره؟ درست حدس زدید. log(n).

حالا بیایم یک حساب کتاب کنیم اگه جای اون روش ساده از Heap استفاده میکردیم چقدر کارمون طول میکشید؟ میدونیم که K تا دیتای جدید اضافه میشه پس اضافه کردن به هیپ K*O(LogN) طول میکشه. از اون طرف هم قراره M تا مینیمم پیدا کنیم که M*O(1) طول میکشه و در نهایت M تا pop که M*O(logN) تا طول میکشه. همه اینا با هم میشه چقدر؟ (M+K) * O(LogN) که دقیقا همون چیزی بود که میخواستیم! بریم پیاده سازیش کنیم و در عمل ببینیم تفاوت چقدره!

پیاده سازی Heap

برای پیاده سازی Heap من از آرایه استفاده میکنم. اینطور که با این فرمول میتونیم با استفاده از ایندکس هر Node ایندکس فرزنداش رو بدست بیاریم.

Left child index = parent index * 2 + 1
Right child index = parent index * 2 + 2

پیاده سازی Min-Heap در گو:

const MaxInt = int(^uint(0) >> 1)

func leftChildIndex(index int) int {
   return index*2 + 1
}
func rightChildIndex(index int) int {
   return index*2 + 2
}
func parentIndex(index int) int {
   if index%2 == 1 {
      index -= 1
   } else {
      index -= 2
   }
   return index / 2
}

type MinHeap struct {
   items []int
}

func NewMinHeap() *MinHeap {
   return &MinHeap{items: make([]int, 0, 0)}
}

func (m *MinHeap) HasLeftChild(index int) bool {
   return leftChildIndex(index) < len(m.items)
}
func (m *MinHeap) HasRightChild(index int) bool {
   return rightChildIndex(index) < len(m.items)
}
func (m *MinHeap) Swap(index1, index2 int) {
   m.items[index1], m.items[index2] = m.items[index2], m.items[index1]
}
func (m *MinHeap) moveUp(index int) {
   if index == 0 {
      return
   }
   parent := parentIndex(index)
   if m.items[parent] > m.items[index] {
      m.Swap(parent, index)
      m.moveUp(parent)
   }
}
func (m *MinHeap) moveDown(index int) {
   if !m.HasLeftChild(index) && !m.HasRightChild(index) {
      return
   }
   value := m.items[index]
   left := MaxInt
   right := MaxInt
   if m.HasLeftChild(index) {
      left = m.items[leftChildIndex(index)]
   }
   if m.HasRightChild(index) {
      right = m.items[rightChildIndex(index)]
   }
   swapIndex := -1
   if value > left && value > right {
      if left < right {
         swapIndex = leftChildIndex(index)
      } else {
         swapIndex = rightChildIndex(index)
      }
   } else if value > left {
      swapIndex = leftChildIndex(index)
   } else if value > right {
      swapIndex = rightChildIndex(index)
   }
   if swapIndex != -1 {
      m.Swap(index, swapIndex)
      m.moveDown(swapIndex)
   }
}

// Pop returns min value or -1 if items is empty
func (m *MinHeap) Pop() int {
   if len(m.items) == 0 {
      return -1
   }
   v := m.items[0]
   m.items[0] = m.items[len(m.items)-1]
   m.items = m.items[:len(m.items)-1] // delete last element of slice
   m.moveDown(0)
   return v
}
func (m *MinHeap) Add(values ...int) {
   for _, value := range values {
      m.add(value)
   }
}
func (m *MinHeap) add(value int) {
   m.items = append(m.items, value)
   m.moveUp(len(m.items) - 1)
}

خب این همه کد زدیم من راه حل معمولی و هم کدشو میزنم که بتونیم واقعا یک مقایسه ببینیم :)

type BadSolution struct {
   items []int
}

func NewBadSolution() *BadSolution {
   return &BadSolution{items: make([]int, 0)}
}
func (b *BadSolution) Add(values ...int) {
   for _, val := range values {
      b.add(val)
   }
}
func (b *BadSolution) add(value int) {
   b.items = append(b.items, value)
}
func (b *BadSolution) Pop() int {
   minIndex := -1
   minValue := -1
   for i, item := range b.items {
      if minValue == -1 || item < minValue {
         minValue = item
         minIndex = i
      }
   }
   b.items = append(b.items[:minIndex], b.items[minIndex+1:]...)
   return minValue
}

حالا بخش جذاب مقایسه پرفورمنس این دو تا کد :) برای این کار میدونم فقط به دو متد Pop و Add نیاز دارم برای همین یک اینترفیس میسازم به اسم Holder و تست رو برای اون اینترفیس مینویسم. بعد یک بار بهش جواب معمولی و یک بار هیپ رو میدم که ببینم چقدر طول میکشه:

func main() {
   Test(NewBadSolution())
   Test(NewMinHeap())
}

type Holder interface {
   Add(values ...int)
   Pop() int
}

func Test(holder Holder) {
   rand.Seed(time.Now().Unix())
   k := 10000
   m := 1000
   iterations := 10
   startTime := time.Now()

   for itr := 0; itr < iterations; itr++ {
      // adding items
      for i := 0; i < k; i++ {
         holder.Add(rand.Int())
      }
      for i := 0; i < m; i++ {
         holder.Pop()
      }
   }
   fmt.Println(&quotFor &quot, reflect.TypeOf(holder), &quotTook &quot, time.Since(startTime))
}

نتیجه تست

اگه تست رو اجرا کنیم نتیجه تست اینطور خواهد بود:

For  *main.BadSolution Took  412.2844ms
For  *main.MinHeap Took  4.9997ms

شاید بگید تفاوت 4 میلی ثانیه با 400 میلی ثانیه خیلی زیاد نیست. فرض کنید درخواست ها زیاد بشه و جای 10 ایتریشن بخوایم 100 ایتریشن داشته باشیم. بنظرتون عددا چطور میشه؟

For  *main.BadSolution Took  42.0210378s
For  *main.MinHeap Took  62.9997ms

می بینیم که 400 میلی ثانیه رسید به 40 ثانیه اما 4 میلی ثانیه رسید به 62 میلی ثانیه.