CODEWITHSUNDEEP
c#algorithm
Gullu
Gullu

Reputation: 3529

How to create bins of fixed size and put the right value in the right bin (efficient algorithm for this logic)

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)

and so on until

and so on until

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

Upvotes: 0

Views: 3119

Answers (4)

Kirk Broadhurst
Kirk Broadhurst

Reputation: 28698

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.

Upvotes: 1

loxxy
loxxy

Reputation: 13151

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.

Upvotes: 1

Ian Mercer
Ian Mercer

Reputation: 39277

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;

}

Upvotes: 3

Adam
Adam

Reputation: 723

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.

Upvotes: 0

Related Questions