Geeks With Blogs
Greg Young Greg.ToString()

I am dealing with trying to put some rankings of various types into the order book items for a given ticker.

I am going to leave some stuff out for brevity.

public class BookItem {

}

public class Ticker {

     BookItemCollection Bids;

}

Bids is kept in a sorted fasion based upon price.

There are N types of rankings which may be required in the future depending on the types of orders ahead of the item in the Bids collection. At this point there is only a single ranking type (position in general based upon price). This is a classic case of denormalization as the bookitem's position could quite easily be calculated at any given time; it is just terribly slow to do so O(n) ... the denormalization is O(n) for the entire book and this is an often checked item; so denormalizing it makes alot of sense.

say I have the prices of.

1       pos = 1
1       pos = 1
1.1    pos = 2
1.3    pos = 3
1.3    pos = 3

To implement this is quite simple ... After I have found the point where I am inserting a new order (i know the order above it/below it and their prices so I can determine a position for it); I iterate through the rest of the collection alterring the position rank. What worries me about this is the fact that the ticker who is doing the insert has the knowledge about how the bookitem is storing its ranking.

My next thought is to put in a ranking class which encapsulates some incremental logic.

public class Ranking {
    public void HasBeenPlacedAhead(BookItem _Item) {
    }
    public void HasBeenRemovedFromAhead(BookItem _Item) {
    }
}

In this case I have moved the logic away from the ticker; but it doesn't always work unless the ranking takes into account the positions of the items that were ahead of it (i.e. was it 1 position 2 or 7 position 2s as if I remove one position 2 it should move up if there is only 1 but if there are 7 then it should not). I have now ended up in a reverse situation where I have placed information regarding the collection into my ranking class where it does not belong.

This leads me to my next thought; what if I created a ranking strategy?


public class Ranking {
     public string Name { get { return m_Name; }}
     public decimal Value { get { return m_Value; }}

public interface IRankingStrategy {
     void SetInitialItem(BookItem _Item);
     void AddItem();
     Ranking GetRanking();
}

I call a factory to get a series of RankingStrategy objects ... I give it my initial object in order to set its inital state. Then I iterate through the rest of the book (past where it was inserted); I pass the item ... internally the ranking generator increments/decrements it's internal ranking ... foreach generator I add the ranking object to a collection on the bookitem.

This is sounding pretty good. The major problems I see with it is how the bookitem itself would deal with these rankings ..

public class BookItem {
    private RankingDictionary m_Rankings...
   
    and eventually I would have to pass in the name of the ranking that I would want (for instance “positional”)
}

Another thought would be to then provide helper methods on the BookItem class ... This would help clear things up quite a bit as far as clarity is concerned.

public class BookItem {
    private RankingDictionary m_Rankings...
    public Ranking PositionalRanking {
          get { return m_Rankings[“Positional“]; }
    }
}

An astute reader has come accross yet another problem here ... my string in the getter is directly coupled to the Ranking name returned by the strategy; I generally don't like this type of coupling. If I could just get rid of this coupling I think this would be a great way of handling things (may not be as efficient as possible but definately maintainable and extensible while maintaining a very reasonable efficiency)

2 other questions ..

1) What if the orderring is being done in a similar method (the looping through the items); is part of the logic not still in the ticker class as it is issuing the loop and calling the methods in a known order on the rankingstrategy?

2) Binary searching may no longer work in all circumstances; the strategies may need to be called on all objects in order  (take for instance a ranking that use its error margin from a regression of all previous items) This would become T(n/2) as opposed to T(log n) as both methods would need to call the 2nd half of the list in iteration on the average case ??? (wow it has been too long since I have done formal notation)

Given item #2 ... I am back to

public class Ranking {
     public string Name { get { return m_Name; }}
     public decimal Value { get { return m_Value; }}

public interface IRankingStrategy {
     void AddItem();
     Ranking GetRanking();
}

where each strategy will be called for each item in the book.

Anyone have any thoughts on a better way of doing this? I am at this point really open to ideas!

Cheers,

Greg

Posted on Wednesday, March 1, 2006 3:00 PM | Back to top


Comments on this post: Interesting issue

# re: Interesting issue
Requesting Gravatar...
On the issue of the rankings:

1 pos = 1
1 pos = 1
1.1 pos = 2
1.3 pos = 3
1.3 pos = 3

Is this normally the way that rankings work, it struck me as maybe these should be:

1 pos = 1
1 pos = 1
1.1 pos = 3
1.3 pos = 4
1.3 pos = 4


Because normally if you have a joint 1st position for example, then the next position is 3rd, or that's what I've seen in the past anyway.

If you do this, I would think that this would simplify your ranking as the rank of a given item would either be:

It's position in the collection

or

Work backwords from the position until the first position that isn't the same value and the rank is then pos + 1.

As I'm writing this, I'm wondering whether it really makes sense, but as I'm at work, I'll see what response I get to it before dwelling any longer...

Just my thoughts.

C
Left by Carl Wright on Mar 02, 2006 3:31 AM

# re: Interesting issue
Requesting Gravatar...
At first thought; I am not sure this would help much.

In either case I could use the ranking compared to the ordinal to help detect whether or not I had a possible situation ahead of me.

i.e. if the inserted node's index is different from its ordinal position then I know that somewhere in the list above it; there is a tie.

On the example of deleting a node I would still have to check if it had a tie and then if not iterate through the rest of the list decrementing one from every ranking.

The reason why we are using this particular ranking system is; this is how stock traders view the order book. They are interested in the top 5 items generally (top 5 prices whether that is 5 or 100 items they don't care). I would prefer to not change this as it is a major concept within the problem domain.



Left by Greg Young on Mar 02, 2006 10:37 AM

Your comment:
 (will show your gravatar)


Copyright © Greg Young | Powered by: GeeksWithBlogs.net