❔ Most efficient way to retrieve a range of objects from an array
Imagine you have some sort of array/list/dict/whatever to store every note in a song. Each note has a note-timestamp (when it appears in the song). You also have a current-timestamp, which could be i.e. the current playback position in the song. What's an efficient way to find all notes within, say, a 5 second range of the current-timestamp?
An example of an inefficient way would be to iterate through every note, evaluate whether its note-timestamp is within 5 seconds of the custom-timestamp, and then save a reference if it's true.
The goal is to match up player input notes with a song's notes for a rhythm game. Every time an input is received, the game needs to find out which note to match up the input with, but I think it would be too inefficient to check every note every time. So I'm wondering if there's a better way.
12 Replies
If the data is sorted by timestamp you can use binary search
Alright, I managed to create and sort a List (
List<HitNote>) for the data by timestamp. However, I don't quite understand how to use myList.BinarySearch() to find i.e. all the items with a timestamp within 5 seconds of the current-timestamp. myList is a list consisting of instances of class HitNote, which is a class that I have defined (has many properties). As I understand it, when I use myList.BinarySearch(item), it makes a search for this exact item. But I don't know what the exact item is, I just want to extract it if the timestamp condition is met.You might need to pass a custom comparer that finds an item that meets your criteria, then you can take a window on either side of that item that matches the number of things you want...
In other words: binary search to get you close without having to do a linear scan, then you will need to implement some logic to get exactly what you want from that rough part of the list.
I don't fully understand how to make a custom comparer like this.
The way I understand what you're saying, the custom comparer is used to find the item that meets my criteria.
So, in order for the custom comparer to find said item, it uses
BinarySearch() . But the only way I know how to use BinarySearch is this: myList.BinarySearch(theItemImLookingFor)
<-- So it seems like I need to have a reference to the item I'm looking for in order find its index. But how do I get a reference to the item without doing a linear search?
I hope it's clear what confuses me. If my goal is to get an index and a reference to an item that matches the criteria, it seems that I need to already have a reference to said item to find it - which is a circularity.There is an overload on the BinarySearch method that takes a comparer as the second parameter.
So if I understand it correctly, I need to define a new
public class HitNoteComparer: IComparer<HitNote>{
public int Compare(HitNote HN1, HitNote HN2){
// algorithm that returns negative number if HN1 has an earlier timestamp than HN2, etc.
}
}
Then pass myList.BinarySearch(theHitNoteImLookingFor, new HitNoteComparer()) ?
If that's what I need to do, wouldn't I still need a reference to theHitNoteImLookingFor in order to find it with my own comparer? All I know is the current timestamp, I don't have a reference to any HitNote, I just have a list of HitNotes sorted by timestamp.I don't see why. You can put whatever logic you want in your comparer. It will be passed a hit note and even if you only have a timestamp you can check if that timestamp is "close enough" that you return 0 to say you have a match. Now you have an index that is close to where you want, and it will be found very efficiently due to binary search.
Binary search is just a technique to halve your search space on each iteration instead of having to scan using a linear search. Whatever logic you would use in a linear search still applies.
Hmm... For the first of BinarySearch's arguments - can I put in a
HitNote instance that isn't necessarily in the myList? And then have a comparer that just finds the closes instance in the list?
Because the problem that got me confused is that I need to know the item in order to find the itemYes, to use the actual BinarySearch method on List you would pass in a dummy item with the timestamp you care about, I think. You could also always implement binary search yourself. I suggested it for the overall technique itself, not necessarily for exactly how it looks on List<T>.
Ah, I think I get it now
I will try to implement it
I made it work. Thanks for the help
Was this issue resolved? If so, run
/close - otherwise I will mark this as stale and this post will be archived until there is new activity.