What is actually the array?

Asked

Viewed 2,915 times

20

Initially, it seems a silly question. But my goal here is to come up with a more concrete concept regarding the array.

In languages such as Javascript, the array is an object that accepts you to add and remove members to a kind of list. This list always has the indexes numbered starting from 0.

In Python, we have something similar to array of Javascript, which would be the list and the tuple, except the latter which is an immutable but similar list.

However, in PHP, the array seems to be a mixture of hash (or as Object in Javascript) with a list.

As my first programming language was PHP, I got used to Array being what it is in PHP, but when comparing with array of Java, Javascript and other languages, I see that even having the same nomenclature, they seem to be different things, generating a confusion of technical terms.

  • But after all, what is a array? Is it a sequentially indexed list? Or is it a container of manually indexed items (as in PHP)?

  • It would be correct to state that the PHP language array concept is wrong? If it is "wrong", what would be the most appropriate name for the "array" of this language?

  • List and array is the same thing? If not, what is the difference?

Related questions:

  • 3

    Name of stackoverflow moderator pt. D

  • 5

    Would it be correct to say that the PHP Language Array concept is wrong? A: In a way yes, there are a thousand other things that have an inappropriate name in PHP. If you look closely, you will see that PHP "borrows" many resource names from other languages, but without the proper concept domain. Ex: 7 "type" system, OO behavior simulation, "define" imitation, etc

  • 2

    In the case of PHP, even what would be a simple array, is an associative: http://ideone.com/iEDhkz (and that’s why in the question about how to detect the difference, the most important thing was missing in most answers: no difference, pq pro PHP is always associative. Any detection that does not read the source code looking for the definition, will not differentiate pq the only difference is in the source, apparently).

5 answers

23


But after all, what is a array? Is it a sequentially indexed list? Or is it a container of manually indexed items (as in PHP)?

Formally anything other than a single, continuous sequence of values is not a array.

Continue using the term that everyone in the technology community uses.

Each technology can name every element of it after itself. This is not to say that formally it is correct in computation, or even in mathematics since computation is a specific application of mathematics.

It would be correct to state that the concept of array of the PHP language is wrong? If it is "wrong", what would be the most appropriate name for the "array" of that language?

It is difficult to say this concretely.

PHP has a structure with sparse elements and its access made by a key that is not the position of the element in the sequence. At least it calls array associative and probably array is only a shortened form. If you pay attention to the documentation it is said that it is a array associative despite using the term Array in syntax.

Roughly it’s the same as a table hash. You don’t have to call it hash table, including because this may be just implementation detail. Some people call this a map or dictionary.

It is far from ideal in performance, but as it is to perform scripts nothing too problematic. So much array how much hash table have complexity O(1), but the array makes a simple pointer arithmetic, a table hash needs a more complex arithmetic and in some cases the complexity of the formula can be O(n) relative to the size of the key object.

The same way you talk about hash when you’re actually talking hash table. Or when you use list for list on. So depending on where you look something might look wrong, there’s a place that classifies it the right way, without simplification.

List and array is the same thing? If not, what is the difference?

List is a set of values that have a certain sequence, but the exact form of organization in memory and access to it is not defined. A list must accept new elements. A array does not usually accept.

Although the name array can be used there are more specific names for more specific data structures, except for the purest vector. List can be used so freely, but depending on how it is implemented it can have a more specific name.

Behold What is the function of the vector (array)?.

  • 4

    Basically, the main problem in PHP was centralizing everything in one structure only. As the documentation itself says: "it can be treated as an array, a list (array), hashtable (which is a map implementation), dictionary, collection, stack, queue and probably more".

  • 1

    @Andersoncarloswoss even remembering that it is always associative after all, even if declared as array: http://ideone.com/iEDhkz

  • Any and every object in Javascript memory is a hash table. That’s why Javascript arrays are hash tables.

9

"Array" is a word that existed long before programming. This is its meaning, according to the Dictionary.:

Verb (used with Object)
1. to place in Proper or desired order; marshal: (...)
Noun
3. order or arrangement, as of Troops Drawn up for Battle.
(...)
5. a large and impressive grouping or Organization of Things: He couldn’t Dismiss the array of Facts.
6. regular order or arrangement; series: an array of figures.
7. a large group, number, or Quantity of people or Things: an impressive array of scholars; an imposing array of Books.
(...)
9. an arrangement of interrelated Objects or items of Equipment for accomplishing a particular task: thousands of solar Cells in one Vast array.

All these meanings can be summarized, in Portuguese, as "an ordering or positioning of things". Or a set of things.

When the first programming languages were created, it was necessary to create a data structure that could store a variable amount of information. The name given to this type of structure was "Array". The only requirement he should meet was to store several items in an orderly manner. Over time, new needs were emerging, and for every need a new data structure emerged: stack, queue, tree etc.

Something interesting happens here. The other structures are either not "embedded" in most languages/platforms, or there are libraries with implementations for them. But the array is something so simple that it is part of the standard implementation of most common languages (it is even used internally to implement several other structures like the stack).

We know that arrays are something conceptual, simple and that almost every language has. The way each language implements this concept, however, varies.

In Javascript, for example, the Array resembles a simple chained list (emphasis on "resembles"... Each Javascript engine and interpreter implements in a different way). Already in C and C++, a array is a pointer. That’s right, a pointer! The array in these languages is a "syntactic sugar" to facilitate navigation by memory.

To characterize the array at the implementation level, we would have to characterize each language - and there are many of them. More useful is to understand the array by its concept. To simplify, just think of it as a structure where you store data in an orderly fashion. If you can add items beyond the stated size initially, if you can mix different types and other behaviors will vary according to the language you use - then it’s best to choose some languages you like best, understand how the array behaves in them, and learn the most common techniques of use. Good study!

  • 3

    One thing that seems incorrect to me is that an array does not necessarily store elements in an orderly fashion. The indexes are in fact ordered, but the elements are not.

  • 1

    @Wilker see this: https://answall.com/q/168531/101

  • @bigown ops. Caught by common sense, when it comes to mind the ordered word also comes the definition of Sorted.

  • 1

    @Wilker normal, everyone thinks the same thing, I thought for many years. In fact when talking ordered everyone thinks of the classified. I do not know what was the intention of Renan, but by wanting or unintentional he wrote right.

  • 2

    I think people tend to think that sorting is the same as sorting due to the alphabetic "order", which is the first classification that everyone learns. But my concept is the exact one of the question mentioned.

9

Array is a primitive data structure about which you quoted (Listas, Tuplas) and others Objetos which store data can be built.

Language-independent, array, is nothing more than a continuous space in the reserved memory to store data. This way they can be accessed quickly and directly only using the desired position index.

Unlike other complex structures, such as lists, which need to be accessed the previous or later elements (depending on the type of list).


Below can be seen the representation of this structure in memory as well as the access to the elements from the point of view of the programmer and the operating system.

Note that the index value in most languages starts from the 0. 1d Array

  • 1

    I agree, so I quoted commonly, wanted to give the sense of common sense. I think it best to edit to make clear.

5

Interesting thing about it. First, let’s think about array in its essence.
We know that a variable is a name, a tag that points to a memory location that stores a value.
Studying the language C, from which derive most of the most widely used languages today, either by syntax or by having AIDS based on it, we will see that a array is a pointer pointing to a continuous region of memory, with fixed size, where we store several data/objects of the same type, and to facilitate their identification, we use the same variable name.
The definition @Wilker put forth explains this well:

continuous space in the reserved memory to store data

Well, if we take this as an initial concept, a variable that points to a group of objects of the same type can be understood with a array.

Here is a very important feature: continuous and fixed storage. You declare an array, for example like this: int[2] x, what would be an array of two values of the type int, identified by the name of "x".
Here we can already differentiate a list, which is dynamic, ie, allows to add/remove objects, which characterizes an object that is not fixed, and can not be kept in a continuous region of memory, obviously because of being dynamic.

So we can say, in a very concise way, that a list would be a array dynamic. Therefore, in my humble opinion, based on these concepts I quote, I could say that:

  • array: object pointing to a sequence of objects of the same type, with fixed size, stored continuously;
  • list: object that stores a dynamic sequence of objects of the same type, stored in a noncontinuous manner.

We also know that in many languages (such as Java and C#) list objects have a number of operations that facilitate the job, such as searching and sorting, which in the case of a array would have to be implemented manually, this also highlights the difference between the two.

1

But after all, what is an Array? Is it a sequentially indexed list? Or is it a manually indexed item container (like in PHP)?

Array has its origin in algebra as matrix:

Matrix : "Arrangement of m.n mathematical elements arranged in a rectangular or square frame containing rows and n columns."

List of matrix types

Would it be correct to say that the PHP Language Array concept is wrong? If it is "wrong", what would be the most appropriate name for the "Array" of this language?

I believe the array in PHP falls within the definition of matriz.

List and Array is the same thing? If not, what is the difference?

Lista without an index is just a list a Array List is a matrix.

  • 1

    Constructive criticisms are welcome (even through the negative), could explain the reason for the negative for me to improve my response and maybe reverse it?

  • 1

    Easy to press down hard arrow is to show where the error is.

  • I will opine, see in the other answers that the PHP array is associative, its index is not necessarily numbered, in general it is a key, like a hash table. And Array List would not be an array, at least in Java it would be a list (elastic data structure, which can change size) based on an array (array, fixed structure). That’s what the staff must have got in trouble with the answer.

  • @Piovezan knows which translation of the name array?

  • Arrangement. Arrays are indexed by ordinals. Matrix is a two-dimensional array. The PHP array does not fit into being indexed by ordinals (although it may be).

  • @Piovezan well, actually I’m not understanding what you really mean. In my answer I say that the php array is part of a base concept called matrix, and there are several types of matrices. All these concepts tuples, vectors, array are matrix derivatives. The matrix is not necessarily two-dimensional, the simplest type of matrix is one-way. Regardless of the language the basic concept is matrix, for the simple fact that memory is a matrix. See I have no intention of making what I say understood as an absolute truth...

  • ...this is my interpretation of my research. https://en.wikipedia.org/wiki/Array_data_structure

  • Well I don’t want to get into the merits of the question, I also took that matrix is two-dimensional Wikipedia in Portuguese and I don’t know if there is correct. I only raised the points that I found discrepant of your answer in a read on top because you asked for feedback (of course I was not the one who objected) and I don’t want to delve into.

  • @Piovezan is calm, I do not care for negatives, I call if negative and say nothing. The fact that people expect complexity for something that is simple. And my answer is simple... At the end of the computation account in my understanding there is no data structure that is not based on a matrix, further I believe that everything in the universe starts from a matrix ... The complexity is in the manipulation and access to matrix... But if you are a programmer should delve deeper, I will still devote more to this theme.

Show 4 more comments

Browser other questions tagged

You are not signed in. Login or sign up in order to post.