Content deleted Content added
No edit summary |
→clarity: new section |
||
| (42 intermediate revisions by 29 users not shown) | |||
Line 1:
{{
{{WikiProject
{{WikiProject Computer science|importance=Top}}
}}
{{Copied |from=Index (computer science) |from_oldid=470513254 |to=Array data structure |to_diff=470647949 |to_oldid=470644178 |date=17:50, 10 January 2012}}
==array==
Line 67 ⟶ 70:
: Two dimensional slices like <code>Slice (5 .. 20, 5 .. 20)</code> - of course since C/C++ don't support array slices to begin with you won't notice the difference. --[[User:Krischik|Krischik]] <sup>[[User_talk:Krischik|T]]</sup> 11:53, 30 January 2008 (UTC)
: The article goes far enough in allowing that c/c++ supports arrays. Essentially, "c arrays" are just pointers (with weak, compile-time type support) to chunks of memory. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/188.126.207.212|188.126.207.212]] ([[User talk:188.126.207.212|talk]]) 12:46, 16 March 2011 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
== "1-Dimensional or Linear Array" makes no sense ==
Line 196 ⟶ 201:
: Do you have a good example? [[User:Rgrig|Rgrig]] ([[User talk:Rgrig|talk]]) 01:24, 24 April 2009 (UTC)
:: For example, some kinds of [[hash table]] often reduces a number to the appropriate range of array index (the range varies over time with dynamic resizing) with a ''mod'' operator. --[[User:DavidCary|DavidCary]] ([[User talk:DavidCary|talk]]) 08:32, 23 January 2021 (UTC)
== Proposal to split the article ==
Line 222 ⟶ 225:
My idea for fixing the last two bugs was to introduce a "FAIL" value to be the result of accessing an invalid index, and postulate that get(FAIL,I) = set(FAIL,I,V)=FAIL for all I,V; and then remove the phrase "for which the operations are defined". However then the first axiom is violated if ''I'' is an invalid index.<br/>
Does the paper say anythng about these problems? --[[User:Jorge Stolfi|Jorge Stolfi]] ([[User talk:Jorge Stolfi|talk]]) 02:54, 13 May 2009 (UTC)
:The axioms are pretty '''standard''' (at least in the research communities dealing with program correctness), except the names used are typically '''not''' ''get'' and ''set''. Let's take your complaints one by one. (1) Yes, you will need additional axioms to specify ''particular'' types of arrays. These axioms only capture the ''essence'' of an array. (2) Yes, correctness and efficiency are orthogonal issues. (Although there are attempts to analyze efficiency using logic, but they are rather clumsy at the moment.) (3) Yes. Again, they are supposed to be general enough to describe the ''essence'' of what "array" means. (4) No, you are mistaken and I do not see how you reached this conclusion. Finally, regarding your fix: While introducing a special value is certainly possible, note that the current axioms simply ''cannot be applied'' to deduce that something is read from a ___location that was not written, and as such it cannot be proved using this axioms that the read value from an unwritten ___location is constrained in any way. Just Google for "array axioms" and you will find a plethora of resources, pretty much all using the '''same''' axioms. [[User:Rgrig|Rgrig]] ([[User talk:Rgrig|talk]]) 16:58, 10 September 2009 (UTC)
:Also, looking at the history of the article I see that at some point it said that ''I'' stands for a tuple of integers (!!!) and other such nonsensical things. Perhaps it's better it was removed in the end. [[User:Rgrig|Rgrig]] ([[User talk:Rgrig|talk]]) 17:08, 10 September 2009 (UTC)
==Requested move==
<div class="boilerplate" style="background-color: #efe; margin: 2em 0 0 0; padding: 0 10px 0 10px; border: 1px dotted #aaa;"><!-- Template:RM top -->
:''The following discussion is an archived discussion of a [[WP:RM|requested move]]. <span style="color:red">'''Please do not modify it.'''</span> Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section. ''
The result of the move request was '''not moved''' [[User:Aervanath|Aervanath]] ([[User talk:Aervanath|talk]]) 18:10, 25 May 2009 (UTC)
----
Swap [[Array data structure]] and [[Array data type]] — Data types are primitive (e.g. Machine data types), whereas data structures are higher-level and more abstract; therefore, this article, which describes the more low-level concept, is misnamed. See also the section "Proposal to split the article" above. --[[User:Cybercobra|Cybercobra]] ([[User talk:Cybercobra|talk]]) 05:45, 16 May 2009 (UTC)
Line 237 ⟶ 250:
===Discussion===
:''Any additional comments:''
::I say, '''merge''' the articles. Whether you call them types or structures is an implementation detail that varies from language to language. Plenty to be said besides that; whether arrays are treated as a primitive or compound by syntax is not an important enough distinction to merit two different articles. -- [[User:Beland|Beland]] ([[User talk:Beland|talk]]) 06:39, 21 May 2009 (UTC)
:::But the point is that "data structure" is a concept that could (and has been) defined and discussed without ever referring to "programming language", "syntax", or "type system"; whereas "data type" is a concept that exists only in the so-caled "higher programming languages" and cannot be discussed independently of them. This distinction is clear, for example, in Knuth's [[The Art of Computer Programming]], which is still a basic reference in the field, and in Paul E. Black's [http://www.itl.nist.gov/div897/sqg/dads/HTML/datastructur.html NIST Dictionary of Algorithms and Data Structures] (which does not even have an entry for "type"). Data types are abstractions that those languages provide so that programmers can handle memory words and (concrete) data structures with safety and convenience — much as those languages substitute abstract "commands" for "CPU instructions". And "abstract data type" (or "abstract data structure") is an even more abstract thing — a ''mathematical'' concept (like a [[group (mathematics)|group]] or [[graph theory|graph]]) that can be used to model both data structures and data types. Sure, often programmers use "data type" and "data structure" interchangeably, to mean any of those three terms, much as one may say "a wine bottle" when one actually means "a wine bottle full of wine", or describe [[sake]] as "rice wine". Merging [[array data type]] and [[array data structure]] (or [[data type]] and [[data structure]]) is as appropriate as merging [[wine]] and [[wine bottle]]. As the old philosphers would say:
:::::''When I use my finger to point at the Moon, no one would mistake my finger for the Moon. But why is it then, that when I use a word to point to an idea, people so often mistake the word for the idea?'' -- attributed to [[Zhuangzi]], c. 350 BC.
:::All the best, --[[User:Jorge Stolfi|Jorge Stolfi]] ([[User talk:Jorge Stolfi|talk]]) 19:57, 21 May 2009 (UTC)
:''The above discussion is preserved as an archive of a [[WP:RM|requested move]]. <span style="color:red">'''Please do not modify it.'''</span> Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.''</div><!-- Template:RM bottom -->
==Array structure?==
Line 255 ⟶ 273:
** Sorry, what "continuous rename or move actions"? There was only *one* split of "Array" into two articles (and a consequent move of "Array (disambiguation)" to "Array") --[[User:Jorge Stolfi|Jorge Stolfi]] ([[User talk:Jorge Stolfi|talk]]) 16:42, 16 May 2009 (UTC)
<!--It seems that the reply by [[User talk:Macrakis|talk]] was inserted in the middle of [[User:Cybercobra|Cybercobra]]'s reply at the same level of indentation. If that is the case, onsider fixing the indentation and/or signatures. -->
::I daresay I ''am'' somewhat of an expert in this field. I have a Ph.D. in computer science with a dissertation on the design of programming languages. I was the secretary of the Ada Distinguished Reviewers committee which reviewed language design decisions. I have participated in the design of multiple languages and on the design and implementation of multiple compilers and interpreters, including the design of their runtime architectures (i.e. the concrete data structures used to implement the language data and control structures). I have reviewed a variety of obscure programming languages for the DoD. And of course I have used a large variety of programming languages.
Line 260 ⟶ 279:
::There is a central core concept of 'array' -- a structure whose components are denoted by an index and its various implementations -- which can usefully be discussed in the mother article. Then, additional detail can be added in subsidiary articles. --[[User:Macrakis|macrakis]] ([[User talk:Macrakis|talk]]) 00:06, 18 May 2009 (UTC)
::At best, the terms used to separate the articles aren't particularly well-established or canonical. At worst, they are arbitrary, possibly original research, and possibly incorrect. --[[User:Cybercobra|Cybercobra]] ([[User talk:Cybercobra|talk]]) 00:29, 18 May 2009 (UTC)
* <p>It looks like the definition of Array Data Structure cites Dictionary of Algorithms and Data Structures definition of array, which says, "Array (data structure) An assemblage of items that are randomly accessible by integers, the index." This matches the WP definition of "Array Data Type", and not so much the WP "Array Data Structure" definition, and says nothing about indexing by physical address (itself a questionable link in this day of virtual memory) by formula. Additionally the ADT information from the DADS entry appears on the Array Data Type page, not here, but is cited here, not there.</p><p>AOCP1 is also cited, and Knuth does have a simple formula on p 244 where he talks about: Linear Lists (which are 1D arrays per p 4 & 629) with Sequential Allocation. A similar formula appears for multidimensional arrays on p 299 with Sequential Allocation, where Sequential Allocation is just a straight-up allocation of a block of words (i.e. a normal array data structure). However, Knuth goes on to then discuss "arrays" with Linked Allocation (i.e. a linked list) on pages 254 and 301. That is to say, he is speaking of arrays in the WP "Array Data Structure" sense when he is talking about Sequential Allocation, but in the WP "Array Data Type" sense when he is talking about Linked Allocation. But since they're all "arrays" to him, WP is making a terminology distinction that Knuth does not seem to be making in the same way.</p><p>So I'm not sure the definitions we're using here are well-backed by their citations.</p><p>Plus, the two pages are very confusing for reasons I don't quite understand (and I'm a pretty experienced computer guy). Arrays as an ADT and as an implementation whether by "sequential allocation", "linked allocation", or otherwise, are a very simple concept to present, so there is no reason why the articles should be anything other than crystal clear. I'm willing to take a stab at it, but there's obviously a lot of history here and I'm reluctant to get involved. So just put this down as a vote for "needs work". [[User:Beej71|Beej71]] ([[User talk:Beej71|talk]]) 12:29, 7 January 2010 (UTC)</p>
==iliffe array==
The implementation of the iliffe array presented here makes the assumption that each row is allocated separately. However, Numerical Recipes in C provide a version of such vector with better locality by allocating the data as a contiguous memory block and have the indexing array points to beginning of rows in this block. Tests show few to no overhead between this and a traditional Dope vector. Would it be worthwhile to speak of this distinction ?
[[User:Joel falcou|Joel falcou]] ([[User talk:Joel falcou|talk]]) 18:27, 4 January 2012 (UTC)
== Arrays not analogous to vectors or matrices ==
(Referring to the 3rd paragraph) Arrays are not analogous to mathematical vectors, matrices or tensors, but rather to the objects called tuples in mathematical terminology. I appreciate that they have often been named this way, and there may even be cases where it is helpful to explain them like this, but the statement as it stands is not correct. I believe at the least there should be a mention of tuples. I am not aware of the mathematical term for multidimensional tuples.
Example:
Vectors and the related objects are linear objects. An array of customer details is valid in computer science, but it has no meaning to act on it using coordinate transformations, linear functions, inner products or any of the other machinery associated with linear mathematics. Conversely Maxwell's equations contain vectors but do not contain any arrays (or tuples). When a vector can be represented as a tuple/array, it must have elements that are members of a field, this is not the case for a general array.
I see that the paragraph doesn't have a reference, so unless there is some disagreement or discussion I will delete it, or possibly edit it.
David Drakard <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/86.182.183.171|86.182.183.171]] ([[User talk:86.182.183.171|talk]]) 22:20, 2 October 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
== linked list O(1) insertion/deletion in the middle? ==
I know this is a common myth, but am surprised to see it in a Wikipedia article. Moreover, how can we read both O(n) for indexed access and O(1) for insertion/deletion in the middle, since to insert or delete item #i in a list, one must first get there, meaning perform indexed access.
Can someone expose this better? I would happily do it, but since I have no reference, edits would probably be quickly removed by ll fans, and I don't want to start an edit war (better abstain).
[[User:Denispir|denis 'spir']] ([[User talk:Denispir|talk]]) 18:09, 9 December 2012 (UTC)
== "A programmer (or a sophisticated compiler) may use this information to choose between ... ==
... row- or column-major layout for each array."
'''Very nice''', but in what actual programming language is that possible"
:Several languages and libraries for numeric computing, e.g. NumPy. I'm not aware of compilers that do this. [[User:Qwertyus|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus|hm?]])</small> 10:51, 25 February 2016 (UTC)
== A Commons file used on this page has been nominated for deletion ==
The following Wikimedia Commons file used on this page has been nominated for deletion:
* [[commons:File:Octicons-terminal.svg|Octicons-terminal.svg]]<!-- COMMONSBOT: discussion | 2019-07-26T23:37:55.984986 | Octicons-terminal.svg -->
Participate in the deletion discussion at the [[commons:Commons:Deletion requests/File:Octicons-terminal.svg|nomination page]]. —[[User:Community Tech bot|Community Tech bot]] ([[User talk:Community Tech bot|talk]]) 23:38, 26 July 2019 (UTC)
== Discuss delayed and manifest arrays ==
We should have a section that discusses different conceptual representations of arrays i.e. manifest and delayed. On a high level:
Manifest arrays
* exists in memory;
* contain trash from the memory without initialisation
* can be hidden behind functions to act as delayed arrays
Delayed arrays
* do not have to actually exist;
* are represented by a function of type (!! :: ix -> a) where ix is the index type and a is the type of the values of the array;
* Multidimensional array access translates to function composition
Delayed arrays seem to become more and more prominent in languages such as Haskell, Accelerate, Single Assignment C, Halide, Repa, Massiv and Futhark.
--[[User:Cluzz|Cluzz]] ([[User talk:Cluzz|talk]]) 15:33, 21 January 2020 (UTC)
== clarity ==
There needs to be some clarity as to what an array is, it seems sometimes it is a consecutive series of same sized elements in a datastructure (consecutive in memory) but then memory on most modern systems isn't physically consecutive anyway... since it is virtualised, so then... is it a logic (pretend) consecutive series of same sized elements? then we have associative arrays, which don't seem to be arrays at all but often lists of things. I know what I was taught originally an array to be, as in k&r C, but... that doesn't appear to be the definitive definition of array - at least any more. [[Special:Contributions/103.232.162.28|103.232.162.28]] ([[User talk:103.232.162.28|talk]]) 18:28, 1 June 2025 (UTC)
| |||