Click here to Skip to main content
14,975,683 members
Please Sign up or sign in to vote.
4.33/5 (3 votes)
See more:
Ok, first a little background information.
I've been working on a class called Region which has 6 key fields:
C#
//these are values in the Region class
int LoVelocity;
int HiVelocity;

int LoNote;
int HiNote;

int LoChannel;
int HiChannel; 


So in order for me to find the Region I'm looking for I would provide the velocity, note, and channel and check to see if it is in between these values.

Something like this:
C#
//somewhere in the Region class
public bool isWithinRegion(int channel, int note, int velocity)
{
    if (channel >= this.LoChannel && channel <= this.HiChannel &&
        note >= this.LoNote && note <= this.HiNote &&
        velocity >= this.LoVelocity && velocity <= this.HiVelocity)
                return true;
    return false;
}


My question is given a bunch of these Regions is there a better way to search for the Region I'm looking for besides using an array and loop because the current implementation seems kinda slow?
C#
//this is the way I find Regions now
//which can be slow when there are alot of them.
private Region FindRegion(int channel, int note, int velocity)
{
    for (int x = 0; x < regions.Length; x++)
    {
        if(regions[x].isWithinRegion(channel,note,velocity))
            return regions[x];
    }
    return null;
}


I did think about using other structures besides an array, but the condition that the values have to be in between the high and low values keeps throwing me off.

Any help is appreciated...

Update Oct 22,11

Here is some more information for those that are wondering

1. The collection of regions will not change once loaded also none will be added or deleted.
2. The regions will not be sorted/ordered but will 'most likely' appear in ascending order based on their note ranges.
//likely ordering
-REGION 1
LoNote = 0
HiNote = 60
...
-REGION 2
LoNote = 61
HiNote = 127
...

3. The region is searched for whenever a noteOn occurs and once it is found it's index is cached until a noteOff event happens and then the process repeats.


If you want I can also make more code available...
Posted
Updated 22-Oct-11 13:12pm
v3
Comments
Sergey Alexandrovich Kryukov 21-Oct-11 22:16pm
   
The major improvement might lie in the direction of adding redundancy to the regions container, but it needs additional information on how this container is populate and what's it meaning. Optimization of IsWithinRegion is possible, but will be minor.
--SA
BillWoodruff 21-Oct-11 23:22pm
   
+5 for this very interesting question !

Is it the case that all 'regions' are non-overlapping, and there can be one and only one region that matches your search criteria ?

Edit: Another question I think could be critical to a solution here is regarding the nature of the collection of class 'Region, titled in your code 'regions.

Is this collection something pre-built, or read in from a data-source when the application initializes, or added to dynamically at run-time ? Are 'Region objects in this collection edited at run-time ?

It would be interesting to see a short excerpt from a data set of the values you expect to encounter, just a few samples.
BillWoodruff 22-Oct-11 19:50pm
   
Unless you are modeling a monophonic synthesizer, I'd assume that playing a chord in a region of your instrument mapped to midi-out (or whatever your internal notation is) on a specific channel would result in your needing some data structure that not only keeps the index of the matching in-use 'region,' but also keeps a list of current note-downs in that region ?

The fact that "regions will not change once loaded" suggests to me some one-off pre-indexing operation to optimize future matching, although that's just an off-the-cuff hunch :)

At the point you 'settle on' a particular data structure, like an Interval Tree, you may wish to post a question on the Algorithms forum here on CP, where there is often very high-level discussion by experts with great depth in formal computer science (of the calibre of Daniel Grunwald, Bob Janova, Luc Patyn).

good luck, Bill

Well, the optimization of IsWithinRegion can be a tiny bit better if you modify the code by André a bit more:

C#
public bool isWithinRegion(int channel, int note, int velocity)
{
    if (channel < this.LoChannel || channel > this.HiChannel)
        result = false;
    else
    if (note < this.LoNote || note > this.HiNote)
        result = false;
    else
    return this.LoVelocity <= velocity && velocity <= this.HiVelocity;
}


However, the improvement will be extremely small. (There is not excuse to leave you original code though.)

I don't think multithreading will help you much; it can even easily make things worse.

Real optimization can potentially come from improvement of data structure and code design, in particular, from adding some data redundancy (please see my comment to the question). For a simple example, why search in the randomly populated list is of O(N) but in the dictionary it is of O(1)? Because of redundancy (buckets) introduced in dictionary. Your case can be way more complex though.

(About "big O" notation, see http://en.wikipedia.org/wiki/Big_O_notation[^].)

However, such approach needs more information on your problem.

—SA
   
v2
Comments
Andrew Rissing 21-Oct-11 22:46pm
   
See my comment above about short circuiting. I would agree whole heartedly with the statement about using a different data structure. I don't see a dictionary working out well if he has a large collection of data. It is just hard to say much with so little information provided.
Sergey Alexandrovich Kryukov 23-Oct-11 20:09pm
   
Agree. You should understand that I mentioned a dictionary just as an example of use of redundancy for improving performance.
--SA
Espen Harlinn 23-Oct-11 19:28pm
   
Nice reply :)
Sergey Alexandrovich Kryukov 23-Oct-11 20:08pm
   
Thank you, Espen.
--SA
Assuming your Regions don't overlap, span a continuous range, and you don't have any weird gaps. I'd just sort the Regions in ascending order and then in reverse order find the first region that is less than the three upper bounds. It'll save you half the checks. It's a simple change.

Like SAKryukov said, you can change the data structure and see some performance improvements. It just means taking advantage of your data's characteristics in some way.

It really just makes me wonder that you're trying to optimize something so simple. To me this means one of three things:

1) You really call this way too much, which to me I'd see if there is a way to cache these results so you don't have to if that makes sense.

2) You are really desperate for milliseconds of time. You really can't do much about that but keep pushing the envelope further.

3) You are looking at the wrong thing. If you've determined that this is indeed your bottleneck, see item 1. If you haven't and you just believe this is your bottle neck, I'd focus elsewhere first.
   
Comments
BillWoodruff 22-Oct-11 2:47am
   
+5 for very thoughtful higher-order analysis.

I find your comment about sorting the Regions in ascending order very interesting, and yet puzzling. While we are kind of "in the dark here" without an actual data set of range values in Regions to look at, I'm wondering how you could sort what in this case are classes.

It seems unlikely that each Region would have, for each of the three ranges, note, velocity, channel, mutually exclusive ranges ?

Now if we had a "heuristic" to go on, like a strong sense of which Region might be most selected, or least selected, we could arrange the search based on that.

If you don't mind, for the benefit of someone who's probably not at your level of excellence in analysis of problems like this, I'd appreciate an expansion of your comment on sorting the Regions.
Andrew Rissing 22-Oct-11 21:07pm
   
I was shooting in the dark with some significant assumptions about the data. If the data covers all of the ranges of the Velocity, Note, Channel values, the sorting would be based upon the three lower bounds of the Region (LoVelocity, LoNote, and LoChannel). It would be analagous to a clustered key in a database.
sdefrtgy 22-Oct-11 18:48pm
   
Actually finding the region is just one step in a multi-step process, but once the region is 'found' I do hang on to the index for future use. Btw the code is used in a software synth I'm making in c# so timing is important.
RaviRanjanKr 23-Oct-11 16:55pm
   
Nice answer, My 5+
Sergey Alexandrovich Kryukov 23-Oct-11 20:07pm
   
Very good, my 5.
I must note there is no "natural" order in the set of regions, but you can introduce some "artificial" one. What do you mind is not quite clear...
--SA
I just can't resist joining the play on this one :)
C#
using System.Collections.Generic;

namespace TestVNCRegions
{
    public class VNCRegion
    {
        public string VNCRegionName;
        int LoVelocity;
        int HiVelocity;
        int LoNote;
        int HiNote;
        int LoChannel;
        int HiChannel;

        public static List<VNCRegion> VNCRegions = new List<VNCRegion>();

        public static VNCRegion NewVNCRegion;

        public static void AddVNCRegion(string vncRegionName, int lVel, int hVel, int lNte, int hNte, int lChn, int hChn)
        {
            NewVNCRegion = new VNCRegion
            {
                // by adjusting the values here
                // we can save comparison time ?
                VNCRegionName = vncRegionName,
                LoVelocity = lVel + 1,
                HiVelocity = hVel - 1,
                LoNote = lNte + 1,
                HiNote = hNte - 1,
                LoChannel = lChn + 1,
                HiChannel = hChn - 1
            };

            VNCRegions.Add(NewVNCRegion);
        }

        public static VNCRegion FindRegion(int velocity, int note, int channel)
        {
            foreach (VNCRegion theRegion in VNCRegions)
            {
                if
                (
                    velocity > theRegion.LoVelocity
                    && velocity < theRegion.HiVelocity
                    && note > theRegion.LoNote
                    && note < theRegion.HiNote
                    && channel > theRegion.LoChannel
                    && channel < theRegion.HiChannel
               )
               return theRegion;
            }

            return null;
        }
    }
}
And a test might look like this:
VNCRegion.AddVNCRegion("region1", 1, 20, 4, 43, 2, 99);
VNCRegion.AddVNCRegion("region2", 21, 32, 45, 66, 100, 145);
VNCRegion.AddVNCRegion("region3", 33, 55, 67, 89, 146, 200);

VNCRegion foundRegion1 = VNCRegion.FindRegion(18, 12, 34);
if (foundRegion1 != null) Console.WriteLine("test 1 returns: " + foundRegion1.VNCRegionName);

VNCRegion foundRegion2 = VNCRegion.FindRegion(24, 50, 102);
if (foundRegion2 != null) Console.WriteLine("test 2 returns: " + foundRegion2.VNCRegionName);

VNCRegion foundRegion3 = VNCRegion.FindRegion(44, 72, 198);
if (foundRegion3 != null) Console.WriteLine("test 3 returns: " + foundRegion3.VNCRegionName);
Discussion: I find this a very interesting question because I can 'envision' a wide gamut of problems in which similar discrimination of items which must match multiple range criteria is required.

While this may be simply 'fantasy,' I wonder if there might be a way to calculate a unique hash ... based on range values, for some sub-set of this type of problem ... that might result in a highly optimized search. Trying to conceptualize higher-order solutions to this type of problem, alas, I encounter my lack of formal computer science education. But, that limit just makes me more insatiably hungry for knowledge :)

And, a final aside: sometimes I think there's a curious lack of an object (an object encapsulating a struct ?) in .NET named 'Range.' That you might use like this:
Range<int> myIntRange = new Range<int> { 12, 24 };

if(myIntRange.Contains(22)) ...

Range<char> myCharRange = new Range<char> { 'k', 'r' };

if (! myCharRange.Contains('x')) ...</char></char></int></int>
   
v3
Comments
sdefrtgy 22-Oct-11 19:18pm
   
Yeah I would love to have kept the hash I had before were I simply took the note value and velocity and produced a unique value, however the Sfz spec, which I'm trying to follow uses these 'ranges'.
BillWoodruff 22-Oct-11 19:44pm
   
Get Linquified ? :)

return VNCRegions.FirstOrDefault(theRegion => velocity > theRegion.LoVelocity && velocity < theRegion.HiVelocity && note > theRegion.LoNote && note < theRegion.HiNote && channel > theRegion.LoChannel && channel < theRegion.HiChannel);
RaviRanjanKr 23-Oct-11 16:57pm
   
My 5+
If I understand your problem correctly, velocity, note, and channel form a 3-dimensional coordinate system. You have a large number of axis-aligned rectangular boxes and want to quickly find the one containing a given point.

A general solution would be to use an Interval Tree[^].

But a lot of the complexity in the interval tree comes from the support for overlapping regions. Given that your find method returns only a single region, I assume that regions are non-overlapping in your case.
Then, it would suggest storing your regions in a spacial data structure (e.g. a K-d tree[^]).
You'll have to re-build the whole data structure whenever the list of regions changes, though; so this is only helpful if you do lots of queries on the same set of regions.

The basic idea could be that each node in the tree represents an rectangular box of space. The root node represents the whole space (int.MinValue to int.MaxValue). Leaf nodes associate that space with one of your region objects (or no region, if that space is empty); while non-leaf nodes partition the space (see K-d tree for details).
Searching for a point in this tree is simple and works in time proportional to the height of the tree. The tricky part is constructing the space partition so that the tree is well balanced.
If the tree is well balanced, lookups will take O(lg N) time.
   
v2
Comments
sdefrtgy 22-Oct-11 19:29pm
   
An Interval Tree may be a good idea as the collection of regions will never change. I will have to try this out.
Espen Harlinn 23-Oct-11 19:26pm
   
Nice reply :)
The first thing I thought of was changing the isWithinRegion function so that not all checks need to be performed.
C#
//somewhere in the Region class
public bool isWithinRegion(int channel, int note, int velocity)
{
    bool result = true;

    if (channel < this.LoChannel || channel > this.HiChannel)
        result = false;
    else
    if (note < this.LoNote || note > this.HiNote)
        result = false;
    else
    if (velocity < this.LoVelocity || velocity > this.HiVelocity)
        result = false;

    return result;
}

See if this gives you better performance.
   
Comments
sdefrtgy 21-Oct-11 20:21pm
   
Thanks for your reply, I put together a simple worst case scenario using both versions and the difference was relatively small until the amount of regions reached a point that it would never actually get to. I might try and solve my latency issues with multithreading instead.
Sergey Alexandrovich Kryukov 21-Oct-11 22:17pm
   
Warning: you can easily waste more CPU time on multithreaded variant than save it.
--SA
Sergey Alexandrovich Kryukov 21-Oct-11 22:30pm
   
I voted "4" because this code still has some unnecessary steps. Please see my solution :-)
Main thing, however, my be in code design, please see my notes in my solution below the code.
--SA
Andrew Rissing 21-Oct-11 22:42pm
   
The above should not improve performance what so ever and may actually decrease it. The && operator in C# automatically short circuits in cases where it can. See: http://msdn.microsoft.com/en-us/library/2a723cdk(v=VS.100).aspx.
BillWoodruff 22-Oct-11 2:41am
   
Your focus on the potential gain from short-circuiting via && is, imho, right on target here, Andrew.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900