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

Question

[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]

.

Этот код является частью алгоритма генерации размещений с повторениями. Может есть реализация куда быстрее полного перебора?

Answer 1

[Alexandroppolus]

Там от "цикла в цикле" - одно название. Средняя длина вложенного цикла равна l/(l-1), а вовсе не k. То есть каждое новое размещение делается из предыдущего за амортизированное O(1)

Answer 2

[Wataru]

Никак не ускорить. Во-первых, если вы со сгенерированными размещениями что-то делаете (хотя бы выводите), то сам код генерации уже не медленнее этого. Быстрее может быть только считать что вам там надо умно без генерации вообще.

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