Jump to content
  • Advertisement
Sign in to follow this  
Rydinare

Design Question: Infinite Streams of Integers

This topic is 3727 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey guys. A friend of mine was chatting with me earlier about a problem he was trying to resolve and what might be the best way to design something like this. I gave him a few ideas but was curious if there might be brighter solutions. To make it simplistic, I'll give the more basic question, since this is the starting point for what he was trying to do. The question he asked was basically that say you're provided with N streams of integers that, hypothetically, will always have data when read from. Each read operation should result in a single integer. He was asking how you could continually read from the streams and output to an output stream, having it always be in sorted order in the resulting output stream. Your thoughts?

Share this post


Link to post
Share on other sites
Advertisement
int last = 0;

while (true)
{
int x = read ();
if (x > last)
{
write(x);
last = x;
}
}


Yes, this does discard integers, but since the input stream is infinite this isn't a problem.

Share this post


Link to post
Share on other sites
I don't see the problem. Just create a stream, based on either a queue or a list or some other datatype with similar functionality, and add elements to it? Maintaining a sorted list is not much harder; just do a binary search when inserting a new number.

Share this post


Link to post
Share on other sites
Quote:
Original post by Rydinare

He was asking how you could continually read from the streams and output to an output stream, having it always be in sorted order in the resulting output stream.


Think about it:

- How can you sort an infinite amount of numbers?

And if your question applies to streams of arbitrary length, with limited working memory, then the good old polyphase sort or something similar would do the job.


The other solution is to use counting sort. Let your output stream be collection of buckets, each containing counts for each integer. When outputting to this stream, increment corresponding member. If you overflow either the buckets, or the counts, increment precision appropriately by resizing the container.

Sorting here is implicit - when you need that information, simply parse the current state, emitting appropriate number of values while traversing the buckets.

PS: later solution requires Turing machine with infinite tape to function properly, but hardware prices are going down all the time, and infinite tape sells for $0.99 per megabyte these days.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Quote:
Original post by Rydinare

He was asking how you could continually read from the streams and output to an output stream, having it always be in sorted order in the resulting output stream.


Think about it:

- How can you sort an infinite amount of numbers?

And if your question applies to streams of arbitrary length, with limited working memory, then the good old polyphase sort or something similar would do the job.


The other solution is to use counting sort. Let your output stream be collection of buckets, each containing counts for each integer. When outputting to this stream, increment corresponding member. If you overflow either the buckets, or the counts, increment precision appropriately by resizing the container.

Sorting here is implicit - when you need that information, simply parse the current state, emitting appropriate number of values while traversing the buckets.

PS: later solution requires Turing machine with infinite tape to function properly, but hardware prices are going down all the time, and infinite tape sells for $0.99 per megabyte these days.


Interesting. Very interesting. I just forwarded your answer to my friend, so I'll let you know what he thinks when he responds. [smile]

Share this post


Link to post
Share on other sites
The cheeky answer:

Assuming positive integers, if we discard (for convenience) multiple instances of the same number, then the final result must be the set of integers, in order. Putting multiples back in, the result is an infinite amount of 1's, followed by an infinite number of 2's, etc...

Unless you need the intermediate states, there's no need to compute anything.



Share this post


Link to post
Share on other sites
Quote:
Original post by Valere
The cheeky answer:

Assuming positive integers, if we discard (for convenience) multiple instances of the same number, then the final result must be the set of integers, in order. Putting multiples back in, the result is an infinite amount of 1's, followed by an infinite number of 2's, etc...

Unless you need the intermediate states, there's no need to compute anything.


What if the input streams only return a small subset of the possible integers? The fact that they're infinite has nothing to do with the set of integers they contain.

Share this post


Link to post
Share on other sites
You're right, the answer would be the set of possible integers from the input stream, sorted in order. Thanks to infinity, as long as the chance of any given input is non-zero, it would appear in the final set, so the distribution of inputs is unimportant.

Share this post


Link to post
Share on other sites
If you sort a stream of infinite integers with at least some guaranteed/statistical % of elements of a minimum representable value, the output stream will begin with those elements sorted to the start.

Since there are an infinity of those elements, your output stream's read function can simply be hardcoded to always return whatever the minimum possible value is.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nypyren
If you sort a stream of infinite integers with at least some guaranteed/statistical % of elements of a minimum representable value, the output stream will begin with those elements sorted to the start.

Since there are an infinity of those elements, your output stream's read function can simply be hardcoded to always return whatever the minimum possible value is.


Hmm, I think you nailed it. He wrote back and said that his streams would be sorted, so sorting to the output stream is trivial because you just compare first elements of all the streams. Well done. [smile]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!