Purely functional data structure: Difference between revisions

Revision as of 20:43, 30 September 2017

Revision as of 21:04, 30 September 2017

Line 36:

In general, having inefficient operations is not acceptable for persistent data structures, because this very operation can be called many times. It is not acceptable either for real-time or for imperative systems, where the user may require the time taken by the operation to be predictable. Furthermore, this unpredictability complicates the use of [[Parallel computing|parallelism]].

In order to avoid those problems, some data structures allow for the inefficient operation to be postponed—this is called [[Scheduling (computing)|scheduling]]. The only requirement is that the computation of the inefficient operation should end before its result is actually needed. A constant part of the inefficient operation is performed simultaneously with the following call to an efficient operation, so that the inefficient operation is already totally done when it is needed, and each individual operation remains efficient.{{clarify|date=September 2017}}

====Example: queue====