Uniform Stride Timestep Subsequence
Problem Statement
Fast samplers run on a sparse subset of the T training timesteps. Build the uniformly strided DDIM subsequence used by most implementations.
Background
To take S sampling steps out of T training steps, use a constant stride c = T // S and pick timesteps 0, c, 2c, ..., (S-1)c, then reverse them so sampling runs from high noise to low:
seq=[(S−1)c,(S−2)c,…,c,0]
This is the "uniform" spacing from the DDIM paper (as opposed to "quadratic").
Your Task
Implement:
def ddim_timesteps(T, S):
Return the descending list of S timesteps.
Input Format
- T (int): number of training steps.
- S (int): number of sampling steps, 1 <= S <= T.
Output Format
- A list of S ints, descending.
Sample
print(ddim_timesteps(1000, 5))
Output:
[800, 600, 400, 200, 0]
Example:
print(ddim_timesteps(1000, 5))
[800, 600, 400, 200, 0]
- Calculate the uniform stride c by performing integer division of the total training steps T by the sampling steps S: c=1000//5=200.
- Generate the ascending sequence of timesteps by multiplying the stride c by indices from 0 to S−1: [0⋅200,1⋅200,2⋅200,3⋅200,4⋅200]=[0,200,400,600,800].
- Reverse the ascending sequence to create the descending order required for sampling from high noise to low noise: [800,600,400,200,0].
- The final output is [800, 600, 400, 200, 0]
Constraints:
1 <= S <= T <= 1000000.- Stride
c = T // S; timesteps are0, c, ..., (S-1)c, then reversed. - Return exactly
Sdescending ints.
1. Background Knowledge
In DDPM (Denoising Diffusion Probabilistic Models), a model is trained to reverse a gradual noising process across T discrete timesteps. Sampling from the trained model by stepping through all T timesteps is computationally expensive. DDIM (Denoising Diffusion Implicit Models) introduced a deterministic, accelerated sampling scheme that allows the model to take only S steps, where S≪T, while still producing high-quality samples.
The choice of which timesteps to visit is critical. The most common strategy is uniform striding: divide the total range [0,T) into S equally spaced intervals. The stride (or step size) is computed as c=T//S. The selected timesteps are then 0,c,2c,…,(S−1)c. Because diffusion sampling proceeds from high noise to low noise, the sequence must be reversed so that the largest timestep comes first. This uniform schedule is simpler and often sufficient compared to more complex schedules like quadratic spacing, which concentrate more steps near the high-noise end.
Understanding this problem requires familiarity with integer division in Python (//), which performs floor division. For example, 1000//5=200, but 1000//3=333 (the remainder is discarded). This means the last selected timestep (S−1)⋅c may not exactly equal T−c or T; it will be the largest multiple of c that is strictly less than T.
2. Algorithm Approach
This is a straightforward arithmetic sequence generation problem. The core pattern is:
- Compute the stride c=T//S.
- Generate the ascending sequence [0,c,2c,…,(S−1)c] using a range or list comprehension.
- Reverse the sequence to get the descending order required for DDIM sampling.
No complex data structures or iterative refinement are needed. The entire solution is a one-liner or a few lines of Python that leverage range() and slicing or reversed().
3. Step-by-Step Strategy
- Step 1: Compute the stride. Calculate c = T // S. This gives the spacing between consecutive selected timesteps.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.