Talk:Dynamic array

From Wikipedia, the free encyclopedia

Contents

[edit] Language of example

What language is the example in. Fresheneesz 02:30, 10 June 2006 (UTC)

Pseudocode. Deco 04:51, 10 June 2006 (UTC)
Ok, but its not very clear what the difference between the = operator and the  := operator is - at least for me. Fresheneesz 10:33, 10 June 2006 (UTC)
:= is a conventional operator for assignment. = refers to equality. In this case I think the context makes it obvious. I'd considered using ← for assignment but that's somewhat harder to edit. Deco 21:08, 10 June 2006 (UTC)
I don't know how the use of = as equality is obvious here - especially to programmers who never learned any pseudo code. And in that case, is this line wrong then?:
a.capacity = a.capacity × 2
May I suggest we switch to a *real* language, pseudo code always makes the syntax seems unreliable (not always the same), and real code is easier to look up. Fresheneesz 23:59, 10 June 2006 (UTC)
You might be interested in Wikipedia:Algorithms on Wikipedia. I would be amused if you attempt to change the guidelines to use the One True Programming Language rather than pseudocode. --68.0.120.35 09:12, 5 March 2007 (UTC)
Ha. I'm not gonna pull that kinda stunt. Maybe I would if my programming language ever gets on wikipedia. : ) Fresheneesz 07:12, 8 March 2007 (UTC)

[edit] Overview

I thought that the overview section should be kept. Dynamic array is obviously an array data structure. I am not clear about the edit that states "dynamic array is not strictly an array data structure". MegaHasher 06:56, 28 July 2007 (UTC)

I suppose this depends on how you define "array." It's certainly not "obvious" that it is, since an array is frequently defined as a fixed-size data structure. Dcoetzee 03:55, 1 August 2007 (UTC)

The cost of expanding to a larger sized array is not n2, but 2n. The amortized cost per insertion is O(1). MegaHasher 07:06, 28 July 2007 (UTC)

The cost is n2 with naive expansion for every insertion. This is the point. Dcoetzee 03:56, 1 August 2007 (UTC)

A constant sized array could have elements removed by using a size field, but this fact is probably not notable. MegaHasher 07:06, 28 July 2007 (UTC)

[edit] We

This topic has many instances of the 'we' pronoun. Who's 'we'? Is this a recommended style for encyclopedic article? MegaHasher 07:10, 28 July 2007 (UTC)

My fault. Feel free to fix. I'll fix eventually if you don't. Dcoetzee 10:33, 28 July 2007 (UTC)

[edit] Redirect into Array

Should this page be merged into Array? Is dynamic array a sufficiently broad topic that it can stand as a separate topic? MegaHasher 03:11, 31 July 2007 (UTC)

I'm not sure. It just seemed like there was a lot of redundancy, and we were explaining the same things in two places. MisterSheik 08:48, 31 July 2007 (UTC)

No, no, no. Dynamic arrays aren't even arrays. They're just a data structure built on top of them. It's only briefly summarized in the array article. Dcoetzee 10:30, 31 July 2007 (UTC)
In C++ that's true. In many other languages, static arrays are a special case of dynamic arrays. It's just a matter of perspective. MisterSheik 15:33, 31 July 2007 (UTC)
No, it's totally language-independent. Just because some languages (e.g. Perl) use dynamic arrays to implement the same functions normally performed by fixed-size arrays doesn't mean fixed-sized arrays have ceased to exist conceptually in those languages - they just have to be implemented differently. Besides the whole fixed-size versus dynamic size thing, they support different set of operations, are frequently given different names, and depending on the implementation can have drastically differently indexing operations such as the one described by Brodnik et al.
Besides, some languages (e.g. Lua) implement almost everything, including arrays, using associative arrays, and I don't think you're about to propose merging that into array. Dcoetzee 03:52, 1 August 2007 (UTC)
What does it mean to say that a data structure is a special case of another? I think there should be only two things to check: if the interface of A is a subset of the interface of B, and if the speed (including complexity guarantees) of the operations that data structure A supports is the same as those that B supports, then A is a special case of B. In that case, I'm glad you brought the Brodnik paper up. They suggest that resizable arrays have four operations: read, write, grow, and shrink. It's clear that static arrays have simply omitted grow and shrink, and offer the same complexity guarantees for read and write. MisterSheik 05:08, 1 August 2007 (UTC)
Your argument appears to be saying that fixed-size arrays are in fact a special case of dynamic arrays; but only abstract data structures are defined strictly in terms of their interfaces. This is about as strange as claiming that a "red-black tree" is a special kind of "hash table", because it supports the same operations and also range queries. It isn't typical to implement fixed-size arrays using dynamic arrays (due partly to problems such as linear wasted space), although some scripting languages do it. Nevertheless I'm happy with the current wording, provided the two articles remain separate. Dcoetzee 05:31, 1 August 2007 (UTC)
Isn't this article about an abstract data structure? Hash tables don't support range queries. And there is no wasted space if the constructor for the dynamic array is called with the initial size, just as the constructor for the fixed-size array would be. However, I am also happy with the current wording :) MisterSheik 09:25, 1 August 2007 (UTC)
Hash tables not supporting range queries was my point - and I don't think this article is about an abstract data structure but rather, like hash table and red-black tree, a concrete data structure with a particular implementation, based on geometric expansion of an underlying array. Some of the variants implement the ADT in other ways, but this is the implementation of interest because of its wide use. But anyway, if you're happy I am. :-) Dcoetzee 11:48, 1 August 2007 (UTC)
Okay, I understand your point. But the example isn't a very good one: Hash tables have O(1) expected access time, and Θ(n) worst case time for element find, while red-black trees are always &Theta(log(n)). What you're saying is that this article is about a concrete data types rather than abstract ones. MisterSheik 20:45, 1 August 2007 (UTC)

[edit] Recent changes

Okay, here's a list of some things that were modified by recent changes that I changed:

  • Dynamic arrays are not supplied with "most standard libraries"; they are not supplied with C, or ML, or Fortran, or Pascal, or countless other standard libraries. The qualifier modern mainstream programming languages is necessary and should not have been removed.
  • I don't like use of the ambiguous term static array, which variously means either compile-time allocated array or fixed-size array, so I've eliminated it.
  • The text no longer makes a clear distinction between the underlying fixed-size storage and the variable-size storage used for the contents of the dynamic array and no longer clearly explains the concept of capacity. I added a section to more clearly explain this before launching into the discussion of geometric expansion, which is another matter entirely.
  • Restored the slightly pedantic explanation that n insertions take O(n) time, under the assumption that people viewing this will not be already familiar with amortized analysis.
  • Recent discussion at Talk:Array established that material related to insertion and deletion of elements in fixed-size arrays, and comparison to linked lists, was more appropriate for this article. All this material was subsequently removed. It has to go somewhere - it is referenced here in two places from array. Restored this.
  • Text was removed noting that wasted cells were a disadvantage over fixed-size arrays. Restored.
  • Discussion of variants was removed, such as the deque variant - it appears that at least some of it was moved to Deque#Dynamic_array_implementation. Linking it properly and expanding it with removed material in the new location. Deques are not strictly speaking "built on top of" dynamic arrays, since this variant changes how the basic data structure is implemented (either the elements are placed in the middle or a circular buffer is used).
  • Brief summary of gap buffer doesn't hurt.
  • realloc() does not implement dynamic arrays. Where are the insertion and deletion operations? Where are the amortized cost guarantees? realloc() can be used to implement dynamic arrays, but isn't even needed for that (malloc, free, and memcpy are enough). realloc() need not be mentioned here at all.

Changes you guys made that I liked:

  • Merging the time-space tradeoff stuff into the discussion. Didn't need its own section.
  • Moving deque-related stuff out to deque.
  • Removal of the pronoun "we" - bad habit.
  • General briefening of some verbose explanation.

Please discuss if you disagree. Dcoetzee 05:23, 1 August 2007 (UTC)

[edit] Merger proposal

This page should be merged with Vector (STL). Vector (STL) talks about an implementation of a dynamic array, and most of the content on that page applies to all dynamic arrays. 71.51.124.230 (talk) 19:29, 5 January 2008 (UTC)

Agreed, this page documents the specific implementation of a dynamic array 16:37, 5 April 2008 (UTC) —Preceding unsigned comment added by Cerf (talk • contribs)

No, I disagree. Vector STL is just one specific C++ construct. At best you could call it an implementation of dynamic arrays. Boost also released a similar implemenation with vectors. Beyond that, dynamic arrays are available in many other languages than C++. Vector STL is C++ specific. Dlother (talk) 18:14, 21 February 2008 (UTC)

I agree, but in the reverse direction. The generic parts of Vector (STL) ought to be merged here (or discarded, if they're already here in some form) - and the language-specific parts left there. Dcoetzee 19:03, 21 February 2008 (UTC)

It doesn't make sense to merge the two. I agree with the second comment. It is just one implementation of dynamic arrays, why should the Dynamic Arrays article focus on the C++ implementation? The C++ implementation is a complete and large subject in its own right. —Preceding unsigned comment added by 24.99.173.164 (talk) 14:59, 29 March 2008 (UTC)

Definitely should not be merged. Yes, STL vector is an implementation of dynamic arrays, just as a Cadillac is a car, but the wiki page for Cadillac shouldn't be merged into automobile. --Anniepoo (talk) 01:16, 22 May 2008 (UTC)

Provided there is truly enough to say about vector - and keep in mind Wikipedia isn't a detailed API guide - it can have its own article. But I think when you boil it down there's really not much left, maybe a paragraph. That is why I suggest merging it into this article. Dcoetzee 07:58, 22 May 2008 (UTC)