C#•14mo ago

❔ Best way to cache index of an object in a list

I have a list with anywhere from 0 to maybe 1000 objects in it, and I have to try and find the index of that object very quickly (during mouse move events, so 100s of times per second possibly) What would be a good way to optimise this?

38 Replies

br4kejetOP•14mo ago

I tried storing the index of the object in the object itself, but because the objects can move in that list during said mouse events, I don't think it would be that much faster, because if I move an object to the start of the list for example, I have to increment the index of every object between the object's previous index and 1 Kinda considering doing something like calculating the size of the object, and getting the address of the current instance and trying to calculate it based on that address and the object size

Judes•14mo ago

Show some code. It's impossible to give you an answer without context of the surrounding code.

br4kejetOP•14mo ago

It's for a video editor, the list being a list of clips within a track

Judes•14mo ago

Post the relevant code snippet to Pastebin and send us the link here so we can see what's being done.

br4kejetOP•14mo ago

I don't know what part to send, it's kinda just all over the place

br4kejetOP•14mo ago

Judes•14mo ago

Can you show the whole thing? Like, where are you updating the list? And how are you doing it? (In code.)

br4kejetOP•14mo ago

I add a clip to the list whenever a clip is added to a track... obviously, and that could be called from either dragging a thing into the timeline, copy+paste, etc.

public void AddClip(Clip clip) => this.InsertClip(this.clips.Count, clip);
public void InsertClip(int index, Clip clip) {
    if (clip.Track != null && clip.Track.TryGetIndexOfClip(clip, out _))
        throw new Exception("Clip already exists and is valid in another track: " + clip.Track);
    Clip.SetTrack(clip, this);
    this.clips.Insert(index, clip);
    this.cache.OnClipAdded(clip);
}

public void AddClip(Clip clip) => this.InsertClip(this.clips.Count, clip);
public void InsertClip(int index, Clip clip) {
    if (clip.Track != null && clip.Track.TryGetIndexOfClip(clip, out _))
        throw new Exception("Clip already exists and is valid in another track: " + clip.Track);
    Clip.SetTrack(clip, this);
    this.clips.Insert(index, clip);
    this.cache.OnClipAdded(clip);
}

At the moment it's completely unordered, but i'm trying to see if I can sort it by the timestamp of the clips which might help

Judes•14mo ago

Is the insertion order relevant?

br4kejetOP•14mo ago

O log n i think It's not

Judes•14mo ago

Like, if I add two tracks at different times, does it matter if they're in the correct chronological positions? Also, can there be the same track twice on this list?

br4kejetOP•14mo ago

Tracks can be in any order, depending on how they're added in the UI, and no there can't be duplicate tracks Nor duplicate clips Would it be easier if you could see the github code? This code base is cheeks so you'd have to work around it

Judes•14mo ago

Yes, that would help.

br4kejetOP•14mo ago

https://github.com/AngryCarrot789/FramePFX/blob/master/FramePFX/Editor/Timelines/Track.cs#L165C21-L165C21

Judes•14mo ago

It seems to me you don't really need to know the index of a given element of the list. Instead you wish to only know whether that element in present in the list, is that right?

br4kejetOP•14mo ago

Because it's an MVVM app, sometimes I have to map the model (Clip) to a view-model (ClipViewModel), and so it would help with performance if I could directly index into either model or view-model track lists

Judes•14mo ago

Do you have an example of that happening?

br4kejetOP•14mo ago

Not in the git repo... I have yet to push it but here:

if (this.Timeline is TimelineViewModel timeline) {
    foreach (TrackViewModel track in timeline.Tracks) {
        foreach (ClipViewModel clip in track.GetSelectedClipsAtFrame(timeline.PlayHeadFrame)) {
            if (!(clip is VideoClipViewModel) || !(((VideoClip) clip.Model).GetSize() is Vector2 frameSize)) {
                continue;
            }
            SKRect rect = ((VideoClip) clip.Model).TransformationMatrix.MapRect(frameSize.ToRectAsSize(0, 0));
            Point pos = new Point(Math.Floor(rect.Left) - half_thickness, Math.Floor(rect.Top) - half_thickness);
            Size size = new Size(Math.Ceiling(rect.Width) + thickness, Math.Ceiling(rect.Height) + thickness);
            dc.DrawRectangle(null, this.OutlinePen, new Rect(pos, size));
        }
    }
}

if (this.Timeline is TimelineViewModel timeline) {
    foreach (TrackViewModel track in timeline.Tracks) {
        foreach (ClipViewModel clip in track.GetSelectedClipsAtFrame(timeline.PlayHeadFrame)) {
            if (!(clip is VideoClipViewModel) || !(((VideoClip) clip.Model).GetSize() is Vector2 frameSize)) {
                continue;
            }
            SKRect rect = ((VideoClip) clip.Model).TransformationMatrix.MapRect(frameSize.ToRectAsSize(0, 0));
            Point pos = new Point(Math.Floor(rect.Left) - half_thickness, Math.Floor(rect.Top) - half_thickness);
            Size size = new Size(Math.Ceiling(rect.Width) + thickness, Math.Ceiling(rect.Height) + thickness);
            dc.DrawRectangle(null, this.OutlinePen, new Rect(pos, size));
        }
    }
}

Wait that doesn't help much

Judes•14mo ago

Still I see no usage of the index.

br4kejetOP•14mo ago

It was in the GetSelectedClipsAtFrame method

public IEnumerable<ClipViewModel> GetSelectedClipsAtFrame(long frame) {
    return this.clips.Where(clip => clip.IsSelected && clip.IntersectsFrameAt(frame));
}

public IEnumerable<ClipViewModel> GetSelectedClipsAtFrame(long frame) {
    return this.clips.Where(clip => clip.IsSelected && clip.IntersectsFrameAt(frame));
}

Judes•14mo ago

Still seems like you're not using any indexes here. You're just iterating the list.

br4kejetOP•14mo ago

Just trying to find an example, i can barely get myself around this project I don't use this method apparently but

public ClipViewModel GetClipByModel(Clip clip) {
    return this.Model.TryGetIndexOfClip(clip, out int index) ? this.clips[index] : null;
}

public ClipViewModel GetClipByModel(Clip clip) {
    return this.Model.TryGetIndexOfClip(clip, out int index) ? this.clips[index] : null;
}

which is them implemented as

public bool TryGetIndexOfClip(Clip clip, out int index) {
    return (index = this.IndexOfClip(clip)) != -1;
}
public int IndexOfClip(Clip clip) {
    List<Clip> list = this.clips;
    for (int i = 0, count = list.Count; i < count; i++) {
        if (ReferenceEquals(this.clips[i], clip)) {
            return i;
        }
    }
    return -1;
}

public bool TryGetIndexOfClip(Clip clip, out int index) {
    return (index = this.IndexOfClip(clip)) != -1;
}
public int IndexOfClip(Clip clip) {
    List<Clip> list = this.clips;
    for (int i = 0, count = list.Count; i < count; i++) {
        if (ReferenceEquals(this.clips[i], clip)) {
            return i;
        }
    }
    return -1;
}

Judes•14mo ago

Are you sure this GetClipByModel compiles?

br4kejetOP•14mo ago

Yeah

Judes•14mo ago

Is there an implicit conversion between Clip and ClipViewModel?

br4kejetOP•14mo ago

Nah GetClipByModel is defined in TrackViewModel, where clips stores ClipViewModels

Judes•14mo ago

I see.

br4kejetOP•14mo ago

I tried to keep the standard of view models containing a Model property, being their model object

Judes•14mo ago

Well, to answer your question: the most appropriate data type here appears to be HashSet<Clip> instead of List<Clip>, since it guarantees uniqueness of elements, ordering doesn't matter, and all read/write operations are O(1). (That said, this whole project is overwhelmingly overengineered, and if I'm being honest performance is the absolute last thing you should be worrying about here.) Here's an article on hash sets: https://medium.com/@shawnastaff/c-collection-types-hashset-vs-list-bae022e7b439.

br4kejetOP•14mo ago

The clips do need to be ordered between the model and view model though, otherwise to map a Model to ViewModel, I'd have to search one of the lists (e.g. Track Model list) for the object's index to then map into the other list (e.g. ViewModel list) So as long as those two lists are in sync, then the app works fine, and the actual clips themselves can be unordered Overengineered though?

Judes•14mo ago

IIRC, the hash set implementation of c# maintains ordering of the elements inserted. although this behavior is not documented you should be fine using a hashset

br4kejetOP•14mo ago

The hash set doesn't contain an IndexOf function though right? I can't seem to get binary sorting to work either 😦

Judes•14mo ago

you won't need one. you don't need to know the index of anything. you're not using it for anything, so you can just query the hashset.

br4kejetOP•14mo ago

I may do at some point though If I need to map a Clip Model to a ViewModel, I have to find the index of the Clip Model in the Timeline Model, then use that to directly index into Timeline ViewModel like the method I showed above. Even though I don't use it now, I may be using it at some point

Judes•14mo ago

Look up YAGNI on Google.

IsNotNull•14mo ago

@carrotther Do they have to click and hold a mouse button down while dragging a clip around to position it? Why wouldn't you store a reference somewhere when they start a drag on the clip? In a web app you might have a list on a timeline that you bind to, and the potential 'drop' locations for an item would just be visual and wouldn't change the cannonical order until the user releases the mouse...but it sounds like you might have some more complicated concerns? Previewing the drop in a more nuanced way?

br4kejetOP•14mo ago

I want to do this but I don't know how to do it in WPF so I'm stuck just moving the live clip around

Accord•14mo ago

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.

Gaming

Programming

❔ Best way to cache index of an object in a list