Sign in to follow this  
Tasche

Data pair searchable structure

Recommended Posts

Hello gamedevs!

i'm pretty sure this has been asked a million times before, but i couldn't come up with search keywords (which you probably can tell by the awkward topic title)
following problem:

i have got a set M of arbitrary data values of the same type.
now i have some random algorithm which pairs them up and puts them into a list, obeying the rule that although a data value may appear in several pairs, the symmetric counterpart (e.g. for the pair values <A,B>, with A,B in M, this would be the pair <B,A>) should not. also, no pair should appear twice.

the elements have, needless to say, no intrinsic ordering relation (else you could sort the pair to have the smaller always first, and would only need to check for the this item when looking if it already exists).

the obvious approach would be to search the entire list first item for A, and check if the pairing with B exists, then search the list's first item for B, and check if the pairing with A exists. if not, add the pair.

i am aware that in programming, you can always define an ordering relation by interpreting the data as a stream of 0 and 1, and use the induced ordering, but it seems so weak a solution. this problem just 'feels' like it can be solved more elegantly. if an ordering were used, what would be the quickest way? the one i mentioned using a sorted list?

i also hope i haven't offended anyone (or perhaps even clouded the question and/or assumptions) by my horrible translation of german math lingo into english.

cheers,
tasche Edited by Tasche

Share this post


Link to post
Share on other sites

i am aware that in programming, you can always define an ordering relation by interpreting the data as a stream of 0 and 1, and use the induced ordering, but it seems so weak a solution. this problem just 'feels' like it can be solved more elegantly.

It's purely an implementation artefact, though. I'm not sure elegance is really the correct criteria to apply.

if an ordering were used, what would be the quickest way? the one i mentioned using a sorted list?

I'd probably go for a hash map of pairs, and check whether the reverse pair was already there before inserting. A hash map saves quite a bit of time complexity versus a sorted list - the insert becomes O(1) versus O(log n), not to mention that you don't need to sort it in the first place.

(in C++ that'd be something like a std::unordered_set<std::pair<A, B>>)

Share this post


Link to post
Share on other sites
You could store all pairs ordered by min(A,B) and with every pair store a boolean that tells whether the values of that pair are reversed. That way you would not have to search twice for a read or write operation. Some variant of balanced binary search tree, like a red-black tree would be fine for this. In C++ std::map is implemented like that.

Share this post


Link to post
Share on other sites

You could store all pairs ordered by min(A,B) and with every pair store a boolean that tells whether the values of that pair are reversed. That way you would not have to search twice for a read or write operation. Some variant of balanced binary search tree, like a red-black tree would be fine for this. In C++ std::map is implemented like that.

min() only works with an ordering relation. i basically used swiftcoder's solution, which uses a map Pair->Value (the hash function), then collapse the buckets into a list. seems to perform well, and i learned something (which, btw, is a key goal of this exercise). this solution is also nicely scalable with respect to the expected data (and its amount), since i get to choose the hash function. most of the time i have lots of elements in M, but only few pairs get generated. +1 for swiftcoder (not that he needs any rep :P)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this