Data
Home * Programming * Data
Data is anything in a form suitable for use with a computer to represent information or knowledge. Bits, bytes, characters, strings, numbers, codes, sets, sequences and structures, as well as references (pointers, addresses) to related data, retrievable stored in memory of any kind of hardware.
A variable in the context of programming languages, associates a symbolic name with a memory address.
Contents
Processor's View
From processor's point of view, an atomic fixed sized data item with a unique memory address is a primitive data item, today usually with a size of one, two, four, or up to eight bytes, sometimes even 16 or 32 bytes. One of these data items may represent numbers in various formats and value ranges, finite sets, codes like a character of a text or a piece on the chessboard, or even instruction codes and memory addresses. It fits into one processor register and is subject of arithmetical or logical operations, or, if interpreted as (part of an) address, to perform random memory access, that is to store and retrieve primitive data items. Program code is decoded and interpreted as instruction to control the combinatorial and sequential logic while executing a program within its processor, usually distinct from application specific data, if the application is not an assembler, compiler or debugger or anything related to self-modifying code or self-replication [2] .
A collection of primitive data types, located consecutively in memory may be accessed relative to the address of its first element via another data item, an index, or - specially if the primitive data items have different sizes, via constant offsets. From machine perspective, this covers array (vector) and structure, while the latter may be interpreted as concrete implementation of abstract objects.
Lifetime of Data
Data may resist in persistent non-volatile memory or volatile random-access memory. The lifetime of volatile data depends on the data declaration of various programming languages, in C related to storage class specifiers [3] .
Static Data
Global or static data as determined and may be initialized at compile time requires static memory allocation. Static data resides in an object file or in segmentated memory in a data- or bss-segment, dependent on their initialization. For instance, some chess programs keep material- and other lookup tables initialized in their object file and data segment, for huge tables likely by generated source code with appropriate data declarations and static initialization. Assuming the initialization code is (much) shorter than the generated data, others prefer to reduce the size of the object file to initialize stuff located in the bss-segment or elsewhere after program startup.
Dynamic Data
Dynamic data is created during the runtime of a process, it might be allocated from a memory pool (heap), and freed if no longer needed, depending on the framework or programming languages, either explicitly, or implicitly by garbage collection.
Automatic Data
Automatic data and variables like local variables and actual parameters have a limited lifetime inside the scope of a subroutine or block. Automatic variables either reside on the processor stack, or inside a processor register.
Algorithms + Data
Data structures are inherently related to algorithms and their efficiency, as for instance elaborated by Niklaus Wirth in Algorithms + Data Structures = Programs [4] .
Primitive Types
General Purpose
Chess Specific
Scalar integers as numbers, enumerations or simple structures related to Chess and Search basics.
Structured Data
General Purpose
- Array
- De Bruijn Sequence
- Hash Table
- Linked List
- Priority Queue
- Queue (FIFO)
- Stack (LIFO)
Chess Specific
- Attack and Defend Maps
- Butterfly Boards
- Move List
- Piece-Lists
- Search Tree
- Transposition Table
- Triangular PV-Table
Persistent Data
- Chess Databases
- Endgame Bitbases
- Endgame Tablebases
- Extended Position Description (EPD)
- Forsyth-Edwards Notation (FEN)
- Opening Book
- Persistent Hash Table
- Portable Game Notation (PGN)
Endianness
See also
Publications
1960 ...
- Georgy Adelson-Velsky, Evgenii Landis (1962). An algorithm for the organization of information. Proceedings of the USSR Academy of Sciences, 146: 263–266. (Russian) English translation by Myron J. Ricci in Soviet Mathematics Doklady, No. 3 [5]
1970 ...
- Burton H. Bloom (1970). Space/time trade-offs in hash coding with allowable errors. Comm. of the ACM, Vol. 13, No. 7, pdf [6]
- Niklaus Wirth (1976). Algorithms + Data Structures = Programs
1980 ...
- Guy Jacobson (1989). Succint Static Data Structures. Ph.D. thesis, Carnegie Mellon University, CMU-CS-89-112, pdf
- Guy Jacobson (1989). Space-efficient Static Trees and Graphs. SFCS'89, pdf
1990 ...
- Keith E. Gorlen, Sanford M. Orlow, Perry S. Plexico (1990). Data abstraction and object-oriented programming in C++. Wiley [7] [8] » C++
- Bernhard Balkenhol (1994). Data Compression in Encoding Chess Positions. ICCA Journal, Vol. 17, No. 3, zipped ps » Chess Position
- Robert Levinson (1994). UDS: A Universal Data Structure. UCSC CRL-94-15
- Leen Ammeraal (1996). Algorithms and Data Structures in C++. ISBN 0-471-96355-0, Chichester: John Wiley
- Liwu Li (1998). Java - Data Structures and Programming. Springer
2000 ...
- Julio César Hernández-Castro, Ignacio Blasco-López, L.Javier Garcéa-Villalba (2004). Hiding Data in Games. ICGA Journal, Vol. 27, No. 2
- Julio César Hernández-Castro, Ignacio Blasco-López, Juan M. Estevez-Tapiador, Arturo Ribagorda-Garnacho (2006). Steganography in games: A general methodology and its application to the game of Go. Computers & Security, Vol. 25, pdf [9]
- Erik D. Demaine, Dion Harmon, John Iacono, Mihai Pătrașcu (2007). Dynamic Optimality—Almost. SIAM Journal on Computing, Vol. 37, No. 1 [10]
- Carl Burch, Data & Procedure. On-line Book
- Kurt Mehlhorn, Peter Sanders (2008). Data Structures and Algorithms: The Basic Toolbox. Springer, ISBN 978-3540779773
- Denis Xavier Charles, Kumar Chellapilla (2008). Bloomier Filters: A Second Look. ESA 2008 [11]
- Anthony Cozzie, Frank Stratton, Hui Xue, Samuel T. King (2008). Digging for Data Structures. OSDI 2008, pdf
- Felix Putze, Peter Sanders, Johannes Singler (2009). Cache-, hash-, and space-efficient bloom filters. ACM Journal of Experimental Algorithmics Vol. 14
2010 ...
- Erik D. Demaine, John Iacono, Stefan Langerman, Özgür Özkan (2013). Combining Binary Search Trees. arXiv:1304.7604
- Erik D. Demaine, John Iacono, Grigorios Koumoutsos, Stefan Langerman (2019). Belga B-trees. arXiv:1903.03560
External Links
- Data (computing) from Wikipedia
- Data (disambiguation) from Wikipedia
- Information from Wikipedia
- Lookup table from Wikipedia
- Cache from Wikipedia
- Data type from Wikipedia
- Initialization from Wikipedia
- Data compression from Wikipedia
- Data segment from Wikipedia
- Addressing mode from Wikipedia
- Data structure from Wikipedia
- Succinct data structure from Wikipedia
- List of data structures from Wikipedia
- Dictionary of Algorithms and Data Structures by Paul E. Black, National Institute of Standards and Technology
- Dictionary of Algorithms and Data Structures from Wikipedia
- Data Structures and Programming Lecture 1 by Steven S. Skiena
- Serialization from Wikipedia
- Marshalling (computer science) from Wikipedia
- Data mining from Wikipedia
- Star Trek TNG: S5E14 Conundrum, Deanna Troi beats Data in Tri-D Chess, YouTube Video
References
- ↑ History of Economics Playground - October « 2008
- ↑ Reflections on Trusting Trust ACM Classic by Ken Thompson
- ↑ Storage-Class Specifiers from MSDN Library
- ↑ Niklaus Wirth (1976). Algorithms + Data Structures = Programs
- ↑ AVL tree from Wikipedia
- ↑ Bloom filter from Wikipedia
- ↑ NIH Class Library — Software Preservation Group, The Computer History Museum
- ↑ NIH Class Library Revision 3.0 - Release Notes (pdf)
- ↑ steganography from Wikipedia
- ↑ Tango tree from Wikipedia
- ↑ Bloom filter - Bloomier filters from Wikipedia