0

I have a strange problem so I'll just demo it for you to make it easier to understand. I have two lists:

>>> a = [1, 2, 20, 6, 210]
>>> b = [20, 6, 1]

The result I'm looking for is 3 (position of last matching item in list a based on matches in b)

b always has less data as it contains all duplicates of list a. I want to know what item in B matches the furthest in list a. So in this example, it would be 6 as 6 is furthest in the list of A.

Is there an easy way to do this - my initial approach is a nested loop but I suspect there's a simpler approach?

Almog
  • 452
  • 1
  • 7
  • 13
Lostsoul
  • 25,013
  • 48
  • 144
  • 239
  • Here's a simple one `sorted(b, key=a.index)[-1]` – yatu Sep 10 '20 at 11:54
  • You can also use `sort_together` from more_itertools – nordmanden Sep 10 '20 at 11:54
  • 1
    For the specific case described, the simplest (if not necessarily most efficient) code is just `max(b, key=a.index)` (or `b.sort(key=a.index)`/`sorted(b, key=a.index)` if you need the whole list sorted, not just the maximum value as described). – ShadowRanger Sep 10 '20 at 11:55
  • If you use map for b; then you can do it in O(n) ie no nested loops – Shubham Srivastava Sep 10 '20 at 11:55
  • @ShadowRanger What if `a = [6, 2, 20, 6, 210]` ? Note the 6 at the beginning. – Andrej Kesely Sep 10 '20 at 11:56
  • @AndrejKesely: You use [one of the techniques for simulating `rindex`](https://stackoverflow.com/q/522372/364696) instead. – ShadowRanger Sep 10 '20 at 11:58
  • @AndrejKesely good point. in my case, I removed dups from both lists but good question. – Lostsoul Sep 10 '20 at 11:58
  • 1
    @Lostsoul If you removed the duplicates even from `a`, then `a.index` will do. – Andrej Kesely Sep 10 '20 at 12:00
  • 2
    Thank you! Sorry I'm not sure why the question was closed when the recommended question did not solve my question. I wish you guys could have posted actual answers and gotten the upvotes but regardless, thank you very much for solving my issue. @ShadowRanger's answer would have been accepted. – Lostsoul Sep 10 '20 at 12:02
  • Do you want the position or the item? Your question says both, isn't quite clear. – superb rain Sep 10 '20 at 13:43

2 Answers2

4

The simplest (if not necessarily most efficient) code is just:

 max(b, key=a.index)

or if you want the whole list sorted, not just the maximum value as described, one of:

b.sort(key=a.index)

or

sorted(b, key=a.index)

If duplicates in the reference list are a possibility and you need to get the last index of a value, replace index with one of these simulations of rindex.

Update: Addressing your requirement for getting the position, not the value, there is an alternative way to solve this that would involve less work. It's basically a modification of one of the better solutions to emulating rindex:

bset = frozenset(b)
last_a_index = len(a) - next(i for i, x in enumerate(reversed(a), 1) if x in bset)

This gets the work down to O(m + n) (vs. O(m * n) for other solutions) and it short-circuits the loop over a; it scans in reverse until it finds a value in b then immediately produces the index. It can trivially be extended to produce the value with a[last_a_index], since it doesn't really matter where it was found in b. More complex code, but faster, particularly if a/b might be huge.

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
  • 1
    @superbrain: Yeah, that wasn't in the original question, and the comment said they liked my solution, so I just posted it. Edited to add an efficient index producing solution (that can also produce the value with theoretically better performance for larger inputs, though for small inputs, [your simple code that pushes the work to the C layer](https://stackoverflow.com/a/63830948/364696) is almost certainly faster; I up-voted it). – ShadowRanger Sep 10 '20 at 13:49
  • Thank you so much @shadowRanger - for me either position or value is good. Thanks for showing me how to do both options. – Lostsoul Sep 10 '20 at 13:52
  • Ah, sorry. I didn't realize that was added. A maybe simpler alternative to your efficient solution: `next(i for i in reversed(range(len(a))) if a[i] in bset)` – superb rain Sep 10 '20 at 14:19
2

Since you asked for the position:

>>> max(map(a.index, b))
3
superb rain
  • 5,300
  • 2
  • 11
  • 25