# 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.

## 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 on other sites
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 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 on other sites
Quote:
 Original post by RydinareHe 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.

- 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 RydinareHe 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 on other sites

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 on other sites
Quote:
 Original post by ValereThe 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 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 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 on other sites
Quote:
 Original post by NypyrenIf 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]

1. 1
2. 2
Rutin
22
3. 3
4. 4
5. 5
frob
12

• 9
• 17
• 9
• 31
• 16
• ### Forum Statistics

• Total Topics
632617
• Total Posts
3007450

×