查找列表中元素的最后一次出现

1. Introduction

When dealing with lists, we’ll sometimes need to identify which of the elements is the last that satisfies a condition.

The reason why this is an interesting problem is that we don’t want to traverse the whole list. That rules out approaches like partitioning the list or reversing it to then find the first element that satisfies the condition.

2. Description of the Solution

Three things to keep in mind before implementing a solution:

1. In reality, what we’re interested in is not the last element itself but the index at which the last element is located. Having the index, extracting the actual value of the element is trivial and efficient.
2. We don’t only want the last element that is equal to a certain value. We want to find the last element that satisfies a condition (equality is just a particular case). Therefore, we’re not going to take a sample value; we’ll take a predicate.
3. From the above, the elements of the list don’t have to be identical. As an example, imagine a list of Person, and we just want to find the last one with a certain telephone number.

First, a little boilerplate, to add a method lastWhen() to Lists:

implicit class Wrapper[T](val list: List[T]) extends AnyVal {

  /** Extension method that gives List instances the possibility to find their
    * last element that satisfies a given predicate.
    *
    * @param predicate
    *   the condition for which the last satisfying element will be searched
    *   for
    * @return
    *   index (zero-based) of the last element that satisfies the condition,
    *   or a negative number if it's not found
    */
  def lastWhen(predicate: T => Boolean): Int =
    useRecursiveScan(list, predicate)

  // TODO actual implementation goes here
}

2.1. Reversing the List

A very simple (even a bit naïve) approach to solve this problem is reversing the list, and then counting how many elements don’t satisfy the predicate:

private def useReverse(list: List[T], predicate: T => Boolean): Int =
  list.size - list.reverse.takeWhile(predicate(_) == false).size - 1

The main problem here is that the whole list needs to be reversed just to start discarding elements from the beginning — very inefficient. Is there a better way? Sure, there is!

2.2. Using a Recursive Scan

Let’s write a tail-recursive implementation to find the last element that satisfies a predicate:

@tailrec
private def useRecursiveScan(list: List[T], predicate: T => Boolean): Int =
  if (list.isEmpty) -1
  else if (predicate(list.last)) list.size - 1
  else useRecursiveScan(list.take(list.size - 1), predicate)

This recursive method stops when the list is empty (returning a negative value), or when the last element of the list satisfies the predicate (returning as an index the size of the list minus one). Otherwise, it calls itself recursively, passing the list without its last element and the same predicate as arguments.

It’s worth noting, in this implementation, that the method is tail recursive, so no concerns about the performance of excessive memory consumption should worry us.

2.3. Using the Native Library

More often than not, the APIs of the native libraries offer us efficient solutions to our basic problems. In our current case, we could avail of the method LastIndexWhere() of Lists (and sequences in general), which does exactly what we need! Let’s see it in action:

private def useNativeLibrary(list: List[T], predicate: T => Boolean): Int =
  list.lastIndexWhere(predicate)

3. Testing the Solution

In any case, if we use ScalaTest, we could implement basic unit tests (extending AnyWordSpec):

"A last element finder" should {
"fail to find last elements in an empty list" in {
  val list = List.empty[Char]
  assert(list.lastWhen(_ == 'c') < 0)
}

"fail find last elements if they are not there" in {
  val list = List('a', 'b', 'c', 'd', 'c', 'e')
  assert(list.lastWhen(_ == 'n') < 0)
}

"find last element as last if all are the same" in {
  val list = List('a', 'a', 'a', 'a', 'a')
  assertResult(4)(list.lastWhen(_ == 'a'))
}

"find last element (happy case)" in {
  val list = List('a', 'b', 'c', 'd', 'c', 'e')
  assertResult(4)(list.lastWhen(_ == 'c'))
}

4. Conclusion

This is a simple problem, yet it has the potential to teach us something: that just coding the first simple algorithm we can think of is not good enough. We should strive to provide an efficient solution. The first solution that we found is both tail-recursive and avoids scanning the whole list to find that last satisfying element.

The second solution is even simpler and relies on the good practices that the library gives us for free.

As usual, the full code for this article is available over on GitHub.