Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

CountZero's blog

By CountZero, 5 years ago, In Russian,

Всем привет. В этом посте я хотел бы рассказать о паре, похоже, мало кому известных, но важных моментов, касающихся написания контестов на языке Go.

Среда

Установка среды

Существуют официальные сборки Go для Linux, OS X и Windows. Их можно скачать с офсайта или установить через пакетный менеджер. Например, в случае Windows можно воспользоваться Chocolatey.

Также на офсайте есть масса отличных руководств и онлайн-IDE.

Редактор и отладчик

Среди пишущих на Go наибольшей популярностью пользуется Sublime Text 2 или 3 с плагином GoSublime — вы получите очень удобный редактор с автоформатированием, подсветкой синтаксиса и ошибок, продвинутым автодополнением, сниппетами, и некоторыми возможностями рефакторинга.

Отладка. Если неохота пользоваться GDB из консоли (см. статью), то можно установить LiteIDE.

Язык

Обобщенные вычисления

Формально в Go есть универсальный тип interface{}, в/из которого можно преобразовать что угодно. Однако это преобразование выполняется настолько медленно, что любой ваш код с его использованием неизбежно получит TL. Поэтому в стандартной библиотеке Go из пригодных для использования контейнеров есть только хэш-таблицы, реализованные на уровне языка без использования interface{}.

Массивы против слайсов

Никогда не используйте массивы в Go — по сравнению со слайсами у них нет никаких преимуществ кроме недостатков.

Во-первых, слайсы можно наращивать, точно так же как std::vector в С++:

slice := make([]int, 3) // slice == [0, 0, 0]
slice = append(slice, 1) // slice == [0, 0, 0, 1]

Во-вторых, слайсы можно передавать в функции с переменным числом аргументов, например в упомянутую выше функцию append:

slice1 := []int{1, 2, 3}
slice2 := []int{4, 5}
slice1 = append(slice1, slice2...) //slice1 == [1, 2, 3, 4, 5]

Вложенные функции

Функции в Go ничем не отличаются от типов — их можно объявлять внутри других функций, присваивать, передавать в качестве параметров (см. ниже пример с двоичным поиском). Есть единственная тонкость: объявление рекурсивных вложенных функций, которое выполняется следующим образом

func main() {
    var fib func(i int) int
    fib = func(i int) int {
        switch i {
        case 0: return 0
        case 1: return 1
        default: return fib(i-1) + fib(i-2)
        }
    }
} 

Стандартная библиотека

Ввод-вывод

В тех единицах сабмитов на Go, которые я видел на CF, для ввода-вывода используется пакет fmt. Это фатальная ошибка: там не используется буферизация, зато используется тип interface{}, о котором я написал выше. Поэтому, навсегда забудьте про fmt и пользуйтесь пакетом bufio:

var scanner *bufio.Scanner = bufio.NewScanner(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)

func ReadInt32() int {
    scanner.Scan()
    ans, _ := strconv.Atoi(scanner.Text())
    return ans
}

func PrintInts(ints ...int) {
    for _, value := range ints {
        writer.WriteString(strconv.Itoa(value))
        writer.WriteByte(' ')
    }
}

func main() {
    defer writer.Flush() // очищает буфер при выходе из функции main
    scanner.Split(bufio.ScanWords) // заставляет scanner считать отдельными токенами слова, разделенные пробелами
                                   // также имеются функции bufio.ScanLines и bufio.ScanBytes
    var n, m int = ReadInt32(), ReadInt32()
    PrintInts(n, m)
    writer.WriteByte('\n')
    slice := []int{1, 2, 3, 4, 5}
    PrintInts(slice...)
}

Файловый ввод-вывод:

func main() {
    fi, _ := os.Open("input.txt") // открывает файл для чтения
    fo, _ := os.Create("output.txt") // открывает файл для записи
    scanner := bufio.NewScanner(fi)
    writer := bufio.NewWriter(fo)
    defer fi.Close() // закрывает файл при выходе из функции main
    defer fo.Close()
    defer writer.Flush()
    scanner.Scan() // считывает следующий токен
    writer.WriteString(scanner.Text()) // пишет текущий токен в вывод
}

Обратите внимание: отложенные (помеченные ключевым словом defer) функции выполняются в порядке "снизу вверх" (LIFO). Это значит, что в случае их написания в таком порядке

defer writer.Flush()
defer fi.Close()
defer fo.Close()

файл будет закрыт ДО очищения буфера, и в него ничего не запишется. Кроме того, отложенные функции не будут вызваны, если работа программы будет завершена вызовом функции os.Exit(0).

Также стоит отметить, что у структуры (в Go нет такого понятия как класс) Scanner есть ограничение на максимальный размер токена 65535 символов. Если вы хотите использовать ее для чтения более длинных строк, то единственный выход — это скопировать ее исходный код в шаблон решения, увеличив значение константы MaxScanTokenSize.

Сортировка и двоичный поиск

Соответствующие функции содержатся в пакете sort. В пакете есть функции, позволяющие сортировать по возрастанию слайсы из типов int, float64 и string. Если вам понадобится отсортировать что-то другое, то придется обернуть это что-то в структуру, реализующую методы Len, Less и Swap, и вызвать функцию sort.Sort:

type Int64Slice []int64
func (slice Int64Slice) Len() int           { return len(slice) }
func (slice Int64Slice) Less(i, j int) bool { return slice[i] < slice[j] }
func (slice Int64Slice) Swap(i, j int)      { slice[i], slice[j] = slice[j], slice[i] }

func main() {
    slice := []int64{5, 3, 4, 2, 1}
    sort.Sort(Int64Slice(slice))
    // slice == [1, 2, 3, 4, 5]
}

Для двоичного поиска используется функция Search(n int, f func(j int) bool) int, возвращающая наименьшее j из диапазона [0..n] такое, что f(j) == true. Пример можете посмотреть в одном из моих сабмитов

Прочие пакеты

Полное описание пакетов стандартной библиотеки приведено на офсайте

Пакеты, которые вам, скорее всего, понадобятся:

  • os — доступ к файлам и потокам, в т.ч. stdin/stderr/stdout; функция os.Exit(0)
  • bufio — буферизованный ввод-вывод;
  • sort — сортировка и двоичный поиск;
  • math — математические функции, длинная арифметика, ГСЧ, комплексные числа;
  • strings, strconv — работа со строками;
  • time — работа с датой и временем;
  • index/suffixarray — поиск всех вхождений строки в текст за время ;
  • container/heap — двоичная куча. Работает очень медленно из-за использования interface{}, однако с недавних пор ничего не мешает скопипастить код оттуда и заменить interface{} на int или что-то еще
 
 
 
 
  • Vote: I like it  
  • +28
  • Vote: I do not like it