Jump to content

  • Log In with Google      Sign In   
  • Create Account

Data pair searchable structure


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 Tasche   Members   -  Reputation: 222

Like
0Likes
Like

Posted 04 February 2013 - 02:06 PM

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, 04 February 2013 - 02:10 PM.


Sponsor:

#2 ApochPiQ   Moderators   -  Reputation: 16423

Like
0Likes
Like

Posted 04 February 2013 - 02:13 PM

What language are you planning on implementing this in?

#3 swiftcoder   Senior Moderators   -  Reputation: 10446

Like
1Likes
Like

Posted 04 February 2013 - 04:38 PM

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>>)

Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#4 Yrjö P.   Crossbones+   -  Reputation: 1412

Like
0Likes
Like

Posted 05 February 2013 - 08:24 AM

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.

#5 Tasche   Members   -  Reputation: 222

Like
1Likes
Like

Posted 06 February 2013 - 03:02 PM

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)






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS