Re: Algorithm to find pairs in array [can not order]
Thanks for your answer,
Patricia Shanahan wrote:
There is a quick halving of the work. The inner loop does not need to
begin from index 1. It can start from i+1, because any match between a
pair either of which has an index value less than i would have been
found on a previous outer loop iteration.
If you look closely at the end of the inner loop I remove the matched
objects from the list:
offeredOptions.remove(i);
offeredOptions.remove(j);
One think that I missed to add is the instruction
i=0 ;
After the pair is found.
// shuffle Option offers
Collections.shuffle(offeredOptions);
for (int i=0;i<offeredOptions.size()-1;i++)
{
Offer of1 = offeredOptions.get(i);
// look for a matching option offer in the list
for (int j=1;j<offeredOptions.size();j++)
{
Offer of2 = offeredOptions.get(j);
/* we are looking for 2 offers for the same Option contract with
opposite
* offer types (write and hold)
*/
if (of1.getOption() == of1.getOption() &&
(of1.type == OfferType.hold && of2.type ==
OfferType.write) ||
(of1.type == OfferType.write && of2.type ==
OfferType.hold))
{
offeredOptions.remove(i);
offeredOptions.remove(j);
// do something else
...
// ...
i=0; // THIS WAS LEFT OUT IN THE PREVIOUS
POST
break; // get to the i loop
}
}
}
So basically I remove the matched objects AND start from the begginning
of the resulting list
(and compare the object 0 to the object 1,2,3...).
If you rely on direct comparison, using the unordered array, the work is
going to be O(n*n).
The issue is that the matching of pairs *must* be random, as it is
possible to have 2 objects [offers]
that match a third one, and the selection of the 2 to be matched has to
be random (if you have not
infered from the code, it is some kind of random clearing between
traders).
What is the type of a getOption() result? Can there be more than two
offers with the same contract?
Basically, getOption() returns an object with the type Option which is
a kind of contract, there CAN be two offers (made by different traders)
with the same contract (as the Option object lists just a *type* of
contract, and there could be several offers with the same *type* of
contract, the type of contract is defined by some parameters in the
Option class)].
And then, what will make two offers match (as stated in the code) is to
have the SAME Option type (hence the comparisson of the two getOption
objects) AND that the offers have opposite positions ('write' and
'hold' which can be seen as sell and buy the contract).
Depending on those answers, there may be much more efficient solutions
for large n in which the data gets copied to a HashSet or HashMap during
the search.
Patricia
At the end I believe given the restrictions a O(n*n) is the best I can
achieve. Not that it is wrong but I thought something better could be
done.
Thank you again!
Omar