Открыть список
Как стать автором
Обновить

Комментарии 14

Первая задача, утверждение «А можно выделить дополнительную память и решить за линейное время.» некорректно.

Описанное решение работает не за линейное, а за N*log(N)*M время. (составление словаря — это N*log(N))
(составление словаря — это N*log(N)

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

Даже если иметь в виду взвешенное бинарное дерево, то там сложность log(N). Откуда еще N не понятно.
Потому что вставить нужно не один раз а N, по количеству элементов.
Упс. Имелась в виду операция вставки конечно.

Бинарное дерево за логарифм никак не строится, хотя бы потому что ему нужна память Θ(N).

Согласен, позабыл, что в удачном случае вставка в хешмап — O(1). (Но так же стоит не забывать, что в неудачном — O(N))

Логарифму все равно взяться неоткуда. А когда вы вставляете множество, да еще и с заранее известным размером, вы как раз должны попадать в амортизированную оценку.

Все верно. Логарифма нет, есть константа или линейная в зависимости от того на сколько нам повезло. Чаще всего везет и сложность O(1)
В задаче "Слить N каналов в один" sync.WaitGroup не обязательно передавать как аргумент:
func joinChannels(chs ...<-chan int) <-chan int {
	mergedCh := make(chan int)

	go func() {
		wg := &sync.WaitGroup{}

		wg.Add(len(chs))

		for _, ch := range chs {
			go func(ch <-chan int) {
				defer wg.Done()
				for id := range ch {
					mergedCh <- id
				}
			}(ch)
		}
		wg.Wait()
		close(mergedCh)
	}()
	return mergedCh
}

Не стоит забывать о нулевых значениях в Go.


Вот этот код


if _, ok := counter[elem]; !ok {
    counter[elem] = 1
} else {
    counter[elem] += 1
}

можно записать как


counter[elem]++
> Создаем канал, куда будем сливать все данные. Он будет небуферезированный, потому что мы не знаем, сколько данных придет из каналов.

Буфер нужен для того, чтобы уменьшить количество переключений между горутинами и позволить им работать параллельно. Вовсе не обязательно делать буфер достаточно большим, чтобы вместить все данные.
Вот последняя часть статьи и раскрывает в чем серьезный недостаток Go. Да, писать на нем легко и просто. Фан и всё такое. Отдых для уставших от бесконечных Java классов и логов. Но выбирать его как основной язык разработки — это большой риск. Потому что если проект разрастется (а это происходит почти всегда, в случае успеха) — без тех самых «надоедливых» фич из Java, C++, C# и прочих, становится очень неудобно и просто опасно. Не всё и не всегда можно разбить на мелкие микросервисы чисто с технической стороны, да и не всегда есть бюджеты и время чтобы это сделать.
Задачу «написать генератор случайных чисел» я представлял иначе.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.