Proposal for Array.prototype.findRight

Find something from array is a very common pattern in development.

Now we have Array.prototype.indexOf, Array.prototype.lastIndexOf to find index of some value in the array.

And we also has Array.prototype.find to find some element who in the array in customized way.

But There’s not a way to allow us find something from the end to the start of array in customized way.

[].reverse().find() is work. But there’s two issues:

  1. unnecessary reverse.
  2. Array.prototype.reverse is not immutable.

You have to write the findRight in your codebase or [...[]].reverse().find().

As the result the third issue:

  1. unnecessary spread

So, perhaps we need Array.prototype.findRight.

And I create a draft proposal https://github.com/Kingwl/proposal-array-find-right.

Thanks!

2 Likes

Added Array.prototype.findIndexRight. Updated in the repo.

Added %TypedArray%.prototype.findRight and %TypedArray%.prototype.findIndexRight.

Updated in the repo.

The method names should use “last”, not “right” (in line with Array.prototype.lastIndexOf).

4 Likes

Or “end”, in line with String.prototype.trimEnd/padEnd?

We have trimStart,trimEnd, padStart, padEnd.

And we have find, findIndex.

But we don't have something like findStart or findIndexStart.

And there's no first or last existed yet.

Currently, we have reduce and reduceRight.

So the ***Right might be a solution for a method that we already have.

The current APIs you've listed depend on being left or right.

Yours does not.

In order for this to be useful, you should describe a use-case where it is probabilistically higher to find an element starting from the end. In particular, not only does it has to have that... the use case should also explain why using reverse would be bad.

IMO, such a use case will be very difficult to find. If such a "probabilistically higher on the right" case existed, then I would probably want to reverse the array, since the unreversed ordering is useless.

Logically, this would imply the only use case is when there is a high probability of finding item 1 from the right, then after finding, there is a high probability of finding item 2 on the left...and so on so forth. But this alternating construct implies that there is uniform probability of finding item n in the array, so findRight is useless since we can just use find and we go back to having no use case.

@jun-sheaf You seem to be missing the case where findRight finds a different item than find, not just the same item with less comparisons.

1 Like

I am actually missing two cases: Single use and duplicate items. The latter implies fairly bad structuring of data.

The only reasonable case seems to be single use.

Thanks for the review. I think my description may not be clear enough.

  1. As @bergus said. findRight finds a different item than find.
    The duplicate items may means the mapping of some items is duplicated. Not literally duplicated.
    One case is:
    a. You have a list and a current index that you should show the result of the index.
    b. Each item may have two status: enabled and disabled.
    c. You have two action: Jump to prev enabled item and Jump to next enabled item.
    d. The action will modified the current index.
    You could:
    a. slice(0, currentIndex) or slice(currentIndex + 1) (Maybe COW, little overhead)
    b. findRightIndex on slice of [0, currentIndex] or findIndex on slice of [currentIndex + 1]
    Or you could do it without findRight on find prev:
    a. create Map<item. index>
    b. slice(0, currentIndex)
    c. [...slice].reverse() (At least a copy and a reverse iteration)
    d. find on reversed slice
    e. indexMap.get(item) || -1

It's a bit complicated and maybe expensive.
If you have a huge list, And the operation happens when you are rendering(eg: React).
That may not caused a good experience.

Actually. That is a simple version of a scene that happened in my recent job. That's why I have the idea of the proposal.

  1. I have searched on github with keyword 'findRight'(and 'findLast'). The result shows many project has implemented their own findRight (or 'findLast'). And there's some references of lodash or ramda.

Thanks!

When I meant duplicate items, I meant duplicate with regard to the predicate. In particular, if they are different items, then you should find based on their differences. Also,

  1. if there is an ordering, then both find and findRight are horrible. You should use binary search.
  2. if there is no ordering, then assuming uniform probability (non-uniform probability was explained previously), then using find or findRight won't matter. Both have equal probability of finding an item.

Now regarding your use case, you have yet to address any issue.

  1. Why do you need to copy then reverse. Who cares if the slice is reversed, you only need it for finding the index.
  2. After you reverse, just findIndex and just subtract that from currentIndex. What is with the map?

The point of this conversation is that you give me a proper algorithmic analysis of the situation. You are asking for an algorithm after all.

In any case, if you do the math, you would understand that reverse takes n/2 operations and a find for an object on the reversed object would take n/2 operations for an object on the first half of the reversed object. All in all, it would essentially be the same as using find.

In the end, your only real argument is that it is convenient (which I cannot/do not argue against; I like convenience).

Why would you want a binary search if there is an ordering? If order matters, then the only kind of search you’d likely want do is “from 0, to length” or “from the length, to 0”.

1 Like

Thinking about this some more, I am against adding four methods (Typed)Array.prototype.findLast(Index) . Instead, the problem should be solved using iterators, which just need to become a bit more flexible to support this:

can achieve

const lastValue = array.values().reverse().find(…)
const [lastIndex, lastValue] = array.entries().reverse().find(…) ?? [-1, null]

while being simple and efficient.

3 Likes

Regarding algorithmic analysis, the runtime complexity of finding an item in an array of n elements that is k removed from the last,

  • using array reverse and find is O(n + k) whereas
  • using a findLast method is O(k)

As in the elements are ordered, e.g. numbers.

Which is precisely why the operation is a convenience. One could just do reverse iteration.

By the way, although your analysis is correct, my point was k must be bounded by n/2 in order for findRight to be useful. I could've stated at most n/2 operations however...

@bergus

Okay. I agreed.

@jun-sheaf

Why do you need to copy then reverse. Who cares if the slice is reversed, you only need it for finding the index.

My bad. slice does not need to spread again. But a readonly slice maybe not a copy. And if you call reverse, that will copy definitely.

After you reverse, just findIndex and just subtract that from currentIndex. What is with the map?

because you must handle -1 that you cannot subtract directly. (Okay, for convenience)

if there is an ordering

There's an ordering but the ordering may not ordered by the predicate you want to find. So you cannot binary search.

tickets.sort((a, b) => a.price - b.price); const mostExpensive = ticket.find(it => it.flight === 'TFS-HAM'), cheapest = ticket.findLast(it => it.flight === 'TFS-HAM');

That would be a case were this would be useful, so in general arrays of objects were you have multiple properties were one could possibly sort by. For findIndex a possibly usecase would be something like:

tickets.slice(tickets.findIndex(it => it.price >= 10), tickets.findLastIndex(it => it.price <= 20))

so I'd say this fairly common.

Using two index pointers would have runtime n. Yours is 2n. As I said, it’s a matter of convenience. I won’t argue against convenience.

1 Like

The latter, searching for an item by condition via reverse iteration, amounts to 99% of reverse searching I do, and I find myself doing that more often than even .lastIndexOf. There's lots of valid use cases for that, and they almost all are structured that way for performance reasons.

1 Like