34 заметки с тегом

googlego

Как быстрее измерить длину строки в Go?

Интересная штука, с которой сталкиваются начинающие разработчики в Гоу — как измерить длину строки в этом языке. То есть речь не идёт даже о быстроте, как, чёрт возьми, вообще это сделать?

Встроенная функция len возвращает длину в байтах, именно поэтому англоязычные разработчики часто и не знают, что проблема есть — строки латиницы, что в байтах, что в символах (в Гоу они называются «руны») занимают одинаково.

Я знаю два способа измерить длину строки:

package main

import ("io/ioutil"; "unicode/utf8")

func main() {
    bytes, _ := ioutil.ReadFile("test.txt")

    // считаем сколько рун встречается в строке
    print(utf8.RuneCountInString(string(bytes)))

    print("\n")

    // считаем длину массива рун
    print(len([]rune(string(bytes))))
}

По работе понадобилось измерить длину строки быстро — у меня здоровый цикл, где она постоянно измеряется, оказалось, что в тысяче итераций на тексте книги «На всех пара́х» Терри Пратчетта разница в две секунды — выигрывает преобразование в массив «рун».

Нужен быстрый способ — используйте len([]rune(…)).

Go и Oracle

На работе произошло кое-что необычное: вдруг пригодились знания Гоу. Не то чтобы нельзя было написать требуемое на другом языке, но нужно было быстро и на чём-то компилируемом. На Си всё работало бы значительно быстрее, но писалось бы неделю или более, поэтому я написал прототип на Гоу, управившись всего за два дня. Скорость работы оказалась выше ожидаемой и теперь, как кажется, прототип уже начинает превращаться в продукт.

прототип (60.56КиБ)

Проблемы начались, когда я попытался подключиться из прототипа к СУБД «Оракл» (такое было условие задачи). Сначала я, как и  наверное многие до меня, нашёл драйвер go-oci8. Очень не рекомендую его использовать, если у вас задача чуть сложнее, чем «выбрать пару чисел из запроса».

Для начала, проблема возникла с кодировкой. У нас в базе используется кодовая таблица 1251. Сначала (тут я сам дурак) мне показалось, что драйвер не учитывает кодировку из переменных откружения (проблема оказалась в 11-й строчке примера (который идёт с драйвером), где очищалась переменная NLS_LANG), поэтому пришлось соорудить патч:

charset := C.CString(charset_dsn)
defer C.free(unsafe.Pointer(charset))

env := new(C.OCIEnv)
rv = C.OCIEnvNlsCreate(
    (**C.OCIEnv)(unsafe.Pointer(&env)),
    C.OCI_DEFAULT | C.OCI_OBJECT,
    nil, nil, nil, nil, 0, nil, 0, 0,
)
charset_id := C.OCINlsCharSetNameToId(unsafe.Pointer(env), (*C.oratext)(unsafe.Pointer(charset)))

rv = C.OCIEnvNlsCreate(
    (**C.OCIEnv)(unsafe.Pointer(&conn.env)),
    C.OCI_DEFAULT | C.OCI_OBJECT | C.OCI_THREADED | C.OCI_NO_MUTEX,
    nil, nil, nil, nil, 0, nil,
    charset_id, charset_id,
)

Этот код должен работать вместо OCIEnvInit, если нужно использовать кодировку. Но, повторюсь, это проблема не драйвера, просто этот тот случай, когда «ложечки нашлись, а осадок остался».

Потом оказалось, что в драйвере нет превыборки (prefetch), из-за чего чтение из таблицы было очень медленным. Чашу терпения же переполнило отстутствие работы с типом CLOB — при попытке получить данные этого типа размером более 4000 байт, драйвер сообщил, что нехватает буфера.

Я подумал, что постоянно решать проблемы драйвера — не мой путь и нашёл прекрасный Goracle, чуть более сложный, но обладающий всеми мыслимыми возможностями, порт с пайтонячего драйвера, написанного на Си.

Единственная неприятность — драйвер все строки возвращает в кодировке UTF-8, т. е. они конвертируются из любой другой автоматически. Мне их приходится конвертировать обратно, но скорость чтения настолько велика (на порядок быстрее ПХП), что меня это пока не волнует.

2014   googlego   oracle

Скачивалка с самарского архива

Несколько читателей сообщили, что моя скачивалка архивов ЭлАра не работает — самарский архив что-то у себя изменил и она перестала работать.

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

Чтобы вытащить из страницы список картинок, которые нужно качать, можно воспользоваться следующим способом: открываем консоль браузера и пишем туда следующее:

console.log("dxo.itemsValue=['"+
window['MainPlaceHolder__storageViewerControl__storageFilesViewerControl_FilesDropDownList_DDD_L'].
itemsValue.join("','")+"'];")

Вывод нужно скопировать в файл и натравить на него скачиватель. Параметры остались неизменными.

Скачивалка документов из архивов ЭлАра (теперь можно указать страницы)

Программа для скачивания документов из архивов ЭлАра (инструкция есть у меня в блоге) неожиданно оказалась одной из самых популярных из того, что я делал.

Новые ключи программы (84.10КиБ)

Мне постоянно пишут благодарственные письма, а иногда — свои пожелания. Самое частое — сделать указание диапазона страниц для скачивания. Сегодня я эту возможность добавил, программа лежит на том же месте.

2013   googlego   родовое дерево

Скачивалка документов из архивов ЭлАра

Написала мне одна читательница по поводу моей утилиты для скачивания документов из электронных архивов ЭлАра. Оказывается, помимо самарского, моя утилита вполне нормально работает и с тобольским. Что ж, наверняка есть ещё архивы с которыми она совместима, поэтому в новую версию я добавил необязательный параметр host, который позволяет указать другой адрес (по-умолчанию используется самарский):

Тобольский архив (8.71КиБ)

Утилита лежит там же — на «ГитХабе».

2013   googlego   родовое дерево

Как скачать документ из АИС ЦГАСО

АИС ЦГАСО (104.73КиБ)

Изучаю тут самарский электронный архив, который сделан в «Эларе». Насколько я понял, продукт называется АИС ЦГАСО. Убиваю сразу двух зайцев — разбираюсь как всё работает и пытаюсь найти нужные мне документы по родственникам.

Ребята из «Элара» молодцы, делают очень нужное дело — оцифровывают бумажные архивы, это невероятный труд, но, к сожалению, интерфейс просмотра документов оставляет желать лучшего, он мне сжёг массу нервов. Решил просто выкачать нужные мне документы на компьютер и дело с концом. Написал специальную программу для скачивания документов из АИС ЦГАСО, на Гугл Гоу. Получилось довольно компактно.

Основная фишка — паралельное скачивание документов в несколько потоков. Не уверен, что это действительно работает (я не до конца понимаю как Гоу переключает свои горутины), но в теории должно. Добавлено: «полевые испытания» подтвердили, что документы действительно скачиваются параллельно. Удалось сделать крайне просто:

ch := make(chan byte, N)

for i, id := range documents {
    ch <- 1

    go func(id string, index int) {
        name := padZero5(strconv.Itoa(index)) + ".jpg"
        copyUrlToFile(strings.Replace(url, `%id`, id, 1), *dir + "/" + name)

        <-ch
    }(id, i)
}

Первой строкой в коде создаётся канал заданной размерности. С ним будут работать горутины (это такие легковесные потоки Гоу). В него можно положить только N значений, после чего следующая операция записи будет ждать его освобождения. С помещением в канал каждого нового значения, запускается горутина для скачивания одного листа документа, как только горутина отработала, она убирает из канала одно значение и цикл основного потока снова его кладёт и запускает новую горутину.

В итоге, одновременно, не будет запущено более N горутин.

Пользоваться программой просто (если кому-нибудь кроме меня это надо) — нужно в браузере (я в «Хроме» пробовал, выбирать при сохранении надо формат «веб-страница полностью») перейти на чтение документа (на снимке экрана иконка книжки рядом с каждым документом), когда загрузится первая страница документа, сохранить текущий документ браузера на диск (Ctrl+S в Винде, ⌘+S на «Маке») и скормить его программе в командной строке:

go run cgodownloader.go скачанный-файл.html

Программа обработает документ, покажет сколько страниц найдено и начнёт их скачивать в виде больших джпегов в ту же папку, показывая их имена. У меня на большом документе (около 1,5 тысяч страниц) заняло прилично времени — час с лишним.

Запуск программы (6.56КиБ)

Зато теперь просматривать удобно.

30 банковских дней-2

Жена попросила во вчерашнюю программу ряд улучшений внести и пожаловалась, что она на одном из компьютеров на работе запускается медленно. Ну, я решил переписать её на Гоу, раз такое дело, может быстрее стартовать будет. Кроме того, мне всегда интересно посмотреть как одна и та же программа выглядит на разных языках программирования.

package main

import (
    "encoding/json"
    "os"
    s "strconv"
    t "time"
    "net/http"
    "io/ioutil"
    "fmt"
    r "regexp"
    "bufio"
    "strings"
    fp "path/filepath"
)

type date struct {
    D byte
    M byte
    Y int
}

func CreateDate(d, m string, y int) date {
    day, _   := s.Atoi(d)
    month, _ := s.Atoi(m)

    return date{D:byte(day), M:byte(month), Y:y}
}

func (d date) FindIn(list []date) bool {
    for _, cur := range list {
        if d.D == cur.D && d.M == cur.M && (d.Y == cur.Y || cur.Y == 0) {
            return true
        }
    } 

    return false
}

func (d date) ToTime() t.Time {
    return t.Date(d.Y, t.Month(d.M), int(d.D), 0, 0, 0, 0, t.UTC)
}

func (d date) IsWeekEnd() bool {
    dw := string(d.ToTime().Weekday())

    return dw == "Saturday" || dw == "Sunday"
}


func (d date) Add(delta string) date {
    dur, _ := t.ParseDuration(delta)
    t := d.ToTime().Add(dur)

    return date{D:byte(t.Day()), M:byte(t.Month()), Y:t.Year()}
}

func (d date) String() string {
    return fmt.Sprintf("%02d.%02d.%04d", d.D, d.M, d.Y)
}

func loadCache(name string) (holidays []date) {
    f, err := os.OpenFile(name, os.O_RDONLY, 0666)

    if err != nil {
        return nil
    }

    defer f.Close()

    if err := json.NewDecoder(f).Decode(&holidays); err != nil {
        return nil
    }

    return
}

func saveCache(name string, holidays []date) bool {
    f, err := os.OpenFile(name, os.O_WRONLY|os.O_TRUNC|os.O_CREATE, 0666)

    if err != nil {
        return false
    }

    defer f.Close()

    if err := json.NewEncoder(f).Encode(&holidays); err != nil {
        return false
    }

    return true
}

func getCurrentCalend() []byte {
    if resp, err := http.Get("http://www.calend.ru/work/"); err == nil {
        defer resp.Body.Close()

        if body, err := ioutil.ReadAll(resp.Body); err == nil {
            return body
        }
    }

    return nil
}

func getCurrentHolidays() (dates []date) {
    table, _ := r.Compile(`(?s)<table\s.+?time_of_death(.+)</table>`)
    chunk, _ := r.Compile(`(?s)<td\s+class="\S+\s+col5"\s+day="(\d+)"\s+month="(\d+)"`)

    dates = []date{}

    year := t.Now().Year()

    for _, value := range chunk.FindAllStringSubmatch(string(table.Find(getCurrentCalend())), -1) {
        dates = append(dates, CreateDate(value[1], value[2], year))
    }

    return
}

func ReadUserInput(message string) string {
    fmt.Print(message)

    input, _ := bufio.NewReader(os.Stdin).ReadString('\n')
    return input
}

func main() {
    var currentholidays []date

    year := t.Now().Year()
    cachename := s.Itoa(year) + ".json"

    // если кеш существует
    if _, e := os.Stat(cachename); e == nil {
        currentholidays = loadCache(cachename)
    } else {
        currentholidays = getCurrentHolidays()
        saveCache(cachename, currentholidays)
    }

    // загружаем другие кеши
    caches, _ := fp.Glob("*.json")
    for _, name := range caches {
        if name != cachename {
            currentholidays = append(currentholidays, loadCache(name)...)
        }
    }

    // опрашиваем пользователя
    mask, _  := r.Compile(`^(?m)(\d+)\D+(\d+)`)

    for {
        var userdate date

        for {
            d := mask.FindStringSubmatch(ReadUserInput("Enter date (dd.mm): "))
            if len(d) > 0 {
                userdate = CreateDate(d[1], d[2], year)
                break
            }
        }

        var period int

        for {
            period, _ = s.Atoi(strings.TrimRight(ReadUserInput("Enter period: "), "\r\n"))

            if period > 0 {
                break
            }
        }

        for ; period > 0; period-- {
            for {
                userdate = userdate.Add("24h")

                if !userdate.FindIn(currentholidays) && !userdate.IsWeekEnd() {
                    break
                }
            }
        }


        fmt.Printf("Result: %s\n\n", userdate)
    }
}

Меня поразил размер скомпилированной программы. Вот эта мелочь под «Маком» занимает 3,9Мб, под «Виндой» — 3,7! Жена попросила убрать гуишное окошко, поэтому я сделал программу полностью консольной. Два разочарования: в регулярных выражениях под Виндой неверно определяется конец строки (не учитывается «\r», судя по всему) и второе — в Гоу нет ничего, чтобы работать с однобайтными кодировками, а в консоли Винды до сих пор CP866. Пришлось выводить всё по-английски, писать конвертирующую функцию мне лень.

Объём увеличился, во-первых, из-за улучшений, во-вторых, мне хотелось хранить файлы кешей в каком-нибудь более-менее читаемом формате, чтобы вручную добавить в кеш татарстанские праздники, так что часть объёма (класс «date и методы работы с ним) как раз для этого.

&^ в Google Go

Отличная иллюстрация того как важны мелочи в документации…

Читал чужой исходный код на «Гоу» и обнаружил необычную конструкцию:

v &^= 1 >> n

Почесал голову, не понял что это и пошёл читать документацию. Выяснилось, что эту конструкцию я когда-то упустил при чтении документации и означает она «bit clear (and not)», то есть является противополжностью „|=“, не ставит бит, а очищает его. Более того, есть ещё унарная операция «^», которая инвертирует все биты в числе (соблюдая размер его типа), вот как они работают:

package main

func main() {
    var test byte = 250

    println(test) // 250 (11111010)
    
    test = ^test
    println(test) // 5 (00000101)

    test &^= 4   //    (00000100)
    println(test) // 1 (00000001)
}

Алгоритм линейного счётчика на Google Go (golang)

Не смог отказать себе в удовольствии и попрактиковаться в «Гоу», написал и выложил на Гитхаб реализацию алгоритма линейного счётчика на Гугл Гоу. Значения, которые надо подсчитать поступают на стандартный вход, есть один параметр командной строки — «size», позволяющий задать размер вектора в битах (по-умолчанию — 10000).

Подсчёт 1 000 000 значений (8.81КиБ)

Подсчёт на моём ноуте одного миллиона уникальных значений занимает примерно 6,5 секунд. Погрешность с вектором длиной 100 тысяч бит (≈3КиБ) — 7,6%.

Чтобы скомпилировать программу новым (версии 1 и выше) компилятором «Гоу», нужно запустить следующую команду:

go build linear-counter.go

Разворот односвязного списка за O(n) (память — O(1)) на Гугл Гоу

Вчера друг подвозил меня до дома, я решил, пока в пробке, попрограмировать на «Гоу». Практики давненько не было, язык уже начинает забываться, не модули, это ерунда, а сами конструкции, вот что неприятно.

Взял задачу — развернуть односвязный список за O(n) с константным ограничением на память. Задачу частенько дают на собеседованиях, как я слышал, говорят мало кто решает, решил посмотреть действительно ли это сложно. В уме прикинул, подумалось что нет, практика показала, что я не ошибся. В общем, выкладываю что получилось.

package main

import (
    "os"
    "bufio"
)

// тип для односвязного списка
type links struct {
    Next *links
    Value string
}

// вывод на печать односвязаного списка
func (chain *links) Print() {
    for chain != nil {
        os.Stdout.WriteString(chain.Value)

        chain = chain.Next
    }
}

// разворачиваем односвязный список за O(n)
func (chain *links) Reverse() *links {
    if chain == nil || chain.Next == nil {
        return chain
    }

    left, next := chain, chain.Next.Next
    chain = chain.Next
    left.Next = nil

    for {
        chain.Next = left

        if next == nil {
            break
        }

        left, chain, next = chain, next, next.Next
    }

    return chain
}

// Создаём список из чего-нибудь, умеющего выдавать по одной строке за раз
func CreateFromReader(readline func() *string) *links {
    var chain, start *links = nil, nil

    for {
        if line := readline(); line != nil {
            link := &links{ nil, *line }

            if chain == nil {
                chain, start = link, link
            } else {
                chain.Next, chain = link, link
            }

        } else {
            return start
        }
    }

    return nil
}

// Точка входа
func main() {
    if len(os.Args) < 2 {
        os.Exit(1)
    }

    f, err := os.OpenFile(os.Args[1], os.O_RDONLY, 0666)

    if err != nil {
        os.Exit(2)
    }

    defer f.Close()

    r := bufio.NewReader(f)

    CreateFromReader(
        func() (*string) {
            if line, e := r.ReadString('\n'); e == nil {
                return &line
            }

            return nil
        },
    ).Reverse().Print()
}

Список создаётся из файла, который нужно передать программе первым параметром. Вообще, вся реализация разворота — в методе Reverse класса links, остальное — заполнение структуры и вывод на печать. Оцените как мало надо кода, чтобы решить это задание.

2012   googlego
Ранее Ctrl + ↓