Introduction
Have you ever needed to loop through a list, but the operation took a significant amount of time to complete? Have you ever had a program crash because an operation used too much memory? This happened to me when I tried to implement a function that generates prime numbers.
Generating prime numbers up to a million took far more time than I would have liked. But generating numbers up to 10 million was impossible. My program would crash or just hang. I was already using the sieve of Eratosthenes, which is supposed to be more efficient at generating primes than the brute force approach.
If you find yourself in a similar situation, you can try using a different algorithm. There are searching and sorting algorithms that work better on larger inputs. The downside is those algorithms may be more difficult to grasp right away. Another option is to use a different programming language.
A compiled language may be able to process the code significantly quicker. But using another language may not be practical. You may also try using multiple threads. Once again, it may not be practical because your programming language would have to support this.
Fortunately, with JavaScript, there is another option. If you have a computationally intensive task, you can use iterators and generators to gain some efficiency. Iterators are a property of certain JavaScript collections.
Iterators improve efficiency by letting you consume the items in a list one at a time as if they were a stream. Generators are a special kind of function that can pause execution. Invoking a generator allows you to produce data one chunk at a time without the need to store it in a list first.
Iterators
First, let’s review the different ways you can loop through collections in JavaScript. A loop of the form for (initial; condition; step) { ... } will execute the commands in its body a specific number of times. Similarly, a while loop will execute the commands in its body for as long as its condition is true.
You can use these loops to traverse a list by incrementing an index variable at each iteration. An iteration is an execution of the body of a loop. These loops do not know about the structure of your list. They act as counters.
A for/in loop and a for/of loop are designed to iterate over specific data structures. Iterating over a data structure means you are stepping through each of its elements. A for/in loop iterates over the keys in a plain JavaScript object. A for/of loop iterates over the values of an iterable. What is an iterable? Simply put, an iterable is an object that has an iterator. Examples of iterables are arrays and sets. The iterator is a property of the object that provides a mechanism for traversing the object.
What makes an iterator special is how it traverses a collection. Other loops need to load the entire collection up front in order to iterate over it, whereas an iterator only needs to know the current position in the collection.
You access the current item by calling the iterator’s next method. The next method will return the value of the current item and a boolean to indicate when you have reached the end of the collection. The following is an example of creating an iterator from an array.
const alpha = ['a','b','c'];
const it = alpha[Symbol.iterator]();
it.next(); //{ value: 'a', done: false }
it.next(); //{ value: 'b', done: false }
it.next(); //{ value: 'c', done: false }
it.next(); //{ value: undefined, done: true }
You can also iterate over the values of the iterator using a for/of loop. Use this method when you know you want to access all of the items in the object. This is how you would use a loop to iterate through the previous list:
for (const elem of it){
console.log(elem);
}
Why would you use an iterator? Using an iterator is beneficial when the computational cost of processing a list is high. If you have a data source that is very large, it may cause problems in your program if you attempt to iterate over it because the entire collection has to be loaded.
With an iterator, you can load the data in chunks. This is more efficient because you only manipulate the part of the list that you need, without incurring the additional cost of processing the entire list.
An example could be that you have loaded data from a file or database, and you want to progressively display the information on the screen. You could create an iterator from the data and set up an event handler to grab a few items every time the event occurs. This is an example of what such an implementation might look like:
let posts = load(url);
let it = posts[Symbol.iterator]();
function loadPosts(iterable, count) {
for (let i = 0; i < count; i++) {
display(iterable.next().value);
}
}
document.getElementById('btnNext').onclick = loadPosts(it, 5);
Generators
If you want to build a collection, you can do so with a generator. A generator function can return values one at a time by pausing execution at each iteration. When you create an instance of a generator, these items can be accessed using an iterator. This is the general syntax for creating a generator function:
function *genFunc() {
...
yield value;
}
The * signifies that this is a generator function. The yield keyword pauses our function and supplies the state of the generator at that particular moment. Why would you use a generator? You would use a generator when you want to algorithmically produce a value in a collection. It is particularly useful if you have a very large or infinite collection. Let’s look at an example to understand how this helps us.
Suppose you have an online pool game you have built, and you want to match players to game rooms. Your objective is to generate all of the ways you can choose two distinct players from your list of 2,000 gamers. The two-player combinations generated from the list ['a', 'b', 'c', 'd'] would be ab, ac, ad, bc, bd, cd. This is a solution using nested loops:
function combos(list) {
const n = list.length;
let result = [];
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
result.push([list[i], list[j]]);
}
}
return result;
}
console.log(combos(['a', 'b', 'c', 'd']));
Now try executing the function with a list of 2,000 elements. (You can initialize your list using a for loop that adds the numbers 1 to 2,000 to an array). What happens now when you run your code?
When I run the code in an online editor, the web page crashes. When I try it out in the console in Chrome, I can see the output slowly printing out. However, my computer’s CPU starts to go into overdrive, and I have to force quit Chrome. This is the revised code using a generator function:
function *combos(list) {
const n = list.length;
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
yield [list[i], list[j]];
}
}
}
let it = combos(['a', 'b', 'c', 'd']);
it.next();
Another example is if we wanted to generate the numbers in the Fibonacci sequence up to infinity. Here is one implementation:
function *fibGen() {
let current = 0;
let next = 1;
while(true) {
yield current;
let nextNum = current + next;
current = next;
next = nextNum;
}
}
let it = fibGen();
it.next().value; //0
it.next().value; //1
it.next().value; //1
it.next().value; //2
Normally, an infinite loop will crash your program. The fibGen function is capable of running forever because there is no stopping condition. But since it is a generator, you control when each step is executed.
Review
Iterators and generators come in handy when you want to process a collection incrementally. You gain efficiency by keeping track of the state of the collection instead of all of the items in the collection. Items in the collection are evaluated one at a time, and the evaluation of the rest of the collection is delayed till later.
Iterators provide an efficient way to traverse and manipulate large lists. Generators provide an efficient way to build lists. You should try out these techniques when you would otherwise use a complex algorithm or implement parallel programming to optimize your code.
If you’re looking for additional resources to study or to use in your work, check out what we have available in the Envato Market.
Resources
- Design Patterns: Elements of Reusable Object-Oriented Software: Iterator pattern
- ECMAScript Specification for Iterators and Generators
- Structure and Interpretation of Computer Programs - Chapter 3.5: Streams
Powered by WPeMatico
