Talk:Array (data structure): Difference between revisions

Revision as of 21:49, 17 May 2009

Revision as of 21:53, 17 May 2009

Line 207:

:::Ok, that seems reasonable but I'm a bit iffy on the proposed page titles/nomenclature. I would have thought that the datatype article would cover the low-level view and the structure article would cover the high-level view, since datatypes are generally lower-level than data structures.--[[User:Cybercobra|Cybercobra]] ([[User talk:Cybercobra|talk]]) 09:13, 12 May 2009 (UTC)

::::Funny, I have exaclty the opposite view ( perhaps for being in the other hemisphere? 8-). To me, data structures are low-level, language-independent concepts that existed well before high-level languages and type systems, and can be perfectly described, implemented and analyzed without ever using the word "type". (That was indeed a conscious decision that Knuth made in the ACP books. Perhaps not good for marketing, but made for a more concrete and precise view.) Data types are high-level concepts that exist only within a specific programming language and its compiler, and were invented precisely to hide the implementation details of data strcutures such as integers, arrays, records, strings, etc.. Thus, for example, the distinction between signed and unsigned integers is meaningful mostly when discussin data types in particular languages; as data structures, they are the same (N-bit arrays packed into a word so that the ADD instruction can operate on them). When implementing a data structure in a high level language, one must necessarily do so through that language's type abstractions, but that does not mean that the data strcuture is built "from" the data types -- rather, it is built "through" them, or even "emulated" with them.<br/>Perhaps you are thinking of "abstract data type" and "abstract data structure", which are the same concept (as far as I can tell) but quite distinct from both "data type" and "data structure". ADTs are theoretical concepts, much as real numbers or linear operators. All the best, --[[User:Jorge Stolfi|Jorge Stolfi]] ([[User talk:Jorge Stolfi|talk]]) 18:17, 12 May 2009 (UTC)

:::::I agree with Jorge Stolfi. "Data type" tells you what operations are supported, but not how. So you can have a data type of finite sets, supporting element insertion and deletion and test for membership. This data type has many possible implementations, which have different efficiency characteristics. It is possible that a processor directly realizes the operations of a given data type, but that is only exceptionally hethe case. A "data structure" specifies a specific way of laying out the storage of a container data type in linear RAM memory using pointers and such, thereby giving an implementation for that data type. For example, the article [[Heap (data structure)]] tells us: "The several variants of heaps are the prototypical most efficient implementations of the [[abstract data type]] [[priority queue]]s." &nbsp;--[[User talk:Lambiam|Lambiam]] 21:49, 17 May 2009 (UTC)

== Abstract array axioms ==