@kr_ilya

Как ускорить код?

Необходимо ускорить код. Цикл в цикле это медленно. Думаю можно как-то записать тоже самое без вложенного цикла.

package main

import "log"

func main()  {
	t := 0
	k := 2
	l := 4
	s := 16

	idx := make([]int, k)
	for t < s {

		log.Println(idx)
		
		for j := k-1; j >= 0; j--{
			if idx[j] >= l-1 {
				idx[j] = 0
			}else{
				idx[j]++
        break
			}
		}
		t++;
	}
}


Данный код выводит:
[0 0]
[0 1]
[0 2]
[0 3]
[1 0]
[1 1]
[1 2]
[1 3]
[2 0]
[2 1]
[2 2]
[2 3]
[3 0]
[3 1]
[3 2]
[3 3]
.

Этот код является частью алгоритма генерации размещений с повторениями. Может есть реализация куда быстрее полного перебора?
  • Вопрос задан
  • 285 просмотров
Решения вопроса 2
Alexandroppolus
@Alexandroppolus
кодир
Там от "цикла в цикле" - одно название. Средняя длина вложенного цикла равна l/(l-1), а вовсе не k. То есть каждое новое размещение делается из предыдущего за амортизированное O(1)
Ответ написан
Комментировать
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Никак не ускорить. Во-первых, если вы со сгенерированными размещениями что-то делаете (хотя бы выводите), то сам код генерации уже не медленнее этого. Быстрее может быть только считать что вам там надо умно без генерации вообще.

Во-вторых, как вам уже сказали - амортизационно это все будет O(s). Потому что внутренний цикл делает "лишних" операций суммарно столько, сколько l-1 на конце всех размещений. Их 0 в l^(n-1)*(l-1) размещениях, 1 в l^(n-2)*(l-1), и т.д. если все это просуммировать, то результат будет меньше l^n - количества итераций внешнего цикла.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы