Jak odwrócić ciąg w Go?

Jak możemy odwrócić prosty ciąg w Go?

W Go1 runa jest typem wbudowanym.

func Reverse(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

Sugeruje Russ Cox z listy mailingowej golang-nuts

package main 
import "fmt"
func main() { 
        input := "The quick brown 狐 jumped over the lazy 犬" 
        // Get Unicode code points. 
        n := 0
        rune := make([]rune, len(input))
        for _, r := range input { 
                rune[n] = r
                n++
        } 
        rune = rune[0:n]
        // Reverse 
        for i := 0; i < n/2; i++ { 
                rune[i], rune[n-1-i] = rune[n-1-i], rune[i] 
        } 
        // Convert back to UTF-8. 
        output := string(rune)
        fmt.Println(output)
}

Działa to bez bałaganu z funkcjami:

func Reverse(s string) (result string) {
  for _,v := range s {
    result = string(v) + result
  }
  return 
}

Działa to na ciągach Unicode, biorąc pod uwagę dwie rzeczy:

• zakres działa na łańcuchu, wyliczając znaki Unicode
• string może być zbudowany z kawałków int, gdzie każdy element jest znakiem Unicode.

Więc oto idzie:

func reverse(s string) string {
    o := make([]int, utf8.RuneCountInString(s));
    i := len(o);
    for _, c := range s {
        i--;
        o[i] = c;
    }
    return string(o);
}

Z przykładowych projektów Go: golang / example / stringutil / reverse.go , autorstwa Andrew Gerranda

/*
Copyright 2014 Google Inc.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
     http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/

// Reverse returns its argument string reversed rune-wise left to right.
func Reverse(s string) string {
    r := []rune(s)
    for i, j := 0, len(r)-1; i < len(r)/2; i, j = i+1, j-1 {
        r[i], r[j] = r[j], r[i]
    }
    return string(r)
}

Przejdź do placu zabaw, aby odwrócić ciąg

Po odwróceniu łańcucha „bròwn”, poprawnym wynikiem powinno być „nwòrb”, a nie „nẁorb”.
Zwróć uwagę na grób nad literą o.

Aby zachować łączenie znaków Unicode, takich jak „as⃝df̅” z odwrotnym wynikiem „f̅ds⃝a”,
zapoznaj się z innym kodem wymienionym poniżej:

http://rosettacode.org/wiki/Reverse_a_string#Go

Zauważyłem to pytanie, kiedy Simon opublikował swoje rozwiązanie które, ponieważ ciągi znaków są niezmienne, jest bardzo nieefektywne. Inne proponowane rozwiązania również są wadliwe; nie działają lub są nieefektywne.

Oto wydajne rozwiązanie, które działa, z wyjątkiem sytuacji, gdy ciąg nie jest prawidłowym kodem UTF-8 lub ciąg zawiera łączone znaki.

package main

import "fmt"

func Reverse(s string) string {
    n := len(s)
    runes := make([]rune, n)
    for _, rune := range s {
        n--
        runes[n] = rune
    }
    return string(runes[n:])
}

func main() {
    fmt.Println(Reverse(Reverse("Hello, 世界")))
    fmt.Println(Reverse(Reverse("The quick brown 狐 jumped over the lazy 犬")))
}

Jest tu zbyt wiele odpowiedzi. Niektóre z nich są wyraźnymi duplikatami. Ale nawet z lewej strony trudno wybrać najlepsze rozwiązanie.

Więc przejrzałem odpowiedzi, wyrzuciłem ten, który nie działa dla Unicode, a także usunąłem duplikaty. Porównałem tych, którzy przeżyli, aby znaleźć najszybszego. Tak oto wyniki z przypisania (jeśli zauważy się, że brakowało mi odpowiedzi, ale warto dodać, nie krępuj się zmodyfikować wzorzec):

Benchmark_rmuller-4   100000         19246 ns/op
Benchmark_peterSO-4    50000         28068 ns/op
Benchmark_russ-4       50000         30007 ns/op
Benchmark_ivan-4       50000         33694 ns/op
Benchmark_yazu-4       50000         33372 ns/op
Benchmark_yuku-4       50000         37556 ns/op
Benchmark_simon-4       3000        426201 ns/op

Oto najszybsza metoda rmullera :

func Reverse(s string) string {
    size := len(s)
    buf := make([]byte, size)
    for start := 0; start < size; {
        r, n := utf8.DecodeRuneInString(s[start:])
        start += n
        utf8.EncodeRune(buf[size-start:], r)
    }
    return string(buf)
}

Z jakiegoś powodu nie mogę dodać testu porównawczego, więc możesz go skopiować z PlayGround(nie możesz tam uruchomić testów). Zmień nazwę i uruchomgo test -bench=.

Napisałem następującą Reversefunkcję, która uwzględnia kodowanie UTF8 i połączone znaki:

// Reverse reverses the input while respecting UTF8 encoding and combined characters
func Reverse(text string) string {
    textRunes := []rune(text)
    textRunesLength := len(textRunes)
    if textRunesLength <= 1 {
        return text
    }

    i, j := 0, 0
    for i < textRunesLength && j < textRunesLength {
        j = i + 1
        for j < textRunesLength && isMark(textRunes[j]) {
            j++
        }

        if isMark(textRunes[j-1]) {
            // Reverses Combined Characters
            reverse(textRunes[i:j], j-i)
        } 

        i = j
    }

    // Reverses the entire array
    reverse(textRunes, textRunesLength)

    return string(textRunes)
}

func reverse(runes []rune, length int) {
    for i, j := 0, length-1; i < length/2; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
}

// isMark determines whether the rune is a marker
func isMark(r rune) bool {
    return unicode.Is(unicode.Mn, r) || unicode.Is(unicode.Me, r) || unicode.Is(unicode.Mc, r)
}

Zrobiłem co w mojej mocy, aby był jak najbardziej wydajny i czytelny. Pomysł jest prosty, przejdź przez runy w poszukiwaniu połączonych postaci, a następnie odwróć runy połączonych postaci na miejscu. Gdy już je wszystkie pokryjemy, odwróć na miejscu runy z całego łańcucha.

Powiedzmy, że chcielibyśmy odwrócić ten ciąg bròwn. Symbol òjest reprezentowany przez dwie runy, jedną odla tego unikodu, \u0301aktóry reprezentuje „grób”.

Dla uproszczenia przedstawmy ciąg w ten sposób bro'wn. Pierwszą rzeczą, którą robimy, jest szukanie połączonych znaków i odwracanie ich. Więc teraz mamy ciąg br'own. Na koniec odwracamy cały ciąg i otrzymujemy nwo'rb. To jest zwracane nam jakonwòrb

Możesz go znaleźć tutaj https://github.com/shomali11/util jeśli chcesz go użyć.

Oto kilka przypadków testowych, które pokazują kilka różnych scenariuszy:

func TestReverse(t *testing.T) {
    assert.Equal(t, Reverse(""), "")
    assert.Equal(t, Reverse("X"), "X")
    assert.Equal(t, Reverse("b\u0301"), "b\u0301")
    assert.Equal(t, Reverse("😎⚽"), "⚽😎")
    assert.Equal(t, Reverse("Les Mise\u0301rables"), "selbare\u0301siM seL")
    assert.Equal(t, Reverse("ab\u0301cde"), "edcb\u0301a")
    assert.Equal(t, Reverse("This `\xc5` is an invalid UTF8 character"), "retcarahc 8FTU dilavni na si `�` sihT")
    assert.Equal(t, Reverse("The quick bròwn 狐 jumped over the lazy 犬"), "犬 yzal eht revo depmuj 狐 nwòrb kciuq ehT")
}

Opierając się na oryginalnej sugestii Stephan202 i wydaje się, że działa dla ciągów znaków Unicode:

import "strings";

func Reverse( orig string ) string {
    var c []string = strings.Split( orig, "", 0 );

    for i, j := 0, len(c)-1; i < j; i, j = i+1, j-1 {
        c[i], c[j] = c[j], c[i]
    }

    return strings.Join( c, "" );
}

Alternatywnie, nie używaj pakietu ciągów, ale nie „bezpieczny dla formatu Unicode”:

func Reverse( s string ) string {
    b := make([]byte, len(s));
    var j int = len(s) - 1;
    for i := 0; i <= j; i++ {
        b[j-i] = s[i]
    }

    return string ( b );
}

//Reverse reverses string using strings.Builder. It's about 3 times faster
//than the one with using a string concatenation
func Reverse(in string) string {
    var sb strings.Builder
    runes := []rune(in)
    for i := len(runes) - 1; 0 <= i; i-- {
        sb.WriteRune(runes[i])
    }
    return sb.String()
}


//Reverse reverses string using string
func Reverse(in string) (out string) {
    for _, r := range in {
        out = string(r) + out
    }
    return
}

BenchmarkReverseStringConcatenation-8   1000000 1571 ns/op  176 B/op    29 allocs/op
BenchmarkReverseStringsBuilder-8        3000000 499 ns/op   56 B/op 6 allocs/op

Używanie strings.Builder jest około 3 razy szybsze niż użycie konkatenacji ciągów

Tutaj jest zupełnie inne, powiedziałbym, bardziej funkcjonalne podejście, nie wymienione wśród innych odpowiedzi:

func reverse(s string) (ret string) {
    for _, v := range s {
        defer func(r rune) { ret += string(r) }(v)
    }
    return
}

To najszybsza realizacja

func Reverse(s string) string {
    size := len(s)
    buf := make([]byte, size)
    for start := 0; start < size; {
        r, n := utf8.DecodeRuneInString(s[start:])
        start += n
        utf8.EncodeRune(buf[size-start:], r)
    }
    return string(buf)
}

const (
    s       = "The quick brown 狐 jumped over the lazy 犬"
    reverse = "犬 yzal eht revo depmuj 狐 nworb kciuq ehT"
)

func TestReverse(t *testing.T) {
    if Reverse(s) != reverse {
        t.Error(s)
    }
}

func BenchmarkReverse(b *testing.B) {
    for i := 0; i < b.N; i++ {
        Reverse(s)
    }
}

Ten kod zachowuje nienaruszone sekwencje łączonych znaków i powinien działać również z nieprawidłowym wejściem UTF-8.

package stringutil
import "code.google.com/p/go.text/unicode/norm"

func Reverse(s string) string {
    bound := make([]int, 0, len(s) + 1)

    var iter norm.Iter
    iter.InitString(norm.NFD, s)
    bound = append(bound, 0)
    for !iter.Done() {
        iter.Next()
        bound = append(bound, iter.Pos())
    }
    bound = append(bound, len(s))
    out := make([]byte, 0, len(s))
    for i := len(bound) - 2; i >= 0; i-- {
        out = append(out, s[bound[i]:bound[i+1]]...)
    }
    return string(out)
}

To mogłoby być trochę bardziej wydajne, gdyby prymitywy Unicode / norm pozwalały na iterację przez granice łańcucha bez przydzielania. Zobacz też https://code.google.com/p/go/issues/detail?id=9055 .

Jeśli potrzebujesz obsługiwać klastry grafemów, użyj modułu unicode lub regexp.

package main

import (
  "unicode"
  "regexp"
)

func main() {
    str := "\u0308" + "a\u0308" + "o\u0308" + "u\u0308"
    println("u\u0308" + "o\u0308" + "a\u0308" + "\u0308" == ReverseGrapheme(str))
    println("u\u0308" + "o\u0308" + "a\u0308" + "\u0308" == ReverseGrapheme2(str))
}

func ReverseGrapheme(str string) string {

  buf := []rune("")
  checked := false
  index := 0
  ret := "" 

    for _, c := range str {

        if !unicode.Is(unicode.M, c) {

            if len(buf) > 0 {
                ret = string(buf) + ret
            }

            buf = buf[:0]
            buf = append(buf, c)

            if checked == false {
                checked = true
            }

        } else if checked == false {
            ret = string(append([]rune(""), c)) + ret
        } else {
            buf = append(buf, c)
        }

        index += 1
    }

    return string(buf) + ret
}

func ReverseGrapheme2(str string) string {
    re := regexp.MustCompile("\\PM\\pM*|.")
    slice := re.FindAllString(str, -1)
    length := len(slice)
    ret := ""

    for i := 0; i < length; i += 1 {
        ret += slice[length-1-i]
    }

    return ret
}

Możesz również zaimportować istniejącą implementację:

import "4d63.com/strrev"

Następnie:

strrev.Reverse("abåd") // returns "dåba"

Lub odwrócić ciąg zawierający znaki łączące unicode:

strrev.ReverseCombining("abc\u0301\u031dd") // returns "d\u0301\u031dcba"

Te implementacje obsługują poprawną kolejność wielobajtów Unicode i łączenie znaków po odwróceniu.

Uwaga: Wbudowane funkcje odwracania ciągów znaków w wielu językach programowania nie zachowują łączenia, a identyfikacja łączonych znaków wymaga znacznie więcej czasu na wykonanie.

Z pewnością nie jest to najbardziej wydajne rozwiązanie pod względem wykorzystania pamięci, ale w przypadku „prostego” bezpiecznego rozwiązania UTF-8 następujące elementy wykonają zadanie i nie zepsują run.

Moim zdaniem najbardziej czytelny i zrozumiały na stronie.

func reverseStr(str string) (out string) {
    for _, s := range str {
        out = string(s) + out
    }

    return
}

Poniższe dwie metody działają szybciej niż najszybsze rozwiązanie, które zachowuje łączenie znaków , chociaż nie oznacza to, że brakuje mi czegoś w mojej konfiguracji testu porównawczego.

//input string s
bs := []byte(s)
var rs string
for len(bs) > 0 {
    r, size := utf8.DecodeLastRune(bs)
    rs += fmt.Sprintf("%c", r)
    bs = bs[:len(bs)-size]
} // rs has reversed string

Druga metoda zainspirowana tym

//input string s
bs := []byte(s)
cs := make([]byte, len(bs))
b1 := 0
for len(bs) > 0 {
    r, size := utf8.DecodeLastRune(bs)
    d := make([]byte, size)
    _ = utf8.EncodeRune(d, r)
    b1 += copy(cs[b1:], d)
    bs = bs[:len(bs) - size]
} // cs has reversed bytes

UWAGA: Ta odpowiedź pochodzi z 2009 roku, więc prawdopodobnie istnieją już lepsze rozwiązania.

Wygląda trochę „okrężnie” i prawdopodobnie niezbyt wydajnie, ale ilustruje, w jaki sposób interfejs Reader może być używany do odczytu z ciągów. IntVectors również wydają się bardzo przydatne jako bufory podczas pracy z łańcuchami utf8.

Byłby jeszcze krótszy w przypadku pominięcia części `` rozmiaru '' i wstawienia do wektora przez Insert, ale myślę, że byłoby to mniej wydajne, ponieważ cały wektor musi być następnie cofany o jeden za każdym razem, gdy dodawana jest nowa runa .

To rozwiązanie zdecydowanie działa ze znakami utf8.

package main

import "container/vector";
import "fmt";
import "utf8";
import "bytes";
import "bufio";


func
main() {
    toReverse := "Smørrebrød";
    fmt.Println(toReverse);
    fmt.Println(reverse(toReverse));
}

func
reverse(str string) string {
    size := utf8.RuneCountInString(str);
    output := vector.NewIntVector(size);
    input := bufio.NewReader(bytes.NewBufferString(str));
    for i := 1; i <= size; i++ {
        rune, _, _ := input.ReadRune();
        output.Set(size - i, rune);
    }
    return string(output.Data());
}

Wersja, która moim zdaniem działa na Unicode. Jest zbudowany na funkcjach utf8.Rune:

func Reverse(s string) string {
    b := make([]byte, len(s));
    for i, j := len(s)-1, 0; i >= 0; i-- {
        if utf8.RuneStart(s[i]) {
            rune, size := utf8.DecodeRuneInString(s[i:len(s)]);
            utf8.EncodeRune(rune, b[j:j+size]);
            j += size;
        }
    }
    return string(b);
}

runa to typ, więc używaj jej. Ponadto Go nie używa średników.

func reverse(s string) string {
    l := len(s)
    m := make([]rune, l)

    for _, c := range s {
        l--
        m[l] = c
    }
    return string(m)
}

func main() {
    str := "the quick brown 狐 jumped over the lazy 犬"
    fmt.Printf("reverse(%s): [%s]\n", str, reverse(str))
}

wypróbuj poniższy kod:

package main

import "fmt"

func reverse(s string) string {
    chars := []rune(s)
    for i, j := 0, len(chars)-1; i < j; i, j = i+1, j-1 {
        chars[i], chars[j] = chars[j], chars[i]
    }
    return string(chars)
}

func main() {
    fmt.Printf("%v\n", reverse("abcdefg"))
}

aby uzyskać więcej informacji, odwiedź http://golangcookbook.com/chapters/strings/reverse/
i http://www.dotnetperls.com/reverse-string-go

Do prostych sznurków można zastosować taką konstrukcję:

func Reverse(str string) string {
    if str != "" {
        return Reverse(str[1:]) + str[:1]
    }
    return ""   
}

Oto jeszcze jedno rozwiązanie:

func ReverseStr(s string) string {
    chars := []rune(s)
    rev := make([]rune, 0, len(chars))
    for i := len(chars) - 1; i >= 0; i-- {
        rev = append(rev, chars[i])
    }
    return string(rev)
}

Jednak powyższe rozwiązanie yazu jest bardziej eleganckie, ponieważ odwraca []runeplasterek w miejscu.

Jeszcze inne rozwiązanie (tm):

package main 
import "fmt"

type Runes []rune

func (s Runes) Reverse() (cp Runes) {
    l := len(s); cp = make(Runes, l)
    // i <= 1/2 otherwise it will mess up with odd length strings
    for i := 0; i <= l/2; i++ { 
        cp[i], cp[l-1-i] = s[l-1-i], s[i] 
    }
    return cp
}

func (s Runes) String() string {
    return string(s)
}

func main() { 
    input := "The quick brown 狐 jumped over the lazy 犬 +odd" 
    r := Runes(input)
    output := r.Reverse()
    valid := string(output.Reverse()) == input
    fmt.Println(len(r), len(output), r, output.Reverse(), valid)
}

package reverseString

import "strings"

// ReverseString - output the reverse string of a given string s
func ReverseString(s string) string {

    strLen := len(s)

    // The reverse of a empty string is a empty string
    if strLen == 0 {
        return s
    }

    // Same above
    if strLen == 1 {
        return s
    }

    // Convert s into unicode points
    r := []rune(s)

    // Last index
    rLen := len(r) - 1

    // String new home
    rev := []string{}

    for i := rLen; i >= 0; i-- {
        rev = append(rev, string(r[i]))
    }

    return strings.Join(rev, "")
}

Test

package reverseString

import (
    "fmt"
    "strings"
    "testing"
)

func TestReverseString(t *testing.T) {

    s := "GO je úžasné!"
    r := ReverseString(s)

    fmt.Printf("Input: %s\nOutput: %s", s, r)

    revR := ReverseString(r)

    if strings.Compare(s, revR) != 0 {
        t.Errorf("Expecting: %s\n. Got: %s\n", s, revR)
    }
}

Wynik

Input: GO je úžasné!
Output: !énsažú ej OG
PASS
ok      github.com/alesr/reverse-string 0.098s

    func reverseString(someString string) string {
        runeString := []rune(someString)
        var reverseString string
        for i := len(runeString)-1; i >= 0; i -- {
            reverseString += string(runeString[i])
        }
        return reverseString
    }