alphanumeric sorting in Go

Question

Я читаю строки из хранилища данных GAE, и я хочу сортировать их по алфавиту.

Предположим, что у меня есть что-то вроде этого:

key  name  description sequence 
=========================================== 
ASD.. maths1 it is maths chap21.1 
ASD.. maths2 it is maths chap21.10 
ASD.. maths3 it is maths chap21.2 

Я хочу, чтобы результат отсортирован в алфавитном на поле последовательности, как это:

key  name  description sequence 
=========================================== 
ASD.. maths1 it is maths chap21.1 
ASD.. maths3 it is maths chap21.2 
ASD.. maths2 it is maths chap21.10 

Answer 1

Используйте команду ISO/IEC 14651:2011 для создания последовательности сортировки. Например,

package main 

import (
    "fmt" 
    "sort" 
) 

const maxByte = 1<<8 - 1 

func isDigit(d byte) bool { 
    return '0' <= d && d <= '9' 
} 

func SequenceKey(key string) string { 
    sKey := make([]byte, 0, len(key)+8) 
    j := -1 
    for i := 0; i < len(key); i++ { 
     b := key[i] 
     if !isDigit(b) { 
      sKey = append(sKey, b) 
      j = -1 
      continue 
     } 
     if j == -1 { 
      sKey = append(sKey, 0x00) 
      j = len(sKey) - 1 
     } 
     if sKey[j] == 1 && sKey[j+1] == '0' { 
      sKey[j+1] = b 
      continue 
     } 
     if sKey[j]+1 > maxByte { 
      panic("SequenceKey: invalid key") 
     } 
     sKey = append(sKey, b) 
     sKey[j]++ 
    } 
    return string(sKey) 
} 

type Chapter struct { 
    Key   string 
    Name  string 
    Description string 
    Sequence string 
    SequenceKey string `datastore:"-"` 
} 

type Chapters []*Chapter 

var chapters = Chapters{ 
    {Key: "ASD..", Name: "maths1", Description: "it is maths", Sequence: "chap21.1"}, 
    {Key: "ASD..", Name: "maths2", Description: "it is maths", Sequence: "chap21.10"}, 
    {Key: "ASD..", Name: "maths3", Description: "it is maths", Sequence: "chap21.2"}, 
} 

func (s Chapters) Len() int { 
    return len(s) 
} 

func (s Chapters) Swap(i, j int) { 
    s[i], s[j] = s[j], s[i] 
} 

type BySequenceKey struct{ Chapters } 

func (s BySequenceKey) Less(i, j int) bool { 
    return s.Chapters[i].SequenceKey < s.Chapters[j].SequenceKey 
} 

func main() { 
    for _, chapter := range chapters { 
     chapter.SequenceKey = SequenceKey(chapter.Sequence) 
    } 
    fmt.Println("Unsorted:") 
    for _, chapter := range chapters { 
     fmt.Printf(" sequence: %#v\n", chapter.Sequence) 
     fmt.Printf(" sort key: %#v\n", chapter.SequenceKey) 
     fmt.Printf("  name: %#v\n", chapter.Name) 
    } 
    fmt.Println("Sorted:") 
    sort.Sort(BySequenceKey{chapters}) 
    for _, chapter := range chapters { 
     fmt.Printf(" sequence: %#v\n", chapter.Sequence) 
     fmt.Printf(" sort key: %#v\n", chapter.SequenceKey) 
     fmt.Printf("  name: %#v\n", chapter.Name) 
    } 
} 

Выход:

Unsorted: 
    sequence: "chap21.1" 
    sort key: "chap\x0221.\x011" 
     name: "maths1" 
    sequence: "chap21.10" 
    sort key: "chap\x0221.\x0210" 
     name: "maths2" 
    sequence: "chap21.2" 
    sort key: "chap\x0221.\x012" 
     name: "maths3" 
Sorted: 
    sequence: "chap21.1" 
    sort key: "chap\x0221.\x011" 
     name: "maths1" 
    sequence: "chap21.2" 
    sort key: "chap\x0221.\x012" 
     name: "maths3" 
    sequence: "chap21.10" 
    sort key: "chap\x0221.\x0210" 
     name: "maths2" 

Answer 2

По словам the reference, вы можете просто отсортировать по недвижимости вам необходимо:

От документа:

// Order alphabetically by last name: 
q := datastore.NewQuery("Person").Order("LastName") 

Таким образом, в вашем примере, вы могли бы что-то вдоль линий:

func queryAll(r *http.Request) ([]string, error) { 
    c := appengine.NewContext(r) 
    res := make([]string, 0, 0) 
    t := datastore.NewQuery("YourStructure").Order("Sequence").Run(c) 
    for { 
     var s YourStructure 
     if _, err := t.Next(&s); err == datastore.Done { 
      // Done iterating 
      return res, nil 
     } else if err != nil { 
      // An error happened 
      return nil, err 
     } 
     res = append(res, s.Name) 
    } 
    panic("unreachable") 
} 

Answer 3

Если вы не слишком много номеров строк, вероятно, можно получить все строки и хранить их в срезе. Затем вы можете отсортировать эти записи в ОЗУ, выполнив команду sort.Interface и вызвав функцию sort.Sort. Взгляните на источник sort.IntSlice, если вам нужен пример для этого.

Трудная часть, вероятно, определяет буквенно-цифровой порядок сортировки. Я не знаю точное его определение (и я не смог найти его за это короткое время), но я все равно попытался его реализовать. Вот код, который вы можете использовать для менее методы:

package main 

import "log" 

func less(a, b string) bool { 
    i, j := 0, 0 
    for i < len(a) && j < len(b) { 
     numeric, numA, numB := false, 0, 0 
     for i < len(a) && a[i] >= '0' && a[i] <= '9' { 
      numA = numA*10 + int(a[i]) - '0' 
      numeric = true 
      i++ 
     } 
     for j < len(b) && b[j] >= '0' && b[j] <= '9' { 
      numB = numB*10 + int(b[j]) - '0' 
      numeric = true 
      j++ 
     } 
     if numeric { 
      if numA != numB { 
       return numA < numB 
      } 
      continue 
     } 
     if a[i] != b[j] { 
      return a[i] < b[j] 
     } 
     i++ 
     j++ 
    } 
    return i == len(a) && j != len(b) 
} 

var tests = []struct { 
    a, b string 
    r1, r2 bool 
}{ 
    {"bar", "foo", true, false}, 
    {"foo100", "foo10", false, true}, 
    {"foo100a", "foo100b", true, false}, 
    {"foo", "foo", false, false}, 
    {"100", "100", false, false}, 
    {"foo5", "foo12", true, false}, 
    {"foo5", "fo3", true, false}, 
    {"foo", "foo8", true, false}, 
} 

func main() { 
    for i := range tests { 
     if less(tests[i].a, tests[i].b) != tests[i].r1 { 
      log.Fatalf("test %d failed", i) 
     } 
     if less(tests[i].b, tests[i].a) != tests[i].r2 { 
      log.Fatalf("reverse test %d failed", i) 
     } 

    } 
} 

я не уверен, если код достаточно для вас, или если вам нужно обрабатывать более сложные случаи, но это могло бы обеспечить, по крайней мере хорошее отправной точкой для ваших собственных модификаций.

Answer 4

ответ Петра напомнил мне о collate пакета в go.text хранилище, в subrepo официального репозитория Go, который содержит некоторые пакеты, которые в настоящее время находятся в стадии разработки. Этот пакет предлагает все, что вам нужно, и полностью соответствует языку и юникоду.

Вы можете использовать метод CompareString для сортировки фрагмента строк в памяти, но лучшим подходом было бы сохранить ключ сортировки (последовательность байтов, который можно сравнить как обычно), в качестве дополнительного столбца, и пусть GAE сделайте все остальное для вас.

package main 

import (
    "code.google.com/p/go.text/collate" 
    "code.google.com/p/go.text/locale" 
    "fmt" 
) 

func main() { 
    locId := locale.Make("en-US") 
    col := collate.New(locId) 
    col.SetOptions(collate.Numeric | collate.IgnoreCase) 

    keys := []string{"chap21.1", "chap21.10", "chap21.2", "chap21.03.3", 
     "chap21.3.03", "chap21.03.03"} 

    buf := new(collate.Buffer) 
    for i := 0; i < len(keys); i++ { 
     fmt.Println(keys[i], col.KeyFromString(buf, keys[i])) 
    } 
} 

Edit: Я только что пристальный взгляд на реализацию и большинство методов (в том числе SetOptions и обработки цифровой сортировки) еще не реализованы. Так что этот ответ был, вероятно, немного слишком рано, но, по крайней мере, вы получили представление о том, как вы можете сортировать строки в будущем;)