Precomputation: Difference between revisions

Revision as of 20:46, 22 August 2014

Revision as of 20:49, 22 August 2014

Line 3:

In [[algorithms]], '''precomputation''' is the act of performing an initial [[computation]] before [[Run time (program lifecycle phase)|run time]] to generate a [[lookup table]] that can be used by an algorithm to avoid repeated computation each time it is executed. Precomputation is often used in algorithms that depend on the results of expensive computations that don't depend on the input of the algorithm. A trivial example of precomputation is the use of [[hardcoded]] mathematical constants, such as [[Pi|π]] and [[E (mathematical constant)|e]], rather than computing their approximations to the necessary precision at run time.

In [[database]]s, the term '''materialization''' is used to refer to storing the results of a precomputation.,<ref name="HanKamber2011">{{cite book|author1=Jiawei Han|author2=Micheline Kamber|title=Data Mining: Concepts and Techniques: Concepts and Techniques|url=http://books.google.com/books?id=pQws07tdpjoC&pg=PA159|date=9 June 2011|publisher=Elsevier|isbn=978-0-12-381480-7|page=159}}</ref><ref name="Groppe2011">{{cite book|author=Sven Groppe|title=Data Management and Query Processing in Semantic Web Databases|url=http://books.google.com/books?id=HdVZ2MhzP_4C&pg=PA178|date=29 April 2011|publisher=Springer Science & Business Media|isbn=978-3-642-19357-6|page=178}}</ref> e.g. in a [[materialized view]].<ref name="MortonOsborne2013">{{cite book|author1=Karen Morton|author2=Kerry Osborne|author3=Robyn Sands|coauthors=Riyaj Shamsudeen, Jared Still|title=Pro Oracle SQL|url=http://books.google.com/books?id=XUPXAQAAQBAJ&pg=PA48|date=28 October 2013|publisher=Apress|isbn=978-1-4302-6220-6|page=48}}</ref>

== Overview ==

Line 55:

* [[Algorithmic efficiency]]

* [[Partial evaluation]]

* [[materialized view]]

== References ==