英文:
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语句
}
}
我想要做的是:
- 找到mySlice中最小的元素,比如
smallestFloat
- 将
smallestFloat
传入switch语句 - 如果
smallestFloat
进入default情况,从mySlice中取下一个最小的浮点数 - 再次执行步骤2
我已经通过for循环完成了第一步和第二步,但是我卡在了第三步和第四步。我目前不知道如何将下一个最小的浮点数从mySlice中重新传入switch语句...
我会非常感谢任何对我的问题的解答。
编辑:我想把我对上述算法的解决方案写出来。
- 创建另一个切片,该切片是mySlice的排序版本。
- 创建一个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:
- identify the smallest element of mySlice ex:
smallestFloat
- run
smallestFloat
through the switch statement - if
smallestFloat
gets to default case take the next smallest float from mySlice - 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.
- create another slice which will be a sorted version of mySlice
- 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 (
"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
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论