which data structure best fits this?

Thread view:

tak - 18 Sep 2006 19:39 GMT

hi,

i am looking for a data structure for fast retrievals... and here is my
scenario.

this table is about foreigncy exchange. i will have a buy currency,
sellcurrency, levels, and rate.

A transaction involves from a BUY currency to Sell currency, and it can
have multiple levels, meaning... if the sell amount is 1000, the rate
is 1.1, but if the sell amount is 2000, the rate is 1.2..etc...

Say there is a fixed amount of currencies that I need to maintain (say
10 type only) And I need to store all these rates in a structure, for
fast retrieval..

More concrete example.

Sell : USD Buy: EUR Level: 1 - 1000 rate: 1.1
Sell : USD Buy: EUR Level: 1000 - 5000 rate: 1.2
Sell : USD Buy: EUR Level: 5000 - 99999999 rate: 1.3

Sell : USD Buy: CAD Level: 1 - 1000 rate: 1.1
Sell : USD Buy: CAD Level: 1000 - 5000 rate: 1.2
Sell : USD Buy: CAD Level: 5000 - 99999999 rate: 1.3

Sell : USD Buy: GBP Level: 1 - 1000 rate: 1.1
Sell : USD Buy: GBP Level: 1000 - 5000 rate: 1.2
Sell : USD Buy: GBP Level: 5000 - 99999999 rate: 1.3

------ So, Sell for USD type is finished here.

Sell : EUR Buy: USD Level: 1 - 1000 rate: 1.1
Sell : EUR Buy: USD Level: 1000 - 5000 rate: 1.2
Sell : EUR Buy: USD Level: 5000 - 99999999 rate: 1.3

Sell : EUR Buy: CAD Level: 1 - 1000 rate: 1.1
Sell : EUR Buy: CAD Level: 1000 - 5000 rate: 1.2
Sell : EUR Buy: CAD Level: 5000 - 99999999 rate: 1.3

Sell : EUR Buy: GBP Level: 1 - 1000 rate: 1.1
Sell : EUR Buy: GBP Level: 1000 - 5000 rate: 1.2
Sell : EUR Buy: GBP Level: 5000 - 99999999 rate: 1.3

------ Sell for EUR is finished here.

so on with GBP, and CAD.

my requirements:

Say, someone tell me, what are all the rates for all the levels and
BuyType from EUR as sell?
Then that means I have to send back all the EUR as sell type.

Or, if someone say, what are all the rates for all the buytype for USD
from EUR as sell?
Then that means i have to send back all the EUR as sell, and USD for
Buy.

Or, if someone say, what are all the rates for all the buytype as GBP?
Then, i will have to send back all the buytype as GBP (including all
levels)

Or someone can just ask for a specific level as well for any buy type
of sell type, or both.

I was thinking about hash of hash... but if i have the Sell type as key
of the outer hash... then the inner hash will need to have a buytype as
the key... but then, i will have multiple levels...if i put the
multiple levels in an array of an object, and this object as the value
of this inner hash, that should be fine... but i am worry about the
speed.

Ideas?

thanks,
T

Reply to this Message

Manish Pandit - 19 Sep 2006 04:07 GMT

Hi,

This got me thinking real hard :)

You can have a hashmap with the sell currency as key, and the value
could be another hashmap with buy currency as key, and value as a
2-dimensional array of range and rate.

This will satisfy queries to your system with minimal performance hit,
and also keep the complexity from going out of hand.

HashMap<String,HashMap<String,String[n][m]>

Your 2-d array will have n and m size where n = number of ranges and m
= 1

like

USD -> GBP -> [Level 1] 1
[Level 2] 1.5

-> LRA -> [Level 1] 2
[Level 2] 3

Hope this helps!

-cheers,
Manish

Reply to this Message

tak - 19 Sep 2006 14:25 GMT

Hi,

I was thinking about the something similar as well, but instead of an
array, i am thinking of using a linked list.

Just b/c i dont know how many levels there are.

But that also mean, when I insert a new rate - i need to add it to the
proper place, in order to keep an ordered list.

as far as efficiency goes - that wouldnt be so bad, right?

Thanks,
T

> Hi,
>
[quoted text clipped - 24 lines]
> -cheers,
> Manish

Reply to this Message

Michael Rauscher - 20 Sep 2006 10:23 GMT

tak schrieb:

> Hi,
>
> I was thinking about the something similar as well, but instead of an
> array, i am thinking of using a linked list.

First of all, let me define an entry as something that consists of two
currencies, a level and a rate. Let's consider we're managing a list of
entries.

Depending on which keys you want to use to retrieve the data, I'd create
some indices.

One for the selling currency, one for the buying currency, one for both.

e. g.
HashMap<String, Entry> sellIndex;
HashMap<String, Entry> buyIndex;
HashMap<Pair<String,String>, Entry> currenciesIndex;

where Pair is a type that represents - a pair :)

Let's have a look at the levels. If you've to assign a level to an entry
from a (pre-/user)defined set of levels and if you only want to find the
entries that match a given level then it's easy:

HashMap<Level, Entry> levelIndex;
or
HashMap<Pair<String,Level>, Entry> sellLevelIndex;
HashMap<Pair<String,Level>, Entry> buyLevelIndex;

But if you need to know which entries match a specific sell amount (give
me all entries where the level covers a sell amount of 1500) it could
get a bit harder - depending on how many levels exist.

If there are just a few levels, a naive search should be enough to find
the appropriate level from the (pre-/user)defined set. One found the
level you can apply it to XXXlevelIndex.

Otherwise I'd suggest a tree whereas I've to mention that managing this
tree is not a trivial task if levels may overlap. Since levels are
ranges you'd have to split/merge them at the time you modify the tree.

As you can see it could get really complex, so perhaps you should
consider using an in memory database yet.

Just some food for thought

Michael

Reply to this Message

Furious George - 19 Sep 2006 15:21 GMT

> hi,
>
[quoted text clipped - 3 lines]
> this table is about foreigncy exchange. i will have a buy currency,
> sellcurrency, levels, and rate.

This suggests a relational database. My pseudo-SQL.

CREATE TABLE exchange(buy,sell,level,rate)

> A transaction involves from a BUY currency to Sell currency, and it can
> have multiple levels, meaning... if the sell amount is 1000, the rate
[quoted text clipped - 41 lines]
> BuyType from EUR as sell?
> Then that means I have to send back all the EUR as sell type.

SELECT buy , level , rate FROM exchange WHERE sell=EUR ;

> Or, if someone say, what are all the rates for all the buytype for USD
> from EUR as sell?
> Then that means i have to send back all the EUR as sell, and USD for
> Buy.

SELECT level , rate FROM exchange WHERE buy=USD AND sell=EUR ;

> Or, if someone say, what are all the rates for all the buytype as GBP?
> Then, i will have to send back all the buytype as GBP (including all
> levels)

SELECT sell , level , rate FROM exchange WHERE buy=GBP ;

> Or someone can just ask for a specific level as well for any buy type
> of sell type, or both.

SELECT rate FROM exchange WHERE buy=b AND sell=s AND level=l ;

> I was thinking about hash of hash... but if i have the Sell type as key
> of the outer hash... then the inner hash will need to have a buytype as
[quoted text clipped - 4 lines]
>
> Ideas?

Why worry about this cr*p? Someone else has already taken care of it
for you. This is what databases are for. If you try to implement
something yourself, you will (no matter how smart you are) invariably
f*ck up your first attempt. Why go through that pain?

> thanks,
> T

Reply to this Message

tak - 19 Sep 2006 19:09 GMT

> Why worry about this cr*p? Someone else has already taken care of it
> for you. This is what databases are for. If you try to implement
> something yourself, you will (no matter how smart you are) invariably
> f*ck up your first attempt. Why go through that pain?

Simply b/c there will be too much read / write and too slow at every
second if storing it in database. Do you really think that real time
data are stored in a database? For example, if you go to any real-time
streamer that contains real time stock quotes --- do you think that
they actually get it from the database every milli-second /
nano-seconds when there is a new quote, and display it on the screen
for you?

No - real time data - they store it in the machine's memory, for the
speed.

Same as forex, the rates changes all the time. it will be too expensive
to waste that much IO...

database may be good for storing historical data. but definitely not
something that changes at milliseconds or nanoseconds.

Ask a friend who works for a trading or IB company... they will tell
you why "we" go thru this so-call pain.

Thanks.
T

Reply to this Message

Furious George - 20 Sep 2006 00:16 GMT

> > Why worry about this cr*p? Someone else has already taken care of it
> > for you. This is what databases are for. If you try to implement
[quoted text clipped - 11 lines]
> No - real time data - they store it in the machine's memory, for the
> speed.

There are memory based databases as well as hard drive based databases.
There are also tape based databases. The memory based databases are
(for obvious reasons) faster than the other two.

> Same as forex, the rates changes all the time. it will be too expensive
> to waste that much IO...
[quoted text clipped - 4 lines]
> Ask a friend who works for a trading or IB company... they will tell
> you why "we" go thru this so-call pain.

Even if your memory comment was true, I don't see why you should go
through this. Why not just buy the solution from the trading or IB
company friend?

> Thanks.
> T

Reply to this Message

tak - 20 Sep 2006 15:13 GMT

> Even if your memory comment was true, I don't see why you should go
> through this. Why not just buy the solution from the trading or IB
> company friend?

b/c it is expensive to buy, and maintenance..etc.. i did look at some
mem db packages, like, memcached... considering it.

Thanks,
T

Reply to this Message

kevin cline - 20 Sep 2006 06:19 GMT

> hi,
>
[quoted text clipped - 3 lines]
> this table is about foreigncy exchange. i will have a buy currency,
> sellcurrency, levels, and rate....

> I was thinking about hash of hash... but if i have the Sell type as key
> of the outer hash... then the inner hash will need to have a buytype as
[quoted text clipped - 4 lines]
>
> Ideas?

Any reasonable structure should be fast enough, given that you have
already decided to write your application in Java instead of a language
that gives you complete control over data structure design. So first
write something relatively simple using nested hash tables, and see if
it is fast enough. How fast does it have to be, in lookups per second?

Reply to this Message

which data structure best fits this?

Free Magazines