在递归函数中使用switch语句

huangapple go评论142阅读模式
英文:

GO - switch statement in a recursive function

问题

我有一个算法,我想要实现,但目前我完全不知道如何从技术角度去做。

我们有一个包含5个浮点数的切片:

mySlice := [float1, float2, float3, float4, float5]

还有一个switch语句:

aFloat := mySlice[index]

switch aFloat {
  case 1:
    {
       //做某事
    }
  case 2:
    {
       //做某事
    }
  case 3:
    {
       //做某事
    }
  case 4:
    {
       //做某事
    }
  case 5:
    {
       //做某事
    }
  default:
    {
       //以某种方式返回到切片,取下一个最小的数再次运行switch语句
    }
}

我想要做的是:

  1. 找到mySlice中最小的元素,比如smallestFloat
  2. smallestFloat传入switch语句
  3. 如果smallestFloat进入default情况,从mySlice中取下一个最小的浮点数
  4. 再次执行步骤2

我已经通过for循环完成了第一步和第二步,但是我卡在了第三步和第四步。我目前不知道如何将下一个最小的浮点数从mySlice中重新传入switch语句...

我会非常感谢任何对我的问题的解答。

编辑:我想把我对上述算法的解决方案写出来。

  1. 创建另一个切片,该切片是mySlice的排序版本。
  2. 创建一个map[int]value,其中索引对应于非排序切片中的值的位置,但是map的项按照排序切片的顺序插入。

结果:一个按值排序的map,其中索引对应于原始非排序切片的位置。

英文:

I have an algorithm that I'm trying to implement but currently I have absolutely no clue how to do so, from a technical perspective.

We have a slice of 5 floats:

mySlice := [float1, float2, float3, float4, float5]

And a switch statement:

aFloat := mySlice[index]

switch aFloat {
  case 1:
    {
       //do something 
    }
  case 2:
    {
       //do something 
    }
  case 3:
    {
       //do something 
    }
  case 4:
    {
       //do something 
    }
  case 5:
    {
       //do something 
    }
  default:
    {
       //somehow go back to slice, take the next smallest and run
       //through the switch statement again
    }
}

What I want to do is as follows:

  1. identify the smallest element of mySlice ex: smallestFloat
  2. run smallestFloat through the switch statement
  3. if smallestFloat gets to default case take the next smallest float from mySlice
  4. do step 2 again.

I've managed to do the first step with a for loop and step 2, but I'm stuck on steps 3 and 4. I don't have an idea at the moment on how I might go about re-feeding the next smallest float from mySlice to the switch statement again...

I would appreciate any light shed on my problem.

EDIT: I figured that it would be good to put my solution to the algorithm presented above.

  1. create another slice which will be a sorted version of mySlice
  2. create a map[int]value where the index will correspond to the position of the value in the non-sorted slice, but the items of the map will be inserted in the same order as the sorted slice.

Result: a value sorted map with the respective indexes corresponding to the position of the original non-sorted slice

答案1

得分: 1

这是使用最小优先队列的实现。原始的浮点数切片没有改变。可以在Go playground上运行。

注意:在处理递归函数时,需要注意堆栈溢出的问题。Go只在有限的情况下进行尾递归优化。有关更多信息,请参考这个答案

这个特定的示例甚至比摊还时间复杂度O(log N)更好,因为它不需要在中途调整优先队列的大小。这使得它的时间复杂度保证为O(log N)。

package main

import (
	"fmt"
)

func main() {
	slice := []float64{2, 1, 13, 4, 22, 0, 5, 7, 3}
	fmt.Printf("Order before: %v\n", slice)

	queue := NewMinPQ(slice)

	for !queue.Empty() {
		doSmallest(queue)
	}

	fmt.Printf("Order after: %v\n", slice)
}

func doSmallest(queue *MinPQ) {
	if queue.Empty() {
		return
	}

	v := queue.Dequeue()

	switch v {
	case 1:
		fmt.Println("Do", v)
	case 2:
		fmt.Println("Do", v)
	case 3:
		fmt.Println("Do", v)
	case 4:
		fmt.Println("Do", v)
	case 5:
		fmt.Println("Do", v)
	default:
		// No hit, do it all again with the next value.
		doSmallest(queue)
	}
}

// MinPQ represents a Minimum priority queue.
// It is implemented as a binary heap.
//
// Values which are enqueued can be dequeued, but will be done
// in the order where the smallest item is returned first.
type MinPQ struct {
	values  []float64 // Original input list -- Order is never changed.
	indices []int     // List of indices into values slice.
	index   int       // Current size of indices list.
}

// NewMinPQ creates a new MinPQ heap for the given input set.
func NewMinPQ(set []float64) *MinPQ {
	m := new(MinPQ)
	m.values = set
	m.indices = make([]int, 1, len(set))

	// Initialize the priority queue.
	// Use the set's indices as values, instead of the floats
	// themselves. As these may not be re-ordered.
	for i := range set {
		m.indices = append(m.indices, i)
		m.index++
		m.swim(m.index)
	}

	return m
}

// Empty returns true if the heap is empty.
func (m *MinPQ) Empty() bool { return m.index == 0 }

// Dequeue removes the smallest item and returns it.
// Returns nil if the heap is empty.
func (m *MinPQ) Dequeue() float64 {
	if m.Empty() {
		return 0
	}

	min := m.indices[1]

	m.indices[1], m.indices[m.index] = m.indices[m.index], m.indices[1]
	m.index--
	m.sink(1)
	m.indices = m.indices[:m.index+1]
	return m.values[min]
}

// greater returns true if element x is greater than element y.
func (m *MinPQ) greater(x, y int) bool {
	return m.values[m.indices[x]] > m.values[m.indices[y]]
}

// sink reorders the tree downwards.
func (m *MinPQ) sink(k int) {
	for 2*k <= m.index {
		j := 2 * k

		if j < m.index && m.greater(j, j+1) {
			j++
		}

		if m.greater(j, k) {
			break
		}

		m.indices[k], m.indices[j] = m.indices[j], m.indices[k]
		k = j
	}
}

// swim reorders the tree upwards.
func (m *MinPQ) swim(k int) {
	for k > 1 && m.greater(k/2, k) {
		m.indices[k], m.indices[k/2] = m.indices[k/2], m.indices[k]
		k /= 2
	}
}
英文:

Here is an implementation using a Minimum Priority Queue. The original input slice of floats is not changed. It can be run on the Go playground

Note: When dealing with recursive functions, you need to be weary of stack overflows.
Go does tail recursion optimizations only in limited cases. For more information on that,
refer to this answer.

This particular example does even better than amortized O(log N) time, because it does not have to resize the priority queue halfway through. This makes it guaranteed O(log N).

package main
import (
&quot;fmt&quot;
)
func main() {
slice := []float64{2, 1, 13, 4, 22, 0, 5, 7, 3}
fmt.Printf(&quot;Order before: %v\n&quot;, slice)
queue := NewMinPQ(slice)
for !queue.Empty() {
doSmallest(queue)
}
fmt.Printf(&quot;Order after: %v\n&quot;, slice)
}
func doSmallest(queue *MinPQ) {
if queue.Empty() {
return
}
v := queue.Dequeue()
switch v {
case 1:
fmt.Println(&quot;Do&quot;, v)
case 2:
fmt.Println(&quot;Do&quot;, v)
case 3:
fmt.Println(&quot;Do&quot;, v)
case 4:
fmt.Println(&quot;Do&quot;, v)
case 5:
fmt.Println(&quot;Do&quot;, v)
default:
// No hit, do it all again with the next value.
doSmallest(queue)
}
}
// MinPQ represents a Minimum priority queue.
// It is implemented as a binary heap.
//
// Values which are enqueued can be dequeued, but will be done
// in the order where the smallest item is returned first.
type MinPQ struct {
values  []float64 // Original input list -- Order is never changed.
indices []int     // List of indices into values slice.
index   int       // Current size of indices list.
}
// NewMinPQ creates a new MinPQ heap for the given input set.
func NewMinPQ(set []float64) *MinPQ {
m := new(MinPQ)
m.values = set
m.indices = make([]int, 1, len(set))
// Initialize the priority queue.
// Use the set&#39;s indices as values, instead of the floats
// themselves. As these may not be re-ordered.
for i := range set {
m.indices = append(m.indices, i)
m.index++
m.swim(m.index)
}
return m
}
// Empty returns true if the heap is empty.
func (m *MinPQ) Empty() bool { return m.index == 0 }
// Dequeue removes the smallest item and returns it.
// Returns nil if the heap is empty.
func (m *MinPQ) Dequeue() float64 {
if m.Empty() {
return 0
}
min := m.indices[1]
m.indices[1], m.indices[m.index] = m.indices[m.index], m.indices[1]
m.index--
m.sink(1)
m.indices = m.indices[:m.index+1]
return m.values[min]
}
// greater returns true if element x is greater than element y.
func (m *MinPQ) greater(x, y int) bool {
return m.values[m.indices[x]] &gt; m.values[m.indices[y]]
}
// sink reorders the tree downwards.
func (m *MinPQ) sink(k int) {
for 2*k &lt;= m.index {
j := 2 * k
if j &lt; m.index &amp;&amp; m.greater(j, j+1) {
j++
}
if m.greater(j, k) {
break
}
m.indices[k], m.indices[j] = m.indices[j], m.indices[k]
k = j
}
}
// swim reorders the tree upwards.
func (m *MinPQ) swim(k int) {
for k &gt; 1 &amp;&amp; m.greater(k/2, k) {
m.indices[k], m.indices[k/2] = m.indices[k/2], m.indices[k]
k /= 2
}
}

huangapple
  • 本文由 发表于 2014年3月11日 19:04:51
  • 转载请务必保留本文链接:https://go.coder-hub.com/22323819.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定