0

Need help with an efficient algorithm to gather data that will be displayed in a chart. I am using c# but you can use pseudo code as a solution.

To explain I am using below sample. Starting with zero create 10 bins on either side (positive bins and negative bins). A bin is just a container. (counter)

  • bin10 (numbers 91 to 100 go in this bin)
  • bin9 (numbers 81 to 90 go in this bin)
  • bin8 (numbers 71 to 80 go in this bin)

and so on until

  • bin2 (numbers 11 to 20 go in this bin)
  • bin1 (numbers 1 to 10 go in this bin)
  • bin0 (number zero goes in this bin - the set point. Any number can be set point. I have taken zero to illustrate)

  • bin-1 (numbers -1 to -10 go in this bin)

  • bin-2

and so on until

  • bin-10 (numbers -91 to -100 go in this bin)

Need help for an efficient algorith for below.

int[] bins = CreateBins(bin range, number of bins on each side, setpoint)

CreateBins(10, 10, 0) 
{
   //??
}

FindTheRightBinAndInsertInFoundBin(value, bin[])
{
  //??
}

FindTheRightBinAndInsertInFoundBin(77, bin[])
//that should basically do a bin8++ where bin8 is an index into the bin array

Update : A 2D array is fine if it does the job. (or any data structure for that matter like dictionary etc).

thank you

2
  • Your most obvious problem here is that you can't have negative arrays - in C# arrays are 0 based. You'd be better off using a dictionary of bins, with the 'index' used as a key. This will let you have negative indexed bins. Sep 12, 2011 at 6:02
  • All, thanks for your responses. I will test all solutions provided here and update in day or two. thanks
    – Gullu
    Sep 12, 2011 at 13:09

4 Answers 4

3

CreateBins can return an array of the right size.

PutInBin can use this method to calculate which bin and then add an offset so it fits in the array (no negative indexes).

int GetBin(int value)
{
  if (value) == 0 return 0;
  else if (value<0) return (value-9)/10;
  else return (value+9)/10;

}
0
1

I don't know what range is supposed to mean - it should measure size, either of a single bin or all bins, because the actual "range" is determined by the set point, the number of bins and the size. I'm going to assume it's bin size.

class Bins
{    
    private int setPoint;
    private int binSize;
    private int numberOfBins;
    private Dictionary<int, int> bins; // bins are just counters, right?

    CreateBins(int range, int numberOfBins, int setPoint)
    {
        this.setPoint = setPoint;
        this.binSize = range
        this.numberOfBins = numberOfBins;
        bins = new Dictionary<int, int>();
    }  

    PutInRightBin(int value) 
    {
        var binIndex = (value - setPoint) / binSize 
        // add or substract a 1 here because your 'first' bin is index 1, not 0.
            + Math.Sign((value - setPoint)/binSize);
        if (!bins.ContainsKey(binIndex))
        {
            bins.Add(binIndex, 0);
        }

        bins[binIndex] = bins[binIndex] + 1;
    }
}

edit

I think the key element here is the bin determing algorithm:

var binIndex = (value - setPoint) / binSize          
+ Math.Sign((value - setPoint)/binSize); 
  • subtract the set point from the value, so you can determine whether it is on the set point, or to the positive or negative side of it.
  • divide by the bin size to determine which bin you want to place in. so 0-9 will result in 0, 10-19 will result in 1, and -20 to -29 will result in -2.
  • add or substract 1 using Math.Sign to fix the indexing, because you effectively want 1-based indexing rather than 0 based indexing (relative to your set point).

I have the edge case of the bin size elements wrong here (i.e. 10 will end up in bin 2 rather than bin 1). The fix is probably

var binIndex = (value - Math.Sign(value) - setPoint) / binSize 
    + Math.Sign((value - setPoint)/binSize);

which will 'move' the value one closer to 0. However you will need to test to prove this.

1
  • Yes. You are correct on range. it is bin size. They are just counters. thx
    – Gullu
    Sep 12, 2011 at 13:14
1

You perhaps missed out that your algorithm requires 2D Array.

Following is a C# Code which implements your algorithm:

int[][] bins = CreateBins(10, 10, 0);

// Arguments : Bin range, Number of bins on each side, Set Point 
static int[][] CreateBins(int binRange, int noOfBins, int setpoint) 
{
    int[][] tempBins = new int[noOfBins * 2 + 1][];

    for (int i = 0, j = noOfBins; i != j; i++ , j--)
    {
        tempBins[i] = new int[binRange];
        tempBins[j] = new int[binRange];
    }

    tempBins[noOfBins] = new int[] {setpoint};

    return tempBins;   
}

// Arguments : Value, Bin in which value is to be inserted
static void PutInRightBin(int value, int [] bin)
{   
    for(int i=0; i<bin.Length;i++) if(bin[i]==null) bin[i]=value;
}

The above will produce a result similar to as shown:

enter image description here

Use PutInRightBin() to insert the values.

5
  • It seems like you've missed the purpose of PutInRightBin - and it's not named well. It should be FindRightBin. It needs to determine which bin the value should be put into. Sep 12, 2011 at 5:40
  • Well I merely filled in the column provided by the OP. But you are right. One could use an additional function GetBin() as per Hightechrider's answer to get the correct bin.
    – loxxy
    Sep 12, 2011 at 5:59
  • you're right, I'm assuming I understand what's being asked. It's not really clear. Sep 12, 2011 at 6:05
  • Yes. I think I should have called it FindTheRightBinAndInsertInFoundBin(). thanks
    – Gullu
    Sep 12, 2011 at 13:13
  • With some tweaks your solution will work and I have upvoted, however I am going with Kirk's solution since he does not iterate over all the bins. thanks
    – Gullu
    Sep 12, 2011 at 22:11
0

I only know PHP, hope it helps some.

function PutInRightBin ($InputNum) {

$BinCycle = -91;
$BinCount = -10;

while ($BinCycle <= 100) {

    if ($InputNum <= $BinCycle) {
        return $BinCount;
    }

    $BinCycle = $BinCycle + 10;
    $BinCount = $BinCount + 1;

    if ($BinCount = 0) {
        $BinCycle = 0;
    }
}

Not sure how you want it to output. But i think that would work with some minor alterations.

1
  • 1
    Could not understand since I dont know php perhaps. Appreciate your effort. thanks
    – Gullu
    Sep 12, 2011 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.