Каково фактическое определение массива?

Question

Возможный дубликат:
Массивы, какой смысл?

Я пытался задать этот вопрос раньше в чем разница между массивом и списком? но мой вопрос был закрыт до достижения окончательного ответа ( подробнее об этом).

Я пытаюсь понять, что на самом деле означает слово "массив" в информатике. Я пытаюсь найти ответ без обсуждения в соответствии с духом этого сайта. То, что я спрашиваю, не зависит от языка, но вы можете опираться на свои знания о том, что массивы используются на разных языках, которые вы использовали.

Способы обдумать этот вопрос:

• Представьте, что вы разрабатываете новый язык программирования и решаете внедрить в него массивы; что это значит, что они делают? Какими будут свойства и возможности этих вещей. Если это зависит от типа языка, как так?
• Что делает массив массивом?
• Когда массив не массив? Когда это, например, список, вектор, таблица, карта или коллекция?

Возможно, нет единого точного определения, что такое массив, если это так, то есть ли какие-либо стандартные или почти стандартные предположения или что такое массив? Есть ли хотя бы общие зоны? Может быть, есть несколько определений, если это так, я ищу наибольшую точность в каждом из них.

Примеры языков:

(Поправьте меня, если я ошибаюсь по любому из них).

• Массивы C представляют собой непрерывные блоки памяти одного типа, которые могут быть пройдены с использованием арифметики указателя или доступны в определенной точке смещения. Они имеют фиксированный размер.
• Массивы в JavaScript, Ruby и PHP имеют переменный размер и могут хранить объекты / скаляры любого типа, которые они также могут увеличивать или удалять элементы из них.
• Массивы PHP бывают двух типов: числовые и ассоциативные. Ассоциативные массивы имеют элементы, которые хранятся и извлекаются со строковыми ключами. Числовые массивы имеют элементы, которые хранятся и извлекаются с целыми числами. Интересно, если у вас есть: $eg = array('a', 'b', 'c') и ты unset($eg[1]) вы все еще получаете 'c' с $eg[2], только сейчас $eg[1] не определено (Ты можешь позвонить array_values() переиндексировать массив). Вы также можете смешивать строковые и целочисленные ключи.

На этой стадии своего рода подозрения, что массивы C являются единственным истинным массивом здесь, и что, строго говоря, массив должен быть массивом, он должен иметь все характеристики, которые я упомянул в этом первом пункте. Если это так, то, опять-таки, это подозрения, которые я ожидаю подтвердить или отклонить - массивы в JS и Ruby на самом деле являются векторами, а PHP-массивы, вероятно, являются таблицами какого-то рода.

Последнее замечание: я сделал это сообщество вики, поэтому, если вместо комментариев нужно несколько раз редактировать ответы, сделайте это. Консенсус в порядке здесь.

Answer 1

Массив | шра |

имя существительное

1 Впечатляющая демонстрация или ассортимент вещей определенного типа: по этой теме имеется огромное количество литературы | изумительный выбор.

2 упорядоченное расположение, в частности

• расположение войск.
  2. Математика: расположение величин или символов в строках и столбцах; матрица.
  3. Вычислительный: упорядоченный набор связанных элементов.
  4. Закон: список присяжных заседателей.

3 поэтические / литературные или красивые одежды: он был одет в прекрасную одежду. глагол

1. [транс. ] (обычно в массиве) отображать или упорядочивать (вещи) определенным образом: по всему столу располагался буфет | силы сосредоточились против него.
2. [транс. ] (обычно в форме) одеть кого-то (указанную одежду): они были в национальной венгерской одежде.
3. [транс. ] Закон император (жюри). ПРОИСХОЖДЕНИЕ Среднеанглийский (в значениях [готовность] и [место в готовности]): от старофранцузского ареи (существительное), арер (глагол), на основе латинского ad- "в сторону" + германская база, означающая "подготовить".

Answer 2

Это или должно быть, все об абстракции

Там на самом деле спрятан хороший вопрос, действительно хороший, и он поднимает язык, который у меня был в течение долгого времени.

И становится все хуже, а не лучше.

ОК: есть что-то скромное и широко неуважительное, что Фортран понял, что мои любимые языки, такие как Ruby, все еще ошибаются: они используют различный синтаксис для вызовов функций, массивов и атрибутов. Насколько это абстрактно? В фортране function(1) имеет тот же синтаксис, что и array(1), так что вы можете изменить один на другой, не изменяя программу. (Я знаю, не для заданий, и в случае с Фортраном это, вероятно, был случай тупых наборов символов перфокарты, а не чего-то преднамеренного.)

Дело в том, я действительно не уверен, что x.y, x[y], а также x(y) должен иметь другой синтаксис. В чем преимущество присоединения конкретной абстракции к определенному синтаксису? Чтобы сделать больше рабочих мест для программистов IDE, работающих над преобразованиями рефакторинга?

Сказав все это, легко определить array, В своей первой нормальной форме это непрерывная последовательность элементов в памяти, доступ к которой осуществляется с помощью числового смещения и с использованием синтаксиса, зависящего от языка. В более высоких нормальных формах это атрибут объекта, который отвечает на типично числовое сообщение.

Answer 3

Массив - это упорядоченная коллекция элементов данных, проиндексированных целым числом. Невозможно быть уверенным в чем-то большем. Проголосуйте за этот ответ, вы считаете, что это единственный разумный ответ на этот вопрос.

Answer 4

От FOLDOC:

массив

1. < программирование > Набор элементов данных одинакового типа, различаемых по их индексам (или "индексам"). Количество измерений, которые может иметь массив, зависит от языка, но обычно не ограничено.

Массив является своего рода агрегированным типом данных. Одна обычная переменная (" скаляр ") может рассматриваться как нульмерный массив. Одномерный массив также известен как " вектор ".

Ссылка на элемент массива записывается как A[i,j,k], где A - имя массива, а i, j и k - индексы. Язык Си отличается тем, что каждый индекс написан в отдельных скобках, например, A[i][j][k]. Это выражает тот факт, что в C N-мерный массив на самом деле является вектором, каждый из элементов которого является N-1-мерным массивом.

Элементы массива обычно хранятся смежно. Языки различаются в зависимости от того, изменяется ли самый левый или самый правый индекс наиболее быстро, то есть хранится ли каждая строка непрерывно или каждый столбец (для двумерного массива).

Массивы подходят для хранения данных, к которым необходимо обращаться в непредсказуемом порядке, в отличие от списков, которые лучше всего использовать при последовательном доступе. Индексы массива представляют собой целые числа, обычно натуральные числа, тогда как элементы ассоциативного массива идентифицируются строками.

2. < архитектура > Массив процессора, не путать с процессором массива.

Также обратите внимание, что в некоторых языках, когда они говорят "массив", они на самом деле означают " ассоциативный массив ":

ассоциативный массив

< программирование > (или "хэш", "карта", "словарь") Массив, где индексы не просто целые числа, но могут быть произвольными строками.

У awk и его потомков (например, Perl) есть ассоциативные массивы, которые реализованы с использованием хэш-кодирования для более быстрого поиска.

Answer 5

Если вы игнорируете, как языки программирования моделируют массивы и списки, и игнорируете детали реализации (и соответствующие характеристики производительности) абстракций, тогда понятия массива и списка неразличимы.

Если вы введете детали реализации (все еще не зависящие от языка программирования), вы сможете сравнить структуры данных, такие как связанные списки, списки массивов, регулярные массивы, разреженные массивы и так далее. Но тогда вы больше не сравниваете массивы и списки как таковые.

На мой взгляд, о разнице между массивами и списками можно говорить только в контексте языка программирования. И, конечно, вы говорите о массивах и списках, поддерживаемых этим языком. Вы не можете обобщать на любой другой язык.

Короче говоря, я думаю, что этот вопрос основан на ложной предпосылке и не имеет полезного ответа.

РЕДАКТИРОВАТЬ: в ответ на комментарии Олли:

Я не говорю, что бесполезно использовать слова "массив" и "список". Я говорю, что слова не имеют и не могут иметь точных и четких определений... кроме как в контексте конкретного языка программирования. Хотя вы хотели бы, чтобы эти два слова имели различное значение, это факт, что они не имеют. Просто взгляните на то, как на самом деле используются слова. Кроме того, попытка навязать миру новый набор определений обречена на провал.

Моя точка зрения на реализацию заключается в том, что когда мы сравниваем и сопоставляем различные реализации массивов и списков, мы делаем именно это. Я не говорю, что это бесполезно. Я говорю о том, что когда мы сравниваем и сопоставляем различные реализации, мы не должны зацикливаться на том, называем ли мы их массивами, списками или чем-то еще. Скорее мы должны использовать термины, с которыми мы можем согласиться... или не использовать термины вообще.

Для меня "массив" означает "упорядоченный набор вещей, которые, вероятно, эффективно индексируются", а "список" означает "упорядоченный набор вещей, которые могут быть эффективно индексируемы". Но есть примеры массивов и списков, которые идут против тренда; например, PHP-массивы с одной стороны и Java ArrayLists с другой стороны. Поэтому, если я хочу быть точным... в контексте, не зависящем от языка, мне нужно поговорить о "C-подобных массивах" или "связанных списках" или какой-либо другой терминологии, которая проясняет, какую структуру данных я действительно имею в виду. Термины "массив" и "список" бесполезны, если я хочу быть ясным.

Answer 6

Массив:

1. это конечная коллекция элементов
2. элементы упорядочены, и это их единственная структура
3. элементы одного типа
4. поддерживается эффективный произвольный доступ
5. не ожидает эффективных вставок
6. может или не может поддержать добавление

(1) отличает массивы от таких вещей, как итераторы или генераторы. (2) отличает массивы от множеств. (3) отличает массивы от таких вещей, как кортежи, где вы получаете int и строку. (4) отличает массивы от других типов списков. Может быть, это не всегда так, но программист ожидает, что произвольный доступ - это постоянное время. (5) и (6) просто чтобы отрицать дополнительные требования.

Answer 7

Я бы сказал, что реальный массив хранит значения в непрерывной памяти. Все остальное называется массивом, потому что его можно использовать как массив, но на самом деле это не так ("массивы" в PHP определенно не являются реальными массивами (неассоциативными)). Векторы и тому подобное являются расширениями массивов, добавляя дополнительную функциональность.

Answer 8

Массив является контейнером, и объекты, которые он содержит, не имеют никаких отношений, кроме порядка; объекты хранятся в непрерывном пространстве абстрактно (высокий уровень, конечно, низкий уровень также может быть непрерывным), так что вы можете получить к ним доступ через слот [x,y,z...]. например, для массива [2,3,5,7,1] вы можете получить 5, используя slot[2] (slot[3] в некоторых языках).

для списка, контейнера тоже, каждый объект (ну точно, каждый объект-держатель, такой как слот или узел), который он содержит, имеет индикаторы, которые "указывают" на другой объект (ы), и это является основным отношением; как на высоком, так и на низком уровне пространство не является непрерывным, но может быть непрерывным; поэтому доступ к слоту [x, y, z...] не рекомендуется. например, для |-2-3-5-7-1-| вам нужно совершить путешествие от первого объекта к третьему, чтобы получить 5.