2
$\begingroup$

There are some enumeration problems which have little input, except for some termination criterion. Examples for the question at hand would be

  • enumeration of prime numbers in ascending order
  • enumeration of grid points by increasing distance

For these there exist two fundamentally different techniques:

  1. With one class of approaches you have to state the scope of your question up front. You'd state the upper bound for the primes you want, the maximal distance, or similar. The Sieve of Eratosthenes would fall into this category, as would an algorithm enumerating all points in a rectangle and then sorting them by distance.

  2. With another class of approaches, you don't have to state the extent of the required output up front. You can see the enumeration as a lazily evaluated infinite sequence, and feed it to some other part of your code that should eventually terminate the generation once a generated output satisfies your requirements. Testing each odd number against a list of already found primes would be an example from this class.

Now I'm looking for a term to distinguish these two forms. Somehow the latter approach feels closely related to online algorithms, which is why I added that tag. But every deifnition I could find specifies an online algorithm as processing its input incrementally. There is almost no input here, unless you count the one-bit decision between “give me the next item” and “that's it, stop now” as an incremental input. Would calling this an online algorithm be appropriate, or is there a better term?

Improve this question
$\endgroup$
5
  • $\begingroup$ Isn't 2 just lazy evaluation, a term you've already used in the question? $\endgroup$
    – David Richerby
    Jul 5, 2016 at 16:21
  • $\begingroup$ 1) enumerator, sometimes "full iterator" 2) generator (lazy iterator). The 1) is uncommon - it is rather not explicitly stated and moreover "iterator" has second (more popular) meaning as object that accesses iterable results. 2) generator is used to denote program that do not perform full enumeration but commonly function that can be restarted to yield more results. So the names are shadowed... So you want to distinguish "full range checker" from "enough results generator"? $\endgroup$
    – Evil
    Jul 5, 2016 at 17:41
  • $\begingroup$ @DavidRicherby: I don't think “lazy evaluation” is optimal as a distinguishing name. I could evaluate the Sieve of Eratosthenes lazily as well, returning each element once I'm done marking its multiples, and I'd still have to specify the total size of the sieve up front. I feel like I'd need to get the concept of infinity into that term somehow. I guess “lazily evaluated infinite sequence” captures that idea, but it doesn't describe the algorithm. “algorithm generating a lazily evaluated infinite sequence” is beginning to get real bulky, so I hope for something more terse. $\endgroup$
    – MvG
    Jul 5, 2016 at 20:11
  • $\begingroup$ @Evil: Thanks for these suggestions. Is your last sentence a question whether you understood the question correctly? If so I'd say yes, although it's more “fixed range” than “full range” I think. Or are these terms in quotation marks your suggestions for less ambiguous terms? They sound slightly non-technical, but might be perfectly adequate for some contexts, so thanks for these as well. $\endgroup$
    – MvG
    Jul 5, 2016 at 20:23
  • $\begingroup$ Yes, non technical terms to be sure that we are on the same page. And I heard them in this context, but it is just one of possible descriptions. $\endgroup$
    – Evil
    Jul 5, 2016 at 20:30

1 Answer 1

Reset to default
1
$\begingroup$

Informally, you might call this lazy evaluation, or a lazily-evaluated stream.

A $O(f(n))$-time delay algorithm is guaranteed to output a stream of answers, with a delay of at most $O(f(n))$ time between answers. One consequence is that outputting $k$ answers will take at most $O(k \times f(n))$ time -- but you also know that you won't ever have to wait too long for the next output. (So, this helps rule out algorithms that return the first $n$ answers very rapidly and then take a really long time to return the $n+1$th answer).

An output-sensitive algorithm is an algorithm that outputs a stream of answers, and where the running time is some function of the length of the output. Normally we evaluate the running time of an algorithm as a function of the length of the input, but an output-sensitive algorithm is analyzed in terms of the length of the output. That's potentially relevant here. Suppose your goal is to enumerate all fidgets in a warbuggle. If you find an polynomial output-sensitive algorithm for this task, then you have an algorithm that's potentially useful for streaming purposes -- in particular, the average delay between outputs isn't too large (though the worst-case delay could potentially be quite high).

If neither of them captures exactly the concept you have in mind, then I suggest you just describe in text what properties your algorithm has, and don't worry too much about finding a short term for it.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Formally, you might call this codata, and algorithms which progress in this manner are said to coterminate. $\endgroup$
    – Pseudonym
    Jul 6, 2016 at 5:03
  • 1
    $\begingroup$ @Pseudonym: Interesting. It took me a while to find readable references on this, but this blog e.g. was fun to read. But perhaps this would be better as an answer on its own, to be voted upon, than a comment to an answer suggesting other terms? Do you want to post another answer? $\endgroup$
    – MvG
    Jul 6, 2016 at 8:35
  • $\begingroup$ I thought of it, but I wasn't sure that it answers the question asked. $\endgroup$
    – Pseudonym
    Jul 7, 2016 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.