Dart data structures efficiency

user_16314136 0
Viewed 72

I have noticed that some Dart data structures implement EfficientLengthIterable like List and Set but Iterable is not implementing it, so I have measured the taken time to calculate the length of List, Set and Iterable that containing 10000000 elements and the results was little strange for me.

Code:

void main() {
  listChecker();
  iterableChecker();
  setChecker();
}

var list = List.generate(10000000, (index) => '${index} + a');

var iterable = Iterable.generate(10000000, (index) => '${index} + a');

var setCollection = Set.from(iterable);

void listChecker() {
  final stopwatch = Stopwatch()..start();
  print(list.length);
  print('${stopwatch.elapsed} List execution Time');
}

void iterableChecker() {
  final stopwatch = Stopwatch()..start();
  print(iterable.length);
  print('${stopwatch.elapsed} Iterable execution Time');
}

void setChecker() {
  final stopwatch = Stopwatch()..start();
  print(setCollection.length);
  print('${stopwatch.elapsed} Set execution Time');
}

Results (each one in a separated execution):

  • List

10000000

0:00:01.402543 List execution Time

  • Iterable

10000000

0:00:00.001933 Iterable execution Time

  • Set

10000000

0:00:06.180889 Set execution Time

It seems like the fastest one was the Iterable but the dart documentation says that about the length property of the Iterable class:

/// Returns the number of elements in [this].

///

/// Counting all elements may involve iterating through all elements and can

/// therefore be slow.

/// Some iterables have a more efficient way to find the number of elements.

So what is meant by efficiency when implementing EfficientLengthIterable? I know that not iterating over each element should be more efficient but how is this reflected to the usage of these data structures? is it means space complexity? what are the cases I should use a List over Iterable in terms of efficiency as it seems that Iterable is too much faster regarding the time.

dart
1 Answers

From the Dart Language Tour:

Top-level and class variables are lazily initialized; the initialization code runs the first time the variable is used.

Since you've declared each Iterable as a top-level variable, they aren't initialized until they are actually used; which means that you are implicitly generating them within your benchmarks. The Set is the one that takes the longest to construct, and that's why the benchmark for Set is taking so long.

Try this instead, and you should find the results are more what you would expect:

void main() {
  var list = List.generate(10000000, (index) => '${index} + a');

  var iterable = Iterable.generate(10000000, (index) => '${index} + a');

  var set = Set.from(iterable);
  
  listChecker(list);
  iterableChecker(iterable);
  setChecker(set);
}



void listChecker(List list) {
  final stopwatch = Stopwatch()..start();
  print(list.length);
  print('${stopwatch.elapsed} List execution Time');
}

void iterableChecker(Iterable iterable) {
  final stopwatch = Stopwatch()..start();
  print(iterable.length);
  print('${stopwatch.elapsed} Iterable execution Time');
}

void setChecker(Set set) {
  final stopwatch = Stopwatch()..start();
  print(set.length);
  print('${stopwatch.elapsed} Set execution Time');
}

However, also note that Iterable.generate probably still creates a list under the hood, and therefore it will probably be equally as efficient in its length calculation, it's just that an object which conforms to Iterable won't necessarily conform to EfficientLengthIterable.

user_81742230
Related