Linear Scan

tags: linear-scan one-loop one-dimensional-array map filter reduce forward-iteration reverse-iteration array-traversal

A sequence is an ordered collection of values where each value is identified by an integer index.

An array with sequence of elements can be scanned left to right. This is forward iteration:

1
2
3
4
5
6
7
8
9

def scan(a)
  n = a.size

  for i in (0..n-1)
    p a[i]
  end
end

p scan([4,3,2,9,2,0])

Every item in the array is examined by using a for loop with index to access the elements in the array. This is array traversal.

The reverse iteration scans the array from right to left:

1
2
3
4
5
6
7
8
9

def reverse_scan(a)
  n = a.size

  (n-1).downto(0) do |i|
    p a[i]
  end
end

reverse_scan([4,3,2,9,2,0])

Often you want to traverse one array and perform some operation on each element in the sequence. For example, the following function takes a string as the input and returns a new string that is in upper case.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def upper_case(input)
  letters = input.chars
  
  for i in (0..input.size-1)
    letters[i] = letters[i].upcase
  end
  
  letters.join
end

p upper_case('hello')

An operation like upper_case is called a map because it maps a function (in this case uppercase) onto each of the elements in the sequence.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def upper_only(input)
  letters = input.chars
  result = []
  
  for letter in letters
    if letter == letter.upcase
      result.append(letter)
    end
  end
  
  result
end

p upper_only('HeLlo')

An operation like upper_only is called a filter because it selects some of the elements and filters out the others.

Most common array operations can be expressed as a combination of map, filter and reduce.

Reduce operation is a basic building block that traverses a sequence and accumulates the elements into a single result.

Map operation is a basic building block that traverses a sequence and performs an operation on each element.

Filter operation is a basic building block that traverses a sequence and selects the elements that satisfy some criterion.