Software Data Structure

From GM-RKB
Jump to navigation Jump to search

A Software Data Structure is a software component that organizes data items (through storage formats and access operations).

References

2018

  • (Wikipedia, 2018) ⇒ https://en.wikipedia.org/wiki/data_structure Retrieved:2018-8-13.
    • In computer science, a data structure is a data organization and storage format that enables efficient access and modification. [1] [2] More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

2018

2014

2013a

  1. ↑ Black (ed.), Paul E. (2004-12-15). Entry for data structure in Dictionary of Algorithms and Data Structures. Online version. U.S. National Institute of Standards and Technology, 15 December 2004. Retrieved on 2009-05-21 from http://xlinux.nist.gov/dads/HTML/datastructur.html.
  2. ↑ Encyclopædia Britannica (2009). Entry data structure in the Encyclopædia Britannica (2009). Retrieved on 2009-05-21 from http://www.britannica.com/EBchecked/topic/152190/data-structure.
  3. ↑ Paul E. Black (ed.), entry for data structure in Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 15 December 2004. Online version Accessed May 21, 2009.
  4. ↑ Entry data structure in the Encyclopædia Britannica (2009) Online entry accessed on May 21, 2009.

2013b

  • (Wikipedia, 2013) ⇒ http://en.wikipedia.org/wiki/Thread_(computing)#Concurrency_and_data_structures Retrieved:2013-11-30.
    • Threads in the same process share the same address space. This allows concurrently running code to couple tightly and conveniently exchange data without the overhead or complexity of an IPC. When shared between threads, however, even simple data structures become prone to race conditions if they require more than one CPU instruction to update: two threads may end up attempting to update the data structure at the same time and find it unexpectedly changing underfoot. Bugs caused by race conditions can be very difficult to reproduce and isolate.

      To prevent this, threading APIs offer synchronization primitives such as mutexes to lock data structures against concurrent access. On uniprocessor systems, a thread running into a locked mutex must sleep and hence trigger a context switch. On multi-processor systems, the thread may instead poll the mutex in a spinlock. Both of these may sap performance and force processors in SMP systems to contend for the memory bus, especially if the granularity of the locking is fine.

2013c

  • http://en.wikibooks.org/wiki/Data_Structures/Introduction
    • Computers can store and process vast amounts of data. Formal data structures enable a programmer to mentally structure large amounts of data into conceptually manageable relationships.

      Sometimes we use data structures to allow us to do more: for example, to accomplish fast searching or sorting of data. Other times, we use data structures so that we can do less: for example, the concept of the stack is a limited form of a more general data structure. These limitations provide us with guarantees that allow us to reason about our programs more easily. Data structures also provide guarantees about algorithmic complexity — choosing an appropriate data structure for a job is crucial for writing good software.

      Because data structures are higher-level abstractions, they present to us operations on groups of data, such as adding an item to a list, or looking up the highest-priority item in a queue. When a data structure provides operations, we can call the data structure an abstract data type (sometimes abbreviated as ADT). Abstract data types can minimize dependencies in your code, which is important when your code needs to be changed. Because you are abstracted away from lower-level details, some of the higher-level commonalities one data structure shares with a different data structure can be used to replace one with the other.

      Our programming languages come equipped with a set of built-in types, such as integers and floating-point numbers, that allow us to work with data objects for which the machine's processor has native support. These built-in types are abstractions of what the processor actually provides because built-in types hide details both about their execution and limitations.

      For example, when we use a floating-point number we are primarily concerned with its value and the operations that can be applied to it. Consider computing the length of a hypotenuse: :[math]\displaystyle{ let c := sqrt(a * a + b * b) }[/math] The machine code generated from the above would use common patterns for computing these values and accumulating the result. In fact, these patterns are so repetitious that high-level languages were created to avoid this redundancy and to allow programmers to think about what value was computed instead of how it was computed.

      Two useful and related concepts are at play here:

      • Encapsulation is when common patterns are grouped together under a single name and then parameterized, in order to achieve a higher-level understanding of that pattern. For example, the multiplication operation requires two source values and writes the product of those two values to a given destination. The operation is parameterized by both the two sources and the single destination.
      • Abstraction is a mechanism to hide the implementation details of an abstraction away from the users of the abstraction. When we multiply numbers, for example, we don't need to know the technique actually used by the processor, we just need to know its properties.

        A programming language is both an abstraction of a machine and a tool to encapsulate-away the machine's inner details. For example, a program written in a programming language can be compiled to several different machine architectures when that programming language sufficiently encapsulates the user away from any one machine.

    • In this book, we take the abstraction and encapsulation that our programming languages provide a step further: When applications get to be more complex, the abstractions programming languages become too low-level to effectively manage. Thus, we build our own abstractions on top of these lower-level constructs. We can even build further abstractions on top of those abstractions. Each time we build upwards, we lose access to the lower-level implementation details. While losing such access might sound like a bad trade off, it is actually quite a bargain: We are primarily concerned with solving the problem at hand rather than with any trivial decisions that could have just as arbitrarily been replaced with a different decision. When we can think on higher levels, we relieve ourselves of these burdens.

      Each data structure that we cover in this book can be thought of as a single unit that has a set of values and a set of operations that can be performed to either access or change these values. The data structure itself can be understood as a set of the data structure's operations together with each operation's properties (i.e., what the operation does and how long we could expect it to take).

2009a

2009b

2004

Retrieved from "http://www.gabormelli.com/RKB/index.php?title=Software_Data_Structure&oldid=920607"