Подтвердить что ты не робот

Есть ли аналог memset в go?

В С++ я могу инициализировать массив с некоторым значением, используя memset:

const int MAX = 1000000;
int is_prime[MAX]

memset(is_prime, 1, sizeof(is_prime))

Что делает memset, грубо можно описать как заполнение массива некоторым значением, но это действительно очень быстро.

В go я могу сделать is_prime := make([]int, 1000000), но это создаст срез со всеми 0, аналогичным образом я могу использовать new([1000000]int), но ничто не позволит мне создать массив/срез со всеми 1 или любым другим ненулевой элемент.

Конечно, я могу использовать цикл, чтобы заполнить его значением позже, но главная цель memset заключается в том, что он намного быстрее, чем цикл.

Итак, программисты Go имеют аналог memset (быстрый способ инициализации массива для некоторого ненулевого значения)?

4b9b3361

ОТВЕТЫ

Ответ 1

Простейшее решение с циклом будет выглядеть так:

func memsetLoop(a []int, v int) {
    for i := range a {
        a[i] = v
    }
}

В стандартной библиотеке нет поддержки memset, но мы можем использовать встроенный copy(), который сильно оптимизирован.

С повторением copy()

Мы можем установить первый элемент вручную и начать копирование уже установленной части в неустановленную часть с помощью copy(); где уже заданная часть становится все больше и больше каждый раз (удваивается), поэтому количество итераций log(n):

func memsetRepeat(a []int, v int) {
    if len(a) == 0 {
        return
    }
    a[0] = v
    for bp := 1; bp < len(a); bp *= 2 {
        copy(a[bp:], a[:bp])
    }
}

Это решение было вдохновлено внедрением bytes.Repeat(). Если вы просто хотите создать новый []byte, заполненный теми же значениями, вы можете использовать функцию bytes.Repeat(). Вы не можете использовать это для существующего среза или срезов, кроме []byte, для этого вы можете использовать представленный memsetRepeat().

В случае небольших фрагментов memsetRepeat() может быть медленнее, чем memsetLoop() (но в случае небольших фрагментов это не имеет большого значения, оно будет выполняться в одно мгновение).

Из-за использования быстрого copy(), memsetRepeat() будет намного быстрее, если число элементов растет.

Сравнивая эти 2 решения:

var a = make([]int, 1000) // Size will vary

func BenchmarkLoop(b *testing.B) {
    for i := 0; i < b.N; i++ {
        memsetLoop(a, 10)
    }
}

func BenchmarkRepeat(b *testing.B) {
    for i := 0; i < b.N; i++ {
        memsetRepeat(a, 11)
    }
}

Результаты тестов

100 элементов: ~ 1,15 раза быстрее

BenchmarkLoop   20000000                81.6 ns/op
BenchmarkRepeat 20000000                71.0 ns/op

1,000 элементов: ~ 2,5 раза быстрее

BenchmarkLoop    2000000               706 ns/op
BenchmarkRepeat  5000000               279 ns/op

10 000 элементов: ~ 2 раза быстрее

BenchmarkLoop     200000              7029 ns/op
BenchmarkRepeat   500000              3544 ns/op

100 000 элементов: ~ в 1,5 раза быстрее

BenchmarkLoop      20000             70671 ns/op
BenchmarkRepeat    30000             45213 ns/op

Наибольшее усиление производительности составляет около 3800-4000 элементов, где ~ 3,2 раза быстрее.

Ответ 2

В соответствии с этой ошибкой под названием "оптимизировать идиому memset" нет способа сделать это в Go, кроме как с циклом. Вопрос был закрыт 9 января 2013 года с этой записью

Я считаю это фиксированным. Оптимизация ненулевых случаев не очень интересно.

Мы можем открыть еще один баг, если люди будут чувствовать себя уверенно в том, чтобы делать больше.

Итак, решение состоит в том, чтобы использовать цикл, который уже был рассмотрен icza.

Существует bytes.Repeat, но также используется цикл:

func Repeat(b []byte, count int) []byte {
    nb := make([]byte, len(b)*count)
    bp := copy(nb, b)
    for bp < len(nb) {
        copy(nb[bp:], nb[:bp])
        bp *= 2
    }
    return nb
}