Difference between revisions of "Space-Time Tradeoff"
GerdIsenberg (talk | contribs) (Created page with "'''Home * Programming * Space-Time Tradeoff''' FILE:vortex1_med.jpg|border|right|thumb|link=http://www.physorg.com/news8256.html|Space-time Vortex <ref>[h...") |
GerdIsenberg (talk | contribs) m |
||
Line 62: | Line 62: | ||
* [https://en.wikipedia.org/wiki/Art_of_memory Art of memory from Wikipedia] | * [https://en.wikipedia.org/wiki/Art_of_memory Art of memory from Wikipedia] | ||
* [https://en.wikipedia.org/wiki/Eureka:_A_Prose_Poem Eureka: A Prose Poem from Wikipedia] | * [https://en.wikipedia.org/wiki/Eureka:_A_Prose_Poem Eureka: A Prose Poem from Wikipedia] | ||
− | * [[Videos#KingCrimson|King Crimson]] - [https://en.wikipedia.org/wiki/Thrak One Time], | + | * [[Videos#KingCrimson|King Crimson]] - [https://en.wikipedia.org/wiki/Thrak One Time] (Live In Japan), [https://en.wikipedia.org/wiki/YouTube YouTube] Video |
− | + | : {{#evu:https://www.youtube.com/watch?v=zP2Rs5qHRCQ|alignment=left|valignment=top}} | |
− | : {{#evu:https://www.youtube.com/watch?v= | ||
=References= | =References= |
Revision as of 15:38, 11 May 2018
Home * Programming * Space-Time Tradeoff
Space-Time Tradeoff refers to providing knowledge, information or data, where memory size competes with computation time. This tradeoff is a frequent issue in computer chess programming, for instance low level stuff to calculate or lookup single populated bitboards by square index, or a distance between two squares. Lookup tables are non-volatile tables or initialized once at program startup, various hash tables and caches. Space-time tradeoff is also an issue in determining (almost) perfect knowledge from interior node recognizers by retrograde analysis, that is the application of endgame bit- or tablebases and various compression techniques.
Space-Time Tradeoffs
There are multiple CPW pages where memory competes with computation:
- Bit by Square
- BitScan
- Distance
- Endgame Bitbases
- Endgame Tablebases
- Hash Table
- Kindergarten Bitboards
- KPK
- Legality Test
- Magic Bitboards
- Manhattan-Distance
- Material Tables
- Population Count
- Rotated Bitboards
- Table-driven Move Generation
- The switch Approach
- Transposition Table
See also
- Algorithms
- Best-First
- Data
- Depth-First
- Dispersion and Distortion
- Knowledge
- Learning
- Memory
- Sequential Logic
Publications
- Burton H. Bloom (1970). Space/time trade-offs in hash coding with allowable errors. Comm. of the ACM, Vol. 13, No. 7, pdf [2]
- Albert Zobrist and Frederic Roy Carlson (1977). Detection of Combined Occurrences. Comm. of the ACM, Vol. 20, No. 1, pp. 31-35.
External Links
- Space-time tradeoff from Wikipedia
- Blum's speedup theorem from Wikipedia
- Algorithmic efficiency from Wikipedia
- Shannon entropy from Wikipedia
- Computer memory from Wikipedia
- Cache from Wikipedia
- Lookup table from Wikipedia
- Database from Wikipedia
- Memory management unit from Wikipedia
- Volatile memory from Wikipedia
- Non-volatile memory from Wikipedia
- Random-access memory from Wikipedia
- Read-only memory from Wikipedia
- Memory footprint from Wikipedia
- Moore's law from Wikipedia
- Computation, Memory, Nature, and Life - Is digital storage the secret of life? by John Walker
- Spacetime from Wikipedia
- Philosophy of space and time from Wikipedia
- Einstein Minkowski Space-Time Diagram
- Art of memory from Wikipedia
- Eureka: A Prose Poem from Wikipedia
- King Crimson - One Time (Live In Japan), YouTube Video