Golang sort.SliceStable在排序后返回不同的结果

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

Golang sort.SliceStable retrun different result after sort

问题

我使用sort.SliceStable对从txt文件中读取的map[string]int进行排序，但排序后的结果不同。我尝试将map转换为结构体或切片，但都没有成功，这种结果正常吗？

代码：

  1. func TestStableUseSlice() {
  2.     counts := make(map[string]int)
  3.     f, err := os.Open("/Users/boroughfan/GitDocuments/GoLangPractise/ch01/dup/text_feel_the_light_lyrics.txt")
  4.     if err != nil {
  5.         fmt.Fprintf(os.Stderr, "dup:%v\n", err)
  6.     }
  7.     input := bufio.NewScanner(f)
  8.     for input.Scan() {
  9.         counts[input.Text()]++
  10.     }
  11.     f.Close()
  12.     ///////////////////////////////////////////////////////////
  13.     linesSlice := make([]string, 0, len(counts))
  15.     for line := range counts {
  16.         linesSlice = append(linesSlice, line)
  17.     }
  18.     sort.SliceStable(linesSlice, func(i, j int) bool {
  19.         return counts[linesSlice[i]] < counts[linesSlice[j]]
  20.     })
  22.     for _, line := range linesSlice {
  23.         fmt.Printf("%d\t%s\n", counts[line], line)
  24.     }
  25. }
  26. func TestStableUsePair() {
  27.     counts := make(map[string]int)
  28.     f, err := os.Open("/Users/boroughfan/GitDocuments/GoLangPractise/ch01/dup/text_feel_the_light_lyrics.txt")
  29.     if err != nil {
  30.         fmt.Fprintf(os.Stderr, "dup:%v\n", err)
  31.     }
  32.     input := bufio.NewScanner(f)
  33.     for input.Scan() {
  34.         counts[input.Text()]++
  35.     }
  36.     f.Close()
  37.     ///////////////////////////////////////////////////////////
  38.     pairList := make([]Pair, 0, len(counts))
  39.     for line := range counts {
  40.         pairList = append(pairList, Pair{line, counts[line]})
  41.     }
  42.     sort.SliceStable(pairList, func(i, j int) bool { return pairList[i].Value < pairList[j].Value })
  43.     for _, pairs := range pairList {
  44.         fmt.Printf("%d\t%s\n", pairs.Value, pairs.Key)
  45.     }
  46. }

这是txt文件的内容：

  1. // this is the dup test file, contents are from the feel the light lyrics
  2. "Feel The Light"
  3. (from "Home" soundtrack)
  4. Hmm, hmm
  5. Hmm
  6. Here I go, here I go
  7. Feel better now, feel better now
  8. Here I go, here I go
  9. It's better now,
  11. <details>
  12. <summary>英文:</summary>
  14. I use sort.SliceStable for a map[string]int which read form a txt file, but after sort the results are different. I have tried translate the map to struct or slices but ethier wored, is it normally for the results?
  15. code:
  17. &lt;!-- begin snippet: js hide: false console: true babel: false --&gt;
  19. &lt;!-- language: lang-html --&gt;
  21.     func TestStableUseSlice() {
  22.     	counts := make(map[string]int)
  23.     	f, err := os.Open(&quot;/Users/boroughfan/GitDocuments/GoLangPractise/ch01/dup/text_feel_the_light_lyrics.txt&quot;)
  24.     	if err != nil {
  25.     		fmt.Fprintf(os.Stderr, &quot;dup:%v\n&quot;, err)
  26.     	}
  27.     	input := bufio.NewScanner(f)
  28.     	for input.Scan() {
  29.     		counts[input.Text()]++
  30.     	}
  31.     	f.Close()
  32.     	///////////////////////////////////////////////////////////
  33.     	linesSlice := make([]string, 0, len(counts))
  35.     	for line := range counts {
  36.     		linesSlice = append(linesSlice, line)
  37.     	}
  38.     	sort.SliceStable(linesSlice, func(i, j int) bool {
  39.     		return counts[linesSlice[i]] &lt; counts[linesSlice[j]]
  40.     	})
  42.     	for _, line := range linesSlice {
  43.     		fmt.Printf(&quot;%d\t%s\n&quot;, counts
    , line)
  44.     	}
  45.     }
  46.     func TestStableUsePair() {
  47.     	counts := make(map[string]int)
  48.     	f, err := os.Open(&quot;/Users/boroughfan/GitDocuments/GoLangPractise/ch01/dup/text_feel_the_light_lyrics.txt&quot;)
  49.     	if err != nil {
  50.     		fmt.Fprintf(os.Stderr, &quot;dup:%v\n&quot;, err)
  51.     	}
  52.     	input := bufio.NewScanner(f)
  53.     	for input.Scan() {
  54.     		counts[input.Text()]++
  55.     	}
  56.     	f.Close()
  57.     	///////////////////////////////////////////////////////////
  58.     	pairList := make([]Pair, 0, len(counts))
  59.     	for line := range counts {
  60.     		pairList = append(pairList, Pair{line, counts
    })
  61.     	}
  62.     	sort.SliceStable(pairList, func(i, j int) bool { return pairList[i].Value &lt; pairList[j].Value })
  63.     	for _, pairs := range pairList {
  64.     		fmt.Printf(&quot;%d\t%s\n&quot;, pairs.Value, pairs.Key)
  65.     	}
  66.     }
  68. &lt;!-- end snippet --&gt;
  70. here is the txt file:
  72. ```txt
  73. // this is the dup test file, contents are from the feel the light lyrics
  74. &quot;Feel The Light&quot;
  75. (from &quot;Home&quot; soundtrack)
  76. Hmm, hmm
  77. Hmm
  78. Here I go, here I go
  79. Feel better now, feel better now
  80. Here I go, here I go
  81. It&#39;s better now, feel better now
  82. Do you remember when we fell under
  83. Did you expect me to reason with thunder
  84. I still remember when time was frozen
  85. What seemed forever was just a moment
  86. Hurry up, hurry up
  87. There&#39;s no more waiting
  88. We&#39;re still worth saving
  89. Feel the light
  90. Shining in the dark of night
  91. Remember what we forgot
  92. I know it&#39;s a long shot
  93. But we&#39;re bringing it all back
  94. We&#39;re bringing it all back
  95. Feel the light
  96. Shining like the stars tonight
  97. Remember what we forgot
  98. I know it&#39;s a long shot
  99. But we&#39;re bringing it all back
  100. We&#39;re bringing it all back
  101. Here I go, here I go
  102. Feel better now, feel better now
  103. Here I go, here I go
  104. It&#39;s better now, feel better now
  105. I still remember when things were broken
  106. But put together the cracks we&#39;ll close in
  107. Hurry up, hurry up
  108. There&#39;s no more waiting
  109. We&#39;re still worth saving
  110. Feel the light
  111. Shining in the dark of night
  112. Remember what we forgot
  113. I know it&#39;s a long shot
  114. But we&#39;re bringing it all back
  115. We&#39;re bringing it all back
  116. Feel the light
  117. Shining like the stars tonight
  118. Remember what we forgot
  119. I know it&#39;s a long shot
  120. But we&#39;re bringing it all back
  121. We&#39;re bringing it all back
  122. You and I can have it all tonight
  123. So let&#39;s bring it back to life
  124. Now we have another chance to fly
  125. Another chance to make it right
  126. Feel the light
  127. Shining in the dark of night
  128. Remember what we forgot
  129. I know it&#39;s a long shot
  130. Feel the light
  131. Shining like the stars tonight
  132. Remember what we forgot
  133. I know it&#39;s a long shot
  134. But we&#39;re bringing it all back
  135. We&#39;re bringing it all back
  136. Here we go, here we go
  137. Feel better now, feel better now
  138. Here we go, here we go
  139. It&#39;s better now, feel better now

答案1

得分: -1

  1. 对于 counts 中的每一行：
  2. ...

将按照映射给出的随机顺序枚举存储在 counts 映射中的行。

sort.SliceStable() 的 "stable" 部分不会使具有相同出现次数的两行变得无序，相反，它将保留这些行的初始顺序。

例如：

"Here we go, here we go" 和 "We're still worth saving" 都有出现次数为 2，所以：

如果 "Here we go, here we go" 在初始切片中出现在 "We're still worth saving" 之前（或之后），在调用 sort.SliceStable() 后，它仍然会在结果切片中保持在之前（或之后）。

如果你想要一个一致的顺序，可以选择一种完全排序行之间的方式：

  1. sort.SliceStable(linesSlice, func(i, j int) bool {
  2. if counts[linesSlice[i]] != counts[linesSlice[j]] {
  3. return counts[linesSlice[i]] < counts[linesSlice[j]]
  4. }
  5. // 在这个例子中：如果行具有相同的计数，按字母顺序排序它们：
  6. return linesSlice[i] < linesSlice[j]
  7. })

（注意，如果元素之间的顺序是完全的，就不再需要 Stable 了）

英文: 
  1. for line := range counts {
  2. ...

will enumerate the lines stored in the counts map following the randomized order given by the map.

The "stable" part of sort.SliceStable() will not un-randomize two lines which have the same occurrence count in your text -- quite the contrary: it will preserve the initial order of such lines.

For example :

&quot;Here we go, here we go&quot; and &quot;We&#39;re still worth saving&quot; both have count 2, so :

if &quot;Here we go, here we go&quot; appears before (resp. after) &quot;We&#39;re still worth saving&quot; in your initial slice, it will remain before (resp. after) in the resulting slice after calling sort.SliceStable().

If you want a consistent order, choose a way to completely order the lines between them :

  1. sort.SliceStable(linesSlice, func(i, j int) bool {
  2. if counts[linesSlice[i]] != counts[linesSlice[j]] {
  3. return counts[linesSlice[i]] &lt; counts[linesSlice[j]]
  4. }
  5. // in this example: if lines have same count, order them alphabetically:
  6. return linesSlice[i] &lt; linesSlice[j]
  7. })

(note that if the order between elements is complete, you don't need the Stable anymore)

huangapple
  • 本文由 发表于 2022年8月1日 22:29:45
  • 转载请务必保留本文链接：https://go.coder-hub.com/73195260.html
  • go
匿名

发表评论

匿名网友

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

确定