Implementation of Golang Knapsack and Iterator

Data structure and several basic API s

package Bag

type Bag struct {
	first *node
	n     int
}

type node struct {
	item interface{}
	next *node
}

func NewBag() Bag {
	return Bag{}
}

func (b Bag) IsEmpty() bool {
	return b.n == 0
}

func (b Bag) Size() int {
	return b.n
}

func (b *Bag) Add(item interface{}) {
	oldfirst := b.first
	b.first = &node{}
	b.first.item = item
	b.first.next = oldfirst
	b.n++
}

Simple knapsack iteration interface

Because go language does not provide native iteration interface support, it needs to be implemented by itself to use iteration. Iteration is an important method of knapsack data structure. The following is a simple iterative implementation:

//Export all elements in the knapsack as slices
func (b Bag) Iterator() []interface{} {
	s := []interface{}{}
	p := b.first
	for i := 0; i < b.n; i++ {
		s = append(s, p.item)
		p = p.next
	}
	return s
}

This simple iterative implementation principle is to traverse the list, export all the elements into a slice, and then return, so that the elements can be iterated through go for range.
This scheme duplicates all data in the knapsack in memory at the beginning of iteration, which is simple to implement and fast to iterate, but it takes time to generate slices and takes up twice the memory, so it is not suitable for the case of large amount of data.

An improved iterator

This version of iterator is designed to store a variable index in the knapsack class to record the location of the current iteration.

type Bag struct {
	first *node
	n     int
	index *node
}

//Eliminating the Intermediate Method

//Initialization iterator
func (b *Bag) InitIterator() {
	b.index = b.first
}

//Check the next element
func (b Bag) HasNext() bool {
	return b.index != nil
}

//Get the next element
func (b *Bag) Next() interface{} {
	item := b.index.item
	b.index = b.index.next
	return item
}

Here is the code for testing the iterator:

func main() {
	b := Bag.NewBag()
	b.Add(1)
	b.Add(2)
	b.Add(3)
	for b.InitIterator(); b.HasNext(); {
		fmt.Println(b.Next())
	}
}

Console output:

[Running] go run "/Users/bbfat/Desktop/Learn/data structure/knapsack/main.go"
3
2
1

[Done] exited with code=0 in 0.231 seconds

This iteration method performs well in time efficiency and space efficiency, but each time we want to achieve iteration function in a class, we need to define these three interfaces. The abstraction of Chengdu is not high.

Implementing Abstract iterator classes by using coprocesses and interfaces

One of the major features of go language is concurrency, which benefits from its coordinating mechanism. Now I'm going to build an iterator class using coordinating and channels.

package Iterator

// Coprocess Iterative Interface
// Iterable objects need to implement the StartIterate method, which requires the following:
// This method continuously returns data through channels before iteration is completed.
// Returning nil represents iteration completion
type IteratorObj interface {
	StartIterate(ch chan interface{})
}

type Iterator struct {
	it IteratorObj
	ch chan interface{}
}

//Create an Iterator object
func InitIterator(it IteratorObj) Iterator {
	ch := make(chan interface{})
	go it.StartIterate(ch)
	return Iterator{it, ch}
}

//Receiving data from the collaboration and returning it during iteration
func (it Iterator) Next() interface{} {
	return <-it.ch
}

StartIterate Interface Method

Iterator is used for iteration of iterative classes, which need to implement this interface. This interface method will be started as a co-process. Iterative classes use their own logic to iterate and pass the results of each iteration to the buffer-free channel ch.

InitIterator function

This function receives an IteratorObj interface type as a parameter, creates an interface type channel, then starts the protocol and returns an Iterator object.

Next method

This method works on the Iterator object, which receives and returns data from ch channel.

Implementation of IteratorObj Interface with Knapsack

Add a method under the Bag class

//Implementing Iterative Class Interface
func (b Bag) StartIterate(ch chan interface{}) {
	index := b.first
	for {
		if index == nil {
			ch <- nil
			break
		} else {
			ch <- index.item
			index = index.next
		}
	}
}

It is a common list traversal, in which the channel is added to transmit data.

Testing coprocess iteration through knapsack

func main() {
	b := Bag.NewBag()
	for i := 0; i < 100; i++ {
		b.Add(i)
	}

    //The following are the specific uses of iterations
	it := Iterator.InitIterator(b)
	for v := it.Next(); v != nil; v = it.Next() {
		fmt.Println(v)
	}
}

Test output:

[Running] go run "/Users/bbfat/Desktop/Learn/data structure/knapsack/main.go"
99
98
//Intermediate ellipsis
1
0

[Done] exited with code=0 in 0.26 seconds

The test was successful!

Test and compare the performance differences of different iterations

1. Generative slicing

func main() {
	b := Bag.NewBag()
	for i := 0; i < 10000000; i++ {
		b.Add(i)
	}
	for _, i := range b.Iterator() {
		fmt.Print(i)
	}
}
Test Number Time use (s)
1 3.091
2 2.606
3 2.486
4 2.478
5 2.538
6 3.031
Average 2.075

2. Direct Iteration Method

func main() {
	b := Bag.NewBag()
	for i := 0; i < 10000000; i++ {
		b.Add(i)
	}
	for b.InitIterator(); b.HasNext(); {
		fmt.Print(b.Next())
	}
}
Test Number Time use (s)
1 1.183
2 1.131
3 1.426
4 1.584
5 1.139
6 1.085
Average 1.258

3. Coefficient Iteration Method

func main() {
	b := Bag.NewBag()
	for i := 0; i < 10000000; i++ {
		b.Add(i)
	}
	it := Iterator.InitIterator(b)
	for v := it.Next(); v != nil; v = it.Next() {
		fmt.Print(v)
	}
}
Test Number Time use (s)
1 1.154
2 1.555
3 1.491
4 1.541
5 1.526
6 1.544
Average 1.468

Overview

Iterative method of slicing generation is not a good choice. It not only occupies a large amount of memory, but also consumes a long time. The direct iteration method is the most efficient, but it is more difficult to implement. The efficiency of the co-process iteration method and the direct iteration method are only a little lower, but it is very comfortable to implement, so my choice is to use the co-process iteration. Law, which is also the charm of go language.

Improvement of Coefficient Iteration Method

There is a flaw in the current collaboration iteration method, which is that it can't exit the collaboration gracefully. If the iteration can't be forced to end in half, the process responsible for iteration will always be blocked in the stack, which is very unpleasant. Next, I will try to improve this problem.

Upgrade Iterator Obj

type IteratorObj interface {
	StartIterate(ch chan interface{}, stop chan bool)
}

An additional channel is added to control the termination of the process, so the interface implementation of the knapsack class also needs to be adjusted:

//Implementing Iterative Class Interface
func (b Bag) StartIterate(ch chan interface{}, stop chan bool) {
	index := b.first
	for {
		select {
		case <-stop:
			return
		default:
			if index == nil {
				ch <- nil
				return
			} else {
				ch <- index.item
				index = index.next
			}
		}
	}
}

select statement

This is a unique statement of go language in order to better support the protocol. It is similar to the common switch, but after each case it must be a communication-related expression. A difference between go and other languages is that go has its own break, and so does select.
When the message from the stop channel is received, the function returns, the coprocess exits gracefully, and in other cases, the previous iteration logic is continued.

Finish function

This function is used to send an exit signal to the iteration process.

//Stop Iterative Coefficient
func (it Iterator) Finish() {
	mutex := sync.Mutex{}
	mutex.Lock()
	<-it.ch
	it.stop <- true
	mutex.Unlock()
}

This uses mutex, which ensures that code between Lock() and Unlock() is not interrupted by other coroutines.
In this way, we first lock, then take out the data blocked by ch channel, then send the signal to stop channel, and finally unlock it so that the iteration process can continue to execute. At this time, the iteration process will monitor the signal coming from stop channel, so that it will execute return exit.

test

func main() {
	b := Bag.NewBag()
	for i := 0; i < 10; i++ {
		b.Add(i)
	}
	it := Iterator.InitIterator(b)
	for v := it.Next(); v != nil; v = it.Next() {
		fmt.Print(v)
		if v.(int) == 5 {
			it.Finish()
			return
		}
	}
}

Console output:

API server listening at: 127.0.0.1:6347
98765

The test was successful!

The code in this section

Tags: Go

Posted on Mon, 26 Aug 2019 00:48:51 -0700 by yhingsmile