Dart Stride Iterators

Introduction

In the context of numerical computation, data is often represented as multi-dimensional arrays. In Dart, a multi-dimensional array can be represented as a list of lists. To speed up arithmetical operations and minimize memory usage it can be advantageous to flatten multi-dimensional arrays (see Numerical computation).

The example below shows the elements of a 2-dimensional array stored as a 1-dimensional array (a Dart list) using a row major layout.

In order to access the elements of the column with index 1 (highlighted using an orange rectangle) one would need to start the iteration at index 1 and then use a step size of 3 (the number of columns in the 2D-array) to move to the next element.

The package stride provides stride iterators and extension methods on List and Iterable that can accomplish precisely the task described above.

Usage

To use this package include stride as a dependency in your pubspec.yaml file. The program below demonstrates how to use the extension method stride to iterate lists using a custom step size and start index. Note that the iteration step size must not be zero. A negative step size and suitable start index may be used to iterate in reverse direction.

Tip: When iterating fixed size lists and especially typed lists it makes perfect sense to disable concurrent modification checks. The slight performance improvement is evident when iterating very long lists.

import 'dart:typed_data';

import 'package:stride/stride.dart';

main(List<String> args) {
  // 3x3 matrix.
  final array2D = <List<String>>[
    ['e00', 'e01', 'e02'],
    ['e10', 'e11', 'e12'],
    ['e20', 'e21', 'e22'],
  ];

  /// Elements of 3x3 matrix in row major layout.
  final list = ['e00', 'e01', 'e02', 'e10', 'e11', 'e12', 'e20', 'e21', 'e22'];

  final stepSize = 3;
  final startIndex = 1;
  final strideIt0 = list.stride(stepSize, startIndex);

  print('2D array:');
  print(array2D[0]);
  print(array2D[1]);
  print(array2D[2]);
  print('');

  print('Column 1:');
  print(strideIt0);
  print('');

  // Typed list (with fixed length).
  final numericalList =
      Float64List.fromList([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

  final strideIt1 = numericalList.stride(
    stepSize,
    startIndex,
    false,   // <-----------    Disabling concurrent modification checks.
  );

  print('Numerical list:');
  print(numericalList);
  print('');

  print('start index: 1 and step-size: 3:');
  print(strideIt1);
  print('');

  print('start index: 9 and step-size: -3:');
  final reverseStrideIt1 = numericalList.stride(-3, 9, false);
  print(reverseStrideIt1);
}

Running the program above produces the following console output:

$ dart example/bin/example.dart
2D array:
[e00, e01, e02]
[e10, e11, e12]
[e20, e21, e22]

Column 1:
(e01, e11, e21)

Numerical list:
[0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0]

start index: 1 and step-size: 3:
(1.0, 4.0, 7.0, 10.0)

start index: 9 and step-size: -3:
(9.0, 6.0, 3.0, 0.0)

Row Major and Column Major Storage Layout

Consider an N-dimensional array, array_N, with length d_i along dimension i, where i ∈ [0, n-1]. Let array_1 be a Dart list able to store all d₀ · d₁ · … · d_n-1 elements of array_N.

Let array_N[i₀][i₁]…[i_n‑1] be stored at location array_1[s₀·i₀ + … + s_n-1·i_n-1], where the iteration step sizes, s_i, depend on the storage order.

For a row major storage order the step sizes are given by:

s₀ = d₁ · d₂ ·   …   · d_n-1

s₁ = d₂ · d₃ ·   …   · d_n-1

⋮

s_n-2 = d_n-1

s_n-1 = 1.

For a column major storage order the step sizes are given by:

s₀ = 1

s₁ = d₀

s₂ = d₀ · d₁

⋮

s_n-2 = d₀ · d₁ ·   …   · d_n-3

s_n-1 = d₀ · d₁ ·   …   · d_n-2

For more information see Row- and column-major order.

Examples

A copy of the program shown in the section above can be found in the folder example.

Features and bugs

Please file feature requests and bugs at the issue tracker.