LoginSignup
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@smith-30

文字列をn個後ろにずらす処理を本気でやる

Last updated at Posted at 2018-05-16

難しそうだからと積読していた珠玉のプログラミングを読みながら
手を動かしながらGoで実験してみました。

お題の repository

お題

要素がn個ある配列を左方向にi要素分回転させるにはどうすればよいか
たとえば、n=5でi=2のとき

配列 abcde を cdeab にする回転

before 自分で考えた実装

sliceが参照であることに注意して、こんな感じで実装しました。

func RotateTaskB(src []string, count int) {
	l := len(src)
	if l == 0 || count == 0 {
		return
	}

	var (
		c int
	)

	switch {
	case l == count:
		return
	case l < count:
		c = count % l
	case l > count:
		c = count
	}

	// 後ろに回す分のデータを新規に確保 (メモリ割り当てが起こる)
	rewind := make([]string, len(src[0:c]))
	copy(rewind, src[0:c])

	// 回転させないデータ領域を先頭にもってくる
	for idx, val := range src[c:l] {
		src[idx] = val
	}

	// 後ろに回す分のデータを整列させたデータの後ろにくっつける
	copy(src[l-c:l], rewind[0:])
}

ベンチ

var (
	refIdx     = map[int][]int{}
	dataCounts = []int{100, 200, 400, 800, 1600, 3200, 6400, 12800, 25600, 51200}
)

func init() {
	for _, dataCount := range dataCounts {
		refIdx[dataCount] = []int{1, dataCount / 2, dataCount - 1}
	}
}

func Benchmark_RotateTaskB(b *testing.B) {
	for _, dataCount := range dataCounts {
		for _, idx := range refIdx[dataCount] {
			b.Run(fmt.Sprintf("dataCount: %v, idx: %v", dataCount, idx), func(b *testing.B) {
				s := bench_helper.GenStrSlice(dataCount)
				b.ResetTimer()
				for i := 0; i < b.N; i++ {
					RotateTaskB(s, idx)
				}
			})
		}
		fmt.Println()
	}
}

func GenStrSlice(count int) []string {
	s := make([]string, 0, count)

	for i := 0; i < count; i++ {
		s = append(s, "a")
	}
	return s
}

Benchmark_RotateTaskB/dataCount:_100,_idx:_1-4         	 5000000	       338 ns/op	      16 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_100,_idx:_50-4        	 2000000	       736 ns/op	     896 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_100,_idx:_99-4        	 2000000	       938 ns/op	    1792 B/op	       1 allocs/op

Benchmark_RotateTaskB/dataCount:_200,_idx:_1-4         	 3000000	       594 ns/op	      16 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_200,_idx:_100-4       	 1000000	      1214 ns/op	    1792 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_200,_idx:_199-4       	 1000000	      1620 ns/op	    3200 B/op	       1 allocs/op

Benchmark_RotateTaskB/dataCount:_400,_idx:_1-4         	 1000000	      1040 ns/op	      16 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_400,_idx:_200-4       	 1000000	      2062 ns/op	    3200 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_400,_idx:_399-4       	  500000	      3105 ns/op	    6528 B/op	       1 allocs/op

Benchmark_RotateTaskB/dataCount:_800,_idx:_1-4         	 1000000	      1963 ns/op	      16 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_800,_idx:_400-4       	  500000	      4163 ns/op	    6528 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_800,_idx:_799-4       	  200000	      6727 ns/op	   13568 B/op	       1 allocs/op

Benchmark_RotateTaskB/dataCount:_1600,_idx:_1-4        	  500000	      3760 ns/op	      16 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_1600,_idx:_800-4      	  200000	      9288 ns/op	   13568 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_1600,_idx:_1599-4     	  100000	     13624 ns/op	   27264 B/op	       1 allocs/op

Benchmark_RotateTaskB/dataCount:_3200,_idx:_1-4        	  200000	      7455 ns/op	      16 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_3200,_idx:_1600-4     	  100000	     19583 ns/op	   27264 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_3200,_idx:_3199-4     	   50000	     29397 ns/op	   57344 B/op	       1 allocs/op

Benchmark_RotateTaskB/dataCount:_6400,_idx:_1-4        	  100000	     15221 ns/op	      16 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_6400,_idx:_3200-4     	   50000	     37289 ns/op	   57344 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_6400,_idx:_6399-4     	   30000	     59300 ns/op	  106496 B/op	       1 allocs/op

Benchmark_RotateTaskB/dataCount:_12800,_idx:_1-4       	   50000	     30026 ns/op	      16 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_12800,_idx:_6400-4    	   20000	     84440 ns/op	  106496 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_12800,_idx:_12799-4   	   10000	    129205 ns/op	  204800 B/op	       1 allocs/op

Benchmark_RotateTaskB/dataCount:_25600,_idx:_1-4       	   20000	     66329 ns/op	      16 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_25600,_idx:_12800-4   	   10000	    202007 ns/op	  204800 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_25600,_idx:_25599-4   	    5000	    309271 ns/op	  409600 B/op	       1 allocs/op

Benchmark_RotateTaskB/dataCount:_51200,_idx:_1-4       	   10000	    117230 ns/op	      16 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_51200,_idx:_25600-4   	    2000	    874801 ns/op	  409600 B/op	       1 allocs/op
Benchmark_RotateTaskB/dataCount:_51200,_idx:_51199-4   	    2000	    893737 ns/op	  819200 B/op	       1 allocs/op

メモリ割り当てが必ず一回発生してしまうので遅い。

after 本書で書かれてた１つの解を実装

実は、本書には条件があって僕はとりあえずそれを無視して↑を作ってみました。
正解とどれくらいパフォーマンス差がでるか知りたかったので。

条件は メモリを数十バイトしか使わずに実行時間もnに比例するだけのように回転させること
僕が作ったプログラムは回転させる位置によってメモリ割り当て量が変わってしまうので
nに比例しないし、メモリもnが増えれば増えるほど割当量が増えてしまう(処理が遅くなる)。

そこで、↑の条件を満たすプログラムを、本書を参考につくりました。
それがこれ。

func NewRotateTaskB(src []string, count int) {
	l := len(src)
	if l == 0 || count == 0 {
		return
	}

	var (
		c int
	)

	switch {
	case l == count:
		return
	case l < count:
		c = count % l
	case l > count:
		c = count
	}

	reverse(src, 0, c-1)
	reverse(src, c, l-1)
	reverse(src, 0, l-1)
}

func reverse(src []string, s, e int) {
	var i int
	for {
		s = s + i
		e = e - i
		if s < e {
			t := src[s]
			src[s] = src[e]
			src[e] = t
		} else {
			break
		}
		i += 1
	}
}

自分で一度書いた改善前の反省から、メモリを割り当てないするためには
うまくスライスのインデックスをいじってやらないとと思っていました。
それをこんなテクニックを使って実装しています

  • 回転させる領域のデータを逆順にする -①
  • 回転させる領域以降のデータを逆順にする -②
  • 全体を逆順にする -③

これだけではわからないと思うので例を元に解説します
スライス: a b c d e f があったとします
これを2要素後ろにずらす処理を上記の手順を踏まえながらやってみます。

最終的に、c d e f a b になってればよいですよね

a b c d e f

↓ ① 2要素分

b a c d e f

↓ ② 2要素目以降を逆順にする

b a f e d c

↓ ③ 全体を逆順にする

c d e f a b

できました、すごいですよね。感動。
細かい理由は後述として、測ってみたいと思います。

ベンチ

// snip
func Benchmark_NewRotateTaskB(b *testing.B) {
	for _, dataCount := range dataCounts {
		for _, idx := range refIdx[dataCount] {
			b.Run(fmt.Sprintf("dataCount: %v, idx: %v", dataCount, idx), func(b *testing.B) {
				s := bench_helper.GenStrSlice(dataCount)
				b.ResetTimer()
				for i := 0; i < b.N; i++ {
					NewRotateTaskB(s, idx)
				}
			})
		}
		fmt.Println()
	}
}

Benchmark_NewRotateTaskB/dataCount:_100,_idx:_1-4         	 5000000	       366 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_100,_idx:_50-4        	 5000000	       469 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_100,_idx:_99-4        	10000000	       401 ns/op	       0 B/op	       0 allocs/op

Benchmark_NewRotateTaskB/dataCount:_200,_idx:_1-4         	10000000	       232 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_200,_idx:_100-4       	10000000	       220 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_200,_idx:_199-4       	10000000	       171 ns/op	       0 B/op	       0 allocs/op

Benchmark_NewRotateTaskB/dataCount:_400,_idx:_1-4         	10000000	       245 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_400,_idx:_200-4       	 5000000	       306 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_400,_idx:_399-4       	 5000000	       249 ns/op	       0 B/op	       0 allocs/op

Benchmark_NewRotateTaskB/dataCount:_800,_idx:_1-4         	 5000000	       338 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_800,_idx:_400-4       	 5000000	       400 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_800,_idx:_799-4       	 5000000	       318 ns/op	       0 B/op	       0 allocs/op

Benchmark_NewRotateTaskB/dataCount:_1600,_idx:_1-4        	 3000000	       461 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_1600,_idx:_800-4      	 3000000	       526 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_1600,_idx:_1599-4     	 3000000	       477 ns/op	       0 B/op	       0 allocs/op

Benchmark_NewRotateTaskB/dataCount:_3200,_idx:_1-4        	 3000000	       627 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_3200,_idx:_1600-4     	 2000000	       811 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_3200,_idx:_3199-4     	 2000000	       585 ns/op	       0 B/op	       0 allocs/op

Benchmark_NewRotateTaskB/dataCount:_6400,_idx:_1-4        	 2000000	       837 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_6400,_idx:_3200-4     	 2000000	       995 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_6400,_idx:_6399-4     	 2000000	       961 ns/op	       0 B/op	       0 allocs/op

Benchmark_NewRotateTaskB/dataCount:_12800,_idx:_1-4       	 1000000	      1325 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_12800,_idx:_6400-4    	 1000000	      1631 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_12800,_idx:_12799-4   	 1000000	      1205 ns/op	       0 B/op	       0 allocs/op

Benchmark_NewRotateTaskB/dataCount:_25600,_idx:_1-4       	 1000000	      1880 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_25600,_idx:_12800-4   	 1000000	      2240 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_25600,_idx:_25599-4   	 1000000	      1741 ns/op	       0 B/op	       0 allocs/op

Benchmark_NewRotateTaskB/dataCount:_51200,_idx:_1-4       	  500000	      2718 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_51200,_idx:_25600-4   	  500000	      3585 ns/op	       0 B/op	       0 allocs/op
Benchmark_NewRotateTaskB/dataCount:_51200,_idx:_51199-4   	 1000000	      2662 ns/op	       0 B/op	       0 allocs/op

メモリ割り当て0。 先程のよりか格段に早い
ひとまず満足のいく実装はできました、結果もでました。

さきほどの効率のよい並べ方の仕組みですが

後ろにずらす部分を a としてそれ以降を b とすると
全体は ab ですよね。これを ba にするのが目標なわけです

その ba のつくりかたが (rはリバース)

ab

↓

a^{r}b

↓

a^{r}b^{r}

↓

(a^{r}b^{r})^{r}

↓

ba

からきているようです。

簡単なお題ですけど、ベストな手を打つのは難しいですね。
今後も書きながら読み進めていこうと思います。

3
2
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?