This is the
talk page for discussing improvements to the
Array (data structure) article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
![]() | This ![]() It is of interest to the following WikiProjects: | |||||||||||||||||
|
![]() | Text and/or other creative content from this version of Index (computer science) was copied or moved into Array data structure with this edit on 17:50, 10 January 2012. The former page's history now serves to provide attribution for that content in the latter page, and it must not be deleted as long as the latter page exists. |
Is there benefit of arrays?
--- How is an array also known as a list? Surely this is just wrong. An array is indexable; a list is not. -- Mike Van Emmerik 02:33, 5 October 2005 (UTC)
"In computer programming, a group of homogeneous elements of a specific data type is known as an array, one of the simplest data structures" is false for Ruby; "Ruby's arrays can accomodate diverse object types". - Ruby User's Guide
Is the definition of arrays inaccurate, or are Ruby arrays not strictly arrays? -- Wootery 20:44, 3 October 2006 (UTC)
From the article: "Supporters of zero-based indexing often criticise one-based and n-based arrays for being slower. While this is true, a one-based or n-based array access can be easily optimized, for example either with a very simple Common subexpression elimination or the use of a well defined Dope vector - to name only two options available. So in real-life applications one-based and n-based arrays are just as fast as zero-based arrays."
I'm looking for a place to rant and rave (as objectively as possible of course :-)) about the C++ vector<bool> specialisation standard-that-is-not-really-a-standard. Where would I go about writing such an article? Or do I just write a vector<bool> article and let someone else move it / splice it later? -- The Extremist 09:14, 6 January 2006 (UTC)
QUESTION: A company is seeking to determine the optimum length of the guarantee period on its product, a device whose reliability and propensity to failure can be predicted with a high degree of accuracy. It is known that the failure rate of the device can be adequately approximated in terms of a constant function of time i.e. about 10% of the devices sold will fail each year until all have failed at the end of 10 years. The company makes a profit of $2.80 on each unit sold. If it offers no guarantee, it can expect to sell 100 units annually. The length of the guarantee is of some importance to customers however, and some empirical studies have suggested that its effect on sales may be shown by the following equation;
Q=100+5t
Where Q=Quantity sold (in units) And T=Length of guarantee (in years)
The company sustained a cost of $1.00 for each unit which it had to repair under terms of the guarantee. In view of this and in view of the fact that 10% of Q would be expected to fail each year, it was believed that the cost of making guaranteed repairs under a guarantee period of length t would be;
C=$1.00X0.1QT =0.1QT
Profit in this analysis can be regarded merely as the gross profit from sales less the cost of making guaranteed repairs. It will be noted that certain simplifying assumptions have been made in the foregoing exposition. The assumed constant failure rate has already been mentioned. Also, it should be noted that constant sales volume has been assumed, and the effect on sales of all variables other than that of the guarantee period has been disregarded.
RFEQUIRED: Determine the optimum length of the guarantee period in order to maximize profits.
In the "Array system cross-reference list", why are C and C++ listed as having Dimension = 1? What do they lack compared to languages listed under Dimension = n? Certainly both multidimensional arrays (arrays of arrays) and arrays of references (Iliffe vectors) are used in C and C++. -- Spoon! 03:25, 25 July 2006 (UTC)
Slice (5 .. 20, 5 .. 20)
- of course since C/C++ don't support array slices to begin with you won't notice the difference. --
Krischik
T
11:53, 30 January 2008 (UTC)Does this make any sense to anyone? What does "sorted" have to do with 1-dimensional arrays? (maybe it's "stored"?) And what does "horizontal" or "vertical" have to do with 1-dimensional arrays? -- Spoon! 11:30, 25 August 2006 (UTC)
137.112.141.152 07:34, 19 October 2006 (UTC)
Howcome PHP isn't on the Array system cross-reference list? - Dan Leveille 22:09, 17 November 2006 (UTC)
Don't know if this is a big deal, but MATLAB is column-major as well. Should we update the table of programming languages/array characteristics to indicate whether that language is row- or column-major?-- Andrew Blackburn 16:20, 01 December 2006 (UTC)
So the article used to talk about how insertion/deletion in an array requires linear time - an editor recently pointed out that insertion/deletion in an array doesn't really make sense, as it's fixed in size. While I'm sure there's no issue with describing insertion/deletion in the context of dynamic arrays, I've still seen many algorithm books and references describe arrays as requiring linear time for insertion and deletion in contexts such as insertion sort, where a list of bounded size is stored inside an array. I attempted to explain this with the following paragraph, but it may not have been sufficiently clear:
I would appreciate any feedback on how better to organize and express this point. Dcoetzee 23:38, 26 July 2007 (UTC)
I think that the lead of this article should only be about fixed-size arrays, with a small section about dynamic arrays. Your example of using a fixed-size array to implement a list whose size is bounded is no different than using a dynamic array having first asked the data structure to allocate enough memory. So, I think that the best way to organize this information is to phrase like that and to put this information into the dynamic array page, if it's not already there. MisterSheik 23:45, 26 July 2007 (UTC)
Hoped I could fit this all in an edit summary. The attempted merge of array and dynamic array, followed by an incomplete cleanup, left the article in an odd state. I reverted and merged in unrelated changes. Then I discovered the article was still attempting to assert the nonstandard position that "dynamic arrays are a type of array", which is controversial at best, so I've eliminated any claim one way or the other and added a suitable disclaimer. I'm not happy with a number of other changes, like the new informal-to-the-point-of-misleading characterization of multidimensional arrays, but one problem at a time. The modified section title "comparison with linked lists" was modified again to fit my changes and the bizarre introduction of out-of-bounds accesses as only a "source of bugs" was moved and rewritten. Dcoetzee 10:06, 1 August 2007 (UTC)
So it seems there's been a recent series of drastic changes to Array and Dynamic array based primarily in a terminology conflict: basically, whether or not a dynamic array is a kind of array or not. I hope we're past the point of attempting to merge Dynamic array into Array, but there's still the issue of how the two ought to be related on their own pages.
First of all I want to avoid referring to fixed-size arrays as static arrays for the reason stated in the article: it's too easily confused with statically-allocated arrays. I also don't like the terms "statically/dynamically-sized", as these aren't widely used and are even more easily confused with the fixed-size versus growable distinction. On reflection I wish I'd titled Dynamic array as Growable array or something like that to prevent confusion with dynamically-allocated arrays - maybe it ought to be moved.
Next, is a dynamic array an array? Sort of and sort of not. You can see it as a kind of array or an array variant that is extended to support efficient resizing and insertion and deletion at the end. On the other hand, you can also see it as a more complex data structure built on top of ordinary arrays. NIST defines a dynamic array as "an array whose size may change over time" and appears to include dynamic arrays as a special case in its liberal definition of arrays, whereas others restrict the term "array" to fixed-size arrays. I don't believe this wording was intended to include arrays with expensive resizing operations like using realloc() in C - conflating dynamically-allocated and growable arrays would only produce confusion. The most useful conceptual distinction to make is between fixed-size and growable arrays, which have significantly different implementations and operation sets. I think the current wording in both articles is consistent can at least be interpreted in a way that's consistent with NIST, which is at least one authoritative source, and it creates useful distinctions. Is anyone unhappy with the way things look now?
As a gentle reminder, please look carefully at the entire content of a set of changes before changing them. I have had unrelated changes reverted on a number of occasions. I hope we can reach a reasonable consensus that reflects not only our understanding of these terms but wide usage in the literature and education. Dcoetzee 11:34, 1 August 2007 (UTC)
struct employee{ ... char namestr[80]; }; ... void editname( char namestr[80] ){ char buf[80]; ... }
an array with a fixed size set at compile time.struct employee{ ... int namelen; char namestr[]; }; ... void editname( char namestr[], int length ){ char buf[length]; ... }
an array whose size is "fixed" in that it cannot be grown after it is created, although some people still call it a
variable-length array since size is not set at compile time. (I think this was added in
C99).struct employee{ ... int namelen; char *namep; }; ... void editname( char **namestr, int *length ){ char *buf; ... }
an "array" that is
growable using realloc().The first section of the article was rather bizarre:
==Arrays== Variables normally only store a single value but, in some situations, it is useful to have a variable that can store a series of related values - using an array. For example, suppose a program is required that will calculate the average age among a group of six students. The ages of the students could be stored in six integer variables in C programming language: <source lang="c"> int age1; int age2; int age3; ... </source> However, a better solution would be to declare a six-element array: <source lang="c">int age[6];</source> This creates a six element array; the elements can be accessed as <code>age[0]</code> through <code>age[5]</code> in C. (Note: in [[Visual Basic .NET]] the similar declaration <code>Dim age(6) as Integer</code> will create a ''seven'' element array, accessed as <code>age(0)</code> through <code>age(6)</code>.) ===Implicit array=== A new array object is implicitly created when an array initializer expression is evaluated; this can occur when a class or interface is initialized, when a new instance of a class is created, or when a local variable declaration statement is executed.
At best, this (excluding paragraph before and after the subsection "Implicit array") is an elementary example of use of an array, but it's probably not complete enough to be useful for anyone who doesn't already know what it seeks to explain. (A more realistic example could be to compute the average score over 6 tests.) If the section is reinserted, it should probably be named "Example" or similar.
The Visual Basic .NET paragraph hints at the split (similar to 0/1/n-based indexing) over whether the number in an array declaration should be the size of the array or the index of the last element. This would be useful to mention in the article, but not in such a specialised context. 81.231.33.217 ( talk) 12:48, 30 June 2008 (UTC)
The article contains one reference, so is it appropriate to remove the Unreferenced tag?
Also, would it be appropriate to increase its quality rating? It seems to meet C-class criteria easily. 81.231.34.61 ( talk) 21:10, 10 September 2008 (UTC)
The article states:
Which is wrong. In french, there is a word rez-de-chaussée meaning "groung floor", while étages are levels over the ground floor. Thus, on elevator buttons, étages are pointed to by ordinals from 1 up, while the unique rez-de-chaussée is (rather logically) referenced either by "RdC" or "0". In other words, what is adressed by the article's statement is a difference of word semantic scope. While it obviously tried to state that : "There are cases in real life where zero is used as an ordinal". Which may be right (?) -- yet precisely not in the case cited as a typical instance!
For couter-arguments, just watch languages. In english, ordinals and cardinals are equally called "numbers" -- compare with german Nummer/Zahl or french numéro/nombre. Yet one may still notice that zero's novelty is witnessed by the everyday use (actually un-use): people don't say "zero apple", "zero person", or "zero time"..., do they? Rather "no apple", "nobody", "never"... -- Denispir ( talk) 21:31, 8 October 2008 (UTC)
In Array#Index_of_the_first_element I'd like to add the point that zero-base is also more natural for applications where an arbitrary subscript is reduced to the appropriate range with a mod operator; but I don't see where it will fit well. Comments? — Tamfang ( talk) 08:12, 1 November 2008 (UTC)
I did an extensive cleanup of the article, trying to clearly distinguish the two concepts "array data structure" (language-independent stuff) and "array data type" (language-dependent stuff). While much remains to be done, I now think that the article should be split along that line. The two concepts are clearly separable and each has enough meterial to fill a large article. The separation should also help reduce editorial conflicts, that often seem to arise from confusion between the two concepts. What do you think? All the best, -- Jorge Stolfi ( talk) 04:53, 12 May 2009 (UTC)
The abstract array axioms in the current version are:
Methink that this is not OK because:
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.
Does the paper say anythng about these problems? --
Jorge Stolfi (
talk)
02:54, 13 May 2009 (UTC)
The result of the move request was not moved 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. -- Cybercobra ( talk) 05:45, 16 May 2009 (UTC)
*'''Support'''
or *'''Oppose'''
, then sign your comment with ~~~~
. Since
polling is not a substitute for discussion, please explain your reasons, taking into account
Wikipedia's naming conventions.These articles about arrays have become a collection of ORIGINAL RESEARCH which is not the purpose of WP. An array is called just an 'array' and hardly ever called an 'array structure'. The hair-splitting activity w/r/t to 'array data structure' and 'array data type' is similarly obscure. Someone please provide definitive reference to the legitimacy of the terms and their definition. The new set of articles is confusing and almost incomprehensible even for knowledgeable readers. Side-by-side comparison of the original with the new clearly reveals that the original array article was superior article for encyclopedic use. Kbrose ( talk) 06:33, 16 May 2009 (UTC)
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.
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.
So I'm not sure the definitions we're using here are well-backed by their citations.
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". Beej71 ( talk) 12:29, 7 January 2010 (UTC)
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 ? Joel falcou ( talk) 18:27, 4 January 2012 (UTC)
(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 — Preceding unsigned comment added by 86.182.183.171 ( talk) 22:20, 2 October 2012 (UTC)
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).
denis 'spir' ( talk) 18:09, 9 December 2012 (UTC)
... row- or column-major layout for each array."
Very nice, but in what actual programming language is that possible"
The following Wikimedia Commons file used on this page has been nominated for deletion:
Participate in the deletion discussion at the nomination page. — Community Tech bot ( talk) 23:38, 26 July 2019 (UTC)
We should have a section that discusses different conceptual representations of arrays i.e. manifest and delayed. On a high level:
Manifest arrays
Delayed arrays
Delayed arrays seem to become more and more prominent in languages such as Haskell, Accelerate, Single Assignment C, Halide, Repa, Massiv and Futhark.
This is the
talk page for discussing improvements to the
Array (data structure) article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
![]() | This ![]() It is of interest to the following WikiProjects: | |||||||||||||||||
|
![]() | Text and/or other creative content from this version of Index (computer science) was copied or moved into Array data structure with this edit on 17:50, 10 January 2012. The former page's history now serves to provide attribution for that content in the latter page, and it must not be deleted as long as the latter page exists. |
Is there benefit of arrays?
--- How is an array also known as a list? Surely this is just wrong. An array is indexable; a list is not. -- Mike Van Emmerik 02:33, 5 October 2005 (UTC)
"In computer programming, a group of homogeneous elements of a specific data type is known as an array, one of the simplest data structures" is false for Ruby; "Ruby's arrays can accomodate diverse object types". - Ruby User's Guide
Is the definition of arrays inaccurate, or are Ruby arrays not strictly arrays? -- Wootery 20:44, 3 October 2006 (UTC)
From the article: "Supporters of zero-based indexing often criticise one-based and n-based arrays for being slower. While this is true, a one-based or n-based array access can be easily optimized, for example either with a very simple Common subexpression elimination or the use of a well defined Dope vector - to name only two options available. So in real-life applications one-based and n-based arrays are just as fast as zero-based arrays."
I'm looking for a place to rant and rave (as objectively as possible of course :-)) about the C++ vector<bool> specialisation standard-that-is-not-really-a-standard. Where would I go about writing such an article? Or do I just write a vector<bool> article and let someone else move it / splice it later? -- The Extremist 09:14, 6 January 2006 (UTC)
QUESTION: A company is seeking to determine the optimum length of the guarantee period on its product, a device whose reliability and propensity to failure can be predicted with a high degree of accuracy. It is known that the failure rate of the device can be adequately approximated in terms of a constant function of time i.e. about 10% of the devices sold will fail each year until all have failed at the end of 10 years. The company makes a profit of $2.80 on each unit sold. If it offers no guarantee, it can expect to sell 100 units annually. The length of the guarantee is of some importance to customers however, and some empirical studies have suggested that its effect on sales may be shown by the following equation;
Q=100+5t
Where Q=Quantity sold (in units) And T=Length of guarantee (in years)
The company sustained a cost of $1.00 for each unit which it had to repair under terms of the guarantee. In view of this and in view of the fact that 10% of Q would be expected to fail each year, it was believed that the cost of making guaranteed repairs under a guarantee period of length t would be;
C=$1.00X0.1QT =0.1QT
Profit in this analysis can be regarded merely as the gross profit from sales less the cost of making guaranteed repairs. It will be noted that certain simplifying assumptions have been made in the foregoing exposition. The assumed constant failure rate has already been mentioned. Also, it should be noted that constant sales volume has been assumed, and the effect on sales of all variables other than that of the guarantee period has been disregarded.
RFEQUIRED: Determine the optimum length of the guarantee period in order to maximize profits.
In the "Array system cross-reference list", why are C and C++ listed as having Dimension = 1? What do they lack compared to languages listed under Dimension = n? Certainly both multidimensional arrays (arrays of arrays) and arrays of references (Iliffe vectors) are used in C and C++. -- Spoon! 03:25, 25 July 2006 (UTC)
Slice (5 .. 20, 5 .. 20)
- of course since C/C++ don't support array slices to begin with you won't notice the difference. --
Krischik
T
11:53, 30 January 2008 (UTC)Does this make any sense to anyone? What does "sorted" have to do with 1-dimensional arrays? (maybe it's "stored"?) And what does "horizontal" or "vertical" have to do with 1-dimensional arrays? -- Spoon! 11:30, 25 August 2006 (UTC)
137.112.141.152 07:34, 19 October 2006 (UTC)
Howcome PHP isn't on the Array system cross-reference list? - Dan Leveille 22:09, 17 November 2006 (UTC)
Don't know if this is a big deal, but MATLAB is column-major as well. Should we update the table of programming languages/array characteristics to indicate whether that language is row- or column-major?-- Andrew Blackburn 16:20, 01 December 2006 (UTC)
So the article used to talk about how insertion/deletion in an array requires linear time - an editor recently pointed out that insertion/deletion in an array doesn't really make sense, as it's fixed in size. While I'm sure there's no issue with describing insertion/deletion in the context of dynamic arrays, I've still seen many algorithm books and references describe arrays as requiring linear time for insertion and deletion in contexts such as insertion sort, where a list of bounded size is stored inside an array. I attempted to explain this with the following paragraph, but it may not have been sufficiently clear:
I would appreciate any feedback on how better to organize and express this point. Dcoetzee 23:38, 26 July 2007 (UTC)
I think that the lead of this article should only be about fixed-size arrays, with a small section about dynamic arrays. Your example of using a fixed-size array to implement a list whose size is bounded is no different than using a dynamic array having first asked the data structure to allocate enough memory. So, I think that the best way to organize this information is to phrase like that and to put this information into the dynamic array page, if it's not already there. MisterSheik 23:45, 26 July 2007 (UTC)
Hoped I could fit this all in an edit summary. The attempted merge of array and dynamic array, followed by an incomplete cleanup, left the article in an odd state. I reverted and merged in unrelated changes. Then I discovered the article was still attempting to assert the nonstandard position that "dynamic arrays are a type of array", which is controversial at best, so I've eliminated any claim one way or the other and added a suitable disclaimer. I'm not happy with a number of other changes, like the new informal-to-the-point-of-misleading characterization of multidimensional arrays, but one problem at a time. The modified section title "comparison with linked lists" was modified again to fit my changes and the bizarre introduction of out-of-bounds accesses as only a "source of bugs" was moved and rewritten. Dcoetzee 10:06, 1 August 2007 (UTC)
So it seems there's been a recent series of drastic changes to Array and Dynamic array based primarily in a terminology conflict: basically, whether or not a dynamic array is a kind of array or not. I hope we're past the point of attempting to merge Dynamic array into Array, but there's still the issue of how the two ought to be related on their own pages.
First of all I want to avoid referring to fixed-size arrays as static arrays for the reason stated in the article: it's too easily confused with statically-allocated arrays. I also don't like the terms "statically/dynamically-sized", as these aren't widely used and are even more easily confused with the fixed-size versus growable distinction. On reflection I wish I'd titled Dynamic array as Growable array or something like that to prevent confusion with dynamically-allocated arrays - maybe it ought to be moved.
Next, is a dynamic array an array? Sort of and sort of not. You can see it as a kind of array or an array variant that is extended to support efficient resizing and insertion and deletion at the end. On the other hand, you can also see it as a more complex data structure built on top of ordinary arrays. NIST defines a dynamic array as "an array whose size may change over time" and appears to include dynamic arrays as a special case in its liberal definition of arrays, whereas others restrict the term "array" to fixed-size arrays. I don't believe this wording was intended to include arrays with expensive resizing operations like using realloc() in C - conflating dynamically-allocated and growable arrays would only produce confusion. The most useful conceptual distinction to make is between fixed-size and growable arrays, which have significantly different implementations and operation sets. I think the current wording in both articles is consistent can at least be interpreted in a way that's consistent with NIST, which is at least one authoritative source, and it creates useful distinctions. Is anyone unhappy with the way things look now?
As a gentle reminder, please look carefully at the entire content of a set of changes before changing them. I have had unrelated changes reverted on a number of occasions. I hope we can reach a reasonable consensus that reflects not only our understanding of these terms but wide usage in the literature and education. Dcoetzee 11:34, 1 August 2007 (UTC)
struct employee{ ... char namestr[80]; }; ... void editname( char namestr[80] ){ char buf[80]; ... }
an array with a fixed size set at compile time.struct employee{ ... int namelen; char namestr[]; }; ... void editname( char namestr[], int length ){ char buf[length]; ... }
an array whose size is "fixed" in that it cannot be grown after it is created, although some people still call it a
variable-length array since size is not set at compile time. (I think this was added in
C99).struct employee{ ... int namelen; char *namep; }; ... void editname( char **namestr, int *length ){ char *buf; ... }
an "array" that is
growable using realloc().The first section of the article was rather bizarre:
==Arrays== Variables normally only store a single value but, in some situations, it is useful to have a variable that can store a series of related values - using an array. For example, suppose a program is required that will calculate the average age among a group of six students. The ages of the students could be stored in six integer variables in C programming language: <source lang="c"> int age1; int age2; int age3; ... </source> However, a better solution would be to declare a six-element array: <source lang="c">int age[6];</source> This creates a six element array; the elements can be accessed as <code>age[0]</code> through <code>age[5]</code> in C. (Note: in [[Visual Basic .NET]] the similar declaration <code>Dim age(6) as Integer</code> will create a ''seven'' element array, accessed as <code>age(0)</code> through <code>age(6)</code>.) ===Implicit array=== A new array object is implicitly created when an array initializer expression is evaluated; this can occur when a class or interface is initialized, when a new instance of a class is created, or when a local variable declaration statement is executed.
At best, this (excluding paragraph before and after the subsection "Implicit array") is an elementary example of use of an array, but it's probably not complete enough to be useful for anyone who doesn't already know what it seeks to explain. (A more realistic example could be to compute the average score over 6 tests.) If the section is reinserted, it should probably be named "Example" or similar.
The Visual Basic .NET paragraph hints at the split (similar to 0/1/n-based indexing) over whether the number in an array declaration should be the size of the array or the index of the last element. This would be useful to mention in the article, but not in such a specialised context. 81.231.33.217 ( talk) 12:48, 30 June 2008 (UTC)
The article contains one reference, so is it appropriate to remove the Unreferenced tag?
Also, would it be appropriate to increase its quality rating? It seems to meet C-class criteria easily. 81.231.34.61 ( talk) 21:10, 10 September 2008 (UTC)
The article states:
Which is wrong. In french, there is a word rez-de-chaussée meaning "groung floor", while étages are levels over the ground floor. Thus, on elevator buttons, étages are pointed to by ordinals from 1 up, while the unique rez-de-chaussée is (rather logically) referenced either by "RdC" or "0". In other words, what is adressed by the article's statement is a difference of word semantic scope. While it obviously tried to state that : "There are cases in real life where zero is used as an ordinal". Which may be right (?) -- yet precisely not in the case cited as a typical instance!
For couter-arguments, just watch languages. In english, ordinals and cardinals are equally called "numbers" -- compare with german Nummer/Zahl or french numéro/nombre. Yet one may still notice that zero's novelty is witnessed by the everyday use (actually un-use): people don't say "zero apple", "zero person", or "zero time"..., do they? Rather "no apple", "nobody", "never"... -- Denispir ( talk) 21:31, 8 October 2008 (UTC)
In Array#Index_of_the_first_element I'd like to add the point that zero-base is also more natural for applications where an arbitrary subscript is reduced to the appropriate range with a mod operator; but I don't see where it will fit well. Comments? — Tamfang ( talk) 08:12, 1 November 2008 (UTC)
I did an extensive cleanup of the article, trying to clearly distinguish the two concepts "array data structure" (language-independent stuff) and "array data type" (language-dependent stuff). While much remains to be done, I now think that the article should be split along that line. The two concepts are clearly separable and each has enough meterial to fill a large article. The separation should also help reduce editorial conflicts, that often seem to arise from confusion between the two concepts. What do you think? All the best, -- Jorge Stolfi ( talk) 04:53, 12 May 2009 (UTC)
The abstract array axioms in the current version are:
Methink that this is not OK because:
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.
Does the paper say anythng about these problems? --
Jorge Stolfi (
talk)
02:54, 13 May 2009 (UTC)
The result of the move request was not moved 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. -- Cybercobra ( talk) 05:45, 16 May 2009 (UTC)
*'''Support'''
or *'''Oppose'''
, then sign your comment with ~~~~
. Since
polling is not a substitute for discussion, please explain your reasons, taking into account
Wikipedia's naming conventions.These articles about arrays have become a collection of ORIGINAL RESEARCH which is not the purpose of WP. An array is called just an 'array' and hardly ever called an 'array structure'. The hair-splitting activity w/r/t to 'array data structure' and 'array data type' is similarly obscure. Someone please provide definitive reference to the legitimacy of the terms and their definition. The new set of articles is confusing and almost incomprehensible even for knowledgeable readers. Side-by-side comparison of the original with the new clearly reveals that the original array article was superior article for encyclopedic use. Kbrose ( talk) 06:33, 16 May 2009 (UTC)
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.
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.
So I'm not sure the definitions we're using here are well-backed by their citations.
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". Beej71 ( talk) 12:29, 7 January 2010 (UTC)
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 ? Joel falcou ( talk) 18:27, 4 January 2012 (UTC)
(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 — Preceding unsigned comment added by 86.182.183.171 ( talk) 22:20, 2 October 2012 (UTC)
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).
denis 'spir' ( talk) 18:09, 9 December 2012 (UTC)
... row- or column-major layout for each array."
Very nice, but in what actual programming language is that possible"
The following Wikimedia Commons file used on this page has been nominated for deletion:
Participate in the deletion discussion at the nomination page. — Community Tech bot ( talk) 23:38, 26 July 2019 (UTC)
We should have a section that discusses different conceptual representations of arrays i.e. manifest and delayed. On a high level:
Manifest arrays
Delayed arrays
Delayed arrays seem to become more and more prominent in languages such as Haskell, Accelerate, Single Assignment C, Halide, Repa, Massiv and Futhark.