以下のプログラムは,タイトルの3つの手法で検索したときにどのくらいの時間がかかったのかと,検索マッチ場所を返し,csvとして出力するコードです.
検索文字列が1文字のときには,力任せが処理が少なく,最高速となるという予想でしたが,KMPに負けてしまいました.
キャッシュが原因なのでしょうか? それとも,ソースがおかしいのでしょうか?
それとも,スライスを利用したことが原因でしょうか?
困惑しています. 助けてください.
追伸 長いソースでごめんなさい. また,ソースこう直した方がいいみたいのがあれば教えていただけると嬉しいです.
Go
1// ssearch project main.go 2package main 3 4import ( 5 "fmt" 6 "io/ioutil" 7 "os" 8 "ssearch/bm" 9 "ssearch/kmp" 10 "ssearch/simple" 11 "strconv" 12 "time" 13) 14 15var filename []string = []string{ 16 "testin.txt", 17 "The Golden Link of Friendship.txt", 18 "The Great Round World and What Is Going On In It, Vol. 1, No. 28, May 20, 1897.txt", 19 "Fishing and Shooting Sketches.txt", 20 "Take the Reason Prisoner.txt", 21 "Jack Hardy.txt", 22 "Dorothy's Mystical Adventures in Oz.txt", 23 "My Lady Peggy Goes to Town.txt", 24 "A Little Girl in Old Quebec.txt", 25 "Cuore (Heart).txt", 26 "The Argentine Republic.txt", 27 "The Great Conspiracy, Complete.txt", 28} 29 30const try_times = 1000 31 32func out_result(r_file string, file_size int, process_time float64, result []int) string { 33 var out_string string 34 //読み込みファイル名,バイト数,実行時間(ms),適合個数,適合個所 35 out_string = "\"" + r_file + "\"" + "," + strconv.Itoa(file_size) + "," + strconv.FormatFloat(process_time, 'f', 4, 64) + "," + strconv.Itoa(len(result)) + "," 36 for _, val := range result { 37 out_string += strconv.Itoa(val) + "," 38 } 39 return out_string 40} 41func out_file(file_name string, str []string) { 42 var output string 43 for _, val := range str { 44 output += val + "\n" 45 } 46 ioutil.WriteFile(file_name, []byte(output), os.ModePerm) 47} 48 49func main() { 50 var simp_str, kmp_str, bm_str []string 51 var simp_res, kmp_res, bm_res []int 52 //scanner := bufio.NewScanner(os.Stdin) 53 path := make([]string, len(filename)) 54 for i := 0; i < len(path); i++ { 55 path[i] = "./corpus/" + filename[i] 56 } 57 58 for file_id, _ := range filename { 59 buff, err := ioutil.ReadFile(path[file_id]) 60 if err != nil { 61 fmt.Fprintln(os.Stderr, err) 62 os.Exit(1) 63 } 64 65 data := string(buff) 66 67 key := "it must be" 68 { 69 start := time.Now() 70 for i := 0; i < try_times; i++ { 71 simp_res = simple.Search(data, key) 72 } 73 end := time.Now() 74 process_time := (end.Sub(start).Seconds() * 1000) / try_times 75 simp_str = append(simp_str, out_result(filename[file_id], len(data), process_time, simp_res)) 76 } 77 { 78 start := time.Now() 79 for i := 0; i < try_times; i++ { 80 bm_res = bm.Search(data, key) 81 } 82 end := time.Now() 83 process_time := (end.Sub(start).Seconds() * 1000) / try_times 84 bm_str = append(bm_str, out_result(filename[file_id], len(data), process_time, bm_res)) 85 } 86 { 87 start := time.Now() 88 for i := 0; i < try_times; i++ { 89 kmp_res = kmp.Search(data, key) 90 } 91 end := time.Now() 92 process_time := (end.Sub(start).Seconds() * 1000) / try_times 93 kmp_str = append(kmp_str, out_result(filename[file_id], len(data), process_time, kmp_res)) 94 } 95 } 96 out_file("simp.csv", simp_str) 97 out_file("bm.csv", bm_str) 98 out_file("kmp.csv", kmp_str) 99 100} 101
Go
1package kmp 2 3var skip []int 4 5func init_skip(key string) { 6 skip = make([]int, len(key)) 7 skip[0] = 1 8 9 for pos := 1; pos < len(key); pos++ { 10 var k int 11 for k = 1; k < pos; k++ { 12 var m int 13 for m = k; m < pos && key[m] == key[m-k]; m++ { 14 } 15 if m == pos { 16 break 17 } 18 } 19 skip[pos] = k 20 } 21} 22 23func Search(data, key string) (match_position []int) { 24 init_skip(key) 25 26 for kpos, pos := 0, 0; pos < len(data); { 27 if key[kpos] == data[pos] { 28 if kpos == len(key)-1 { 29 match_position = append(match_position, pos-len(key)+1) 30 kpos = 0 31 } else { 32 kpos++ 33 } 34 pos++ 35 } else { 36 if kpos == 0 { 37 pos++ 38 } else { 39 kpos -= skip[kpos] 40 } 41 } 42 43 } 44 return 45}
Go
1package bm 2 3var skip [256]int 4 5func init_skip(key string) { 6 7 for pos := 0; pos < len(key)-1; pos++ { 8 skip[key[pos]] = len(key) - pos - 1 9 } 10 for pos := 0; pos < len(skip); pos++ { 11 if skip[pos] == 0 { 12 skip[pos] = len(key) 13 } 14 } 15} 16 17func Search(data, key string) (match_position []int) { 18 init_skip(key) 19 20 for kpos, pos := 0, 0; pos <= len(data)-len(key); { 21 var dpos int = pos + len(key) 22 for kpos = len(key) - 1; kpos >= 0; kpos-- { 23 dpos -= 1 24 if data[dpos] != key[kpos] { 25 break 26 } else if kpos == 0 { 27 match_position = append(match_position, dpos) 28 } 29 } 30 pos += skip[data[dpos]] 31 } 32 33 return 34}
Go
1package simple 2 3func Search(data, key string) (match_position []int) { 4 for kpos, dpos := 0, 0; dpos <= len(data)-len(key); dpos++ { 5 match := true 6 for kpos = 0; kpos < len(key); kpos++ { 7 if data[dpos+kpos] != key[kpos] { 8 match = false 9 break 10 } 11 } 12 if match == true { 13 match_position = append(match_position, dpos) 14 } 15 } 16 return 17}
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。