В компьютерном программировании , массив нарезка является операцией , которая извлекает подмножество элементов в массиве и пакеты них в качестве еще, возможно массива в другом измерении от оригинала.
Распространенными примерами нарезки массива являются извлечение подстроки из строки символов, « ell » в «h ell o», извлечение строки или столбца из двумерного массива или извлечение вектора из матрицы .
В зависимости от языка программирования срез массива может состоять из непоследовательных элементов. Также, в зависимости от языка, элементы нового массива могут иметь псевдонимы (т. Е. Совместно использовать память) с элементами исходного массива.
Подробности
Для «одномерных» (одноиндексированных) массивов - векторов, последовательностей, строк и т. Д. - наиболее распространенной операцией нарезки является извлечение нуля или более последовательных элементов. Таким образом, если у нас есть вектор, содержащий элементы (2, 5, 7, 3, 8, 6, 4, 1), и мы хотим создать срез массива с 3-го по 6-й элементы, мы получим (7, 3, 8, 6). В языках программирования, которые используют схему индексации на основе 0, срез будет от индекса 2 до 5 .
Сокращение диапазона любого индекса до одного значения эффективно устраняет этот индекс. Эту функцию можно использовать, например, для извлечения одномерных срезов (векторов: в 3D, строки, столбцы и трубки [1] ) или двумерных срезов (прямоугольных матриц) из трехмерного массива. Однако, поскольку диапазон может быть указан во время выполнения, для языков с проверкой типов может потребоваться явная (во время компиляции) нотация, чтобы фактически исключить тривиальные индексы.
Общая нарезка массива может быть реализована (независимо от того, встроена она в язык или нет) путем ссылки на каждый массив через допинговый вектор или дескриптор - запись, которая содержит адрес первого элемента массива, а затем диапазон каждого индекса и соответствующий коэффициент в формула индексации. Этот метод также позволяет немедленно переместить массив, инвертировать индекс, подвыборку и т. Д. Для таких языков, как C , где индексы всегда начинаются с нуля, допинговый вектор массива с d индексами имеет как минимум 1 + 2 d параметров. Для языков, которые допускают произвольные нижние границы для индексов, таких как Паскаль , допинговый вектор требует 1 + 3 d записей.
Если абстракция массива не поддерживает истинные отрицательные индексы (как, например, массивы Ada и Pascal ), то отрицательные индексы для границ среза для данного измерения иногда используются для указания смещения от конца массива в это измерение. В схемах, основанных на 1, -1 обычно обозначает предпоследний элемент, в то время как в системе с основанием 0 это будет означать самый последний элемент.
История
Понятие нарезки наверняка было известно еще до изобретения компиляторов . Нарезка как функция языка, вероятно, началась с FORTRAN (1957 г.), скорее как следствие несуществующей проверки типов и диапазонов, чем намеренно. Эта концепция также упоминалась в предварительном отчете для IAL (АЛГОЛ 58) в том смысле, что синтаксис позволял опускать один или несколько индексов элемента массива (или, если на то пошло, вызова процедуры) при использовании в качестве фактического параметр.
Кеннет Айверсон «s APL (1957) был очень гибкий многомерный массив нарезку, которые внесли большой вклад в выразительную силу и популярность языка.
Алгол 68 (1968) представил комплексные функции нарезки и обрезки многомерных массивов.
Средства нарезки массивов включены в несколько современных языков, таких как Ada 2005 , Cobra , D , Fortran 90 , Go , Rust , Julia , MATLAB , Perl , Python , S-Lang , Windows PowerShell и математические / статистические языки GNU Octave , S и R .
Хронология нарезки на разных языках программирования
1966: Fortran 66
Программисты на Фортране 66 могли использовать только разрезание матриц по строкам, и то только при передаче этой строки в подпрограмму :
ПОДПРОГРАММА ПЕЧАТЬ V ( VEC , LEN ) REAL VEC ( * ) PRINT * , ( VEC ( I ), I = 1 , LEN ) END ГЛАВНЫЙ ПАРАМЕТР ПРОГРАММЫ ( LEN = 3 ) РЕАЛЬНАЯ МАТРИЦА ( LEN , LEN ) МАТРИЦА ДАННЫХ / 1 , 1 , 1 , 2 , 4 , 8 , 3 , 9 , 27 / ВЫЗОВ ПЕЧАТЬ V ( МАТРИЦА ( 1 , 2 ), LEN ) КОНЕЦ
Результат:
2,000000 4,000000 8,000000
Обратите внимание, что в FORTRAN 66 нет вектора допинга, поэтому длина среза также должна быть передана в качестве аргумента - или каким-либо другим способом - в SUBROUTINE
. Паскаль 1970-х и Си имели аналогичные ограничения.
1968: Алгол 68
Итоговый отчет Algol68 содержит ранний пример нарезки, срезы указаны в форме:
[нижняя граница: верхняя граница] ¢ для компьютеров с расширенными наборами символов ¢
или же:
(НИЖНЯЯ ОГРАНИЧЕНИЕ..ВЕРХНЯЯ ОГРАНИЧЕНИЕ) # ДЛЯ КОМПЬЮТЕРОВ, КОТОРЫЕ СОСТОЯЕТ ТОЛЬКО 6 БИТНЫХ СИМВОЛОВ . #
Обе границы являются включительными и могут быть опущены, и в этом случае они по умолчанию соответствуют объявленным границам массива. Ни функция шага, ни псевдонимы диагональных срезов не являются частью пересмотренного отчета.
Примеры:
[3, 3] вещественное a: = ((1, 1, 1), (2, 4, 8), (3, 9, 27)); # объявление переменной матрицы # [,] real c = ((1, 1, 1), (2, 4, 8), (3, 9, 27)); # постоянная матрица, размер подразумевается #
ref [] вещественная строка: = a [2,]; # псевдоним / ссылка на срез строки # ref [] real col2 = a [, 2]; # постоянный псевдоним / ссылка на второй столбец #
print ((a [:, 2], новая строка)); # второй фрагмент столбца # print ((a [1⌈a,:], новая строка)); # последний фрагмент строки # print ((a [:, 2⌈a], newline)); # последний фрагмент столбца # print ((a [: 2,: 2], newline)); # ведущая подматрица 2 на 2 "срез" #
+1.0000 10 +0 +4.0000 10 +0 +9.0000 10 +0+3.0000 10 +0 +9.0000 10 +0 +2.7000 10 +1+1.0000 10 +0 +8.0000 10 +0 +2.7000 10 +1+1.0000 10 +0 +1.0000 10 +0 +2.0000 10 +0 +4.0000 10 +0
1970-е: MATLAB
> A = round ( rand ( 3 , 4 , 5 ) * 10 ) % 3x4x5 трехмерный или кубический массив > A (:, :, 3 ) % 3x4 двумерный массив по первому и второму измерениямans = 8 3 5 7 8 9 1 4 4 4 2 5> A (:, 2 : 3 , 3 ) % 3x2 двумерный массив по первому и второму измерениямans = 3 5 9 1 4 2> A ( 2 : end , :, 3 ) % 2x4 двумерный массив с использованием ключевого слова end; работает с GNU Octave 3.2.4ans = 6 1 4 6 10 1 3 1> A ( 1 , :, 3 ) % одномерный массив по второму измерениюans = 8 3 5 7> A ( 1 , 2 , 3 ) % одно значение ans = 3
1976: S / R
Массивы в S и GNU R всегда основаны на единице, поэтому индексы нового среза будут начинаться с единицы для каждого измерения, независимо от предыдущих индексов. Размеры, длина которых равна единице, будут отброшены (если drop = FALSE). Имена размеров (если есть) будут сохранены.
> <- массив ( 1 : 60 , тусклый = C ( 3 , 4 , 5 )) # 3x4x5 трехмерной или кубической массив > [, , 3 ] # 3x4 двумерный массив вдоль первого и второго измерений [1 ] [, 2] [, 3] [, 4] [1,] 25 28 31 34 [2,] 26 29 32 35 [3,] 27 30 33 36 > A [, 2 : 3 , 3 , drop = FALSE ] # 3x2x1 подмножество кубических массивов (сохраненные размеры),, 1 [, 1] [, 2] [1,] 28 31 [2,] 29 32 [3,] 30 33 > A [, 2 , 3 ] # одномерный массив по первому измерению [1] 28 29 30 > A [ 1 , 2 , 3 ] # одно значение [1] 28
1977 год: Fortran 77
Стандарт Fortran 77 представил возможность нарезать и объединять строки:
ГЛАВНАЯ ПЕЧАТЬ ПРОГРАММЫ * , 'ABCDE' ( 2 : 4 ) КОНЕЦ
Производит:
BCD
Такие строки могут быть переданы посредством ссылки в другую подпрограмму, длина также будет прозрачно передана подпрограмме как своего рода короткий вектор допинга.
ПОДПРОГРАММА ПЕЧАТЬ S ( STR ) СИМВОЛ * ( * ) STR PRINT * , STR ENDПРОГРАММА ГЛАВНЫЙ ВЫЗОВ ПЕЧАТЬ S ( 'ABCDE' ( 2 : 4 )) КОНЕЦ
Снова выдает:
BCD
1979: Sinclair BASIC ZX80 / 81 / Spectrum
Стандартное ПЗУ ZX80 / 81 / Spectrum предлагает BASIC с возможностью нарезки и объединения строк:
в части команды (x TO y), которая указывает на необходимый срез массива, значения x и y могут быть опущены, давая смысл использовать все связанные ячейки массива (FROM x TO end) или (begin TO y). С многомерными массивами нарезка возможна только с измерением последнего уровня.
10 ПОЗВОЛЯТЬ $ = "ABCDE" (от 2 до 4 ) 20 НАПЕЧАТАТЬ $
Производит:
BCD
10 ПОЗВОЛЯТЬ a $ = "ABCDE" 20 ПОЗВОЛЯТЬ b $ = a $ ( 4 TO ) + a $ ( 2 TO 3 ) + a $ ( 1 ) 30 ПЕЧАТЬ b $
Производит:
DEBCA
1983: Ada 83 и выше
Ada 83 поддерживает срезы для всех типов массивов. Подобно Fortran 77, такие массивы могут передаваться по ссылке в другую подпрограмму, длина также будет прозрачно передана в подпрограмму как своего рода короткий вектор допинга.
с Text_IO ; процедура Main is Text : String : = "ABCDE" ; начать Text_IO . Put_Line ( Текст ( 2 .. 4 )); конец Main ;
Производит:
BCD
Примечание. Поскольку индексы в Ada основаны на n Text (2 .. 4)
, результатом будет массив с базовым индексом 2.
Определение для Text_IO.Put_Line
:
пакет Ada.Text_IO - это Процедура Put_Line ( Пункт : в строках );
Определение для String
:
пакет Standard - это подтип Положительный - диапазон целых чисел 1 .. Целое число ' Последний ; типа Строка это массив ( положительный диапазон <>) из символов ; прагма Pack ( String );
Поскольку Ада поддерживает истинно отрицательные индексы, так как в type History_Data_Array is array (-6000 .. 2010) of History_Data;
нем не придает особого значения отрицательным индексам. В приведенном выше примере термин Some_History_Data (-30 .. 30)
будет срезать период History_Data
с 31 г. до н.э. до 30 г. н.э. (поскольку нулевого года не было, номер года 0 фактически относится к 1 г. до н.э. ).
1987: Perl
Если мы имеем
@a = ( 2 , 5 , 7 , 3 , 8 , 6 , 4 );
как указано выше, тогда первые 3 элемента, средние 3 элемента и последние 3 элемента будут:
@a [ 0 .. 2 ]; # (2, 5, 7) @a [ 2 .. 4 ]; # (7, 3, 8) @a [ - 3 ..- 1 ]; # (8, 6, 4)
Perl поддерживает индексы отрицательного списка. Индекс -1 - это последний элемент, -2 - предпоследний элемент и т. Д. Кроме того, Perl поддерживает срезы на основе выражений, например:
@a [ 3 .. $ # a ]; # 4-й элемент до конца (3, 8, 6, 4) @a [ grep { ! ( $ _ % 3 ) } ( 0 ... $ # a ) ]; # 1-й, 4-й и 7-й элемент (2,3,4) @a [ grep { ! (( $ _ + 1 ) % 3 ) } ( 0 .. $ # a ) ]; # каждый 3-й элемент (7,6)
1991: Python
Если у вас есть следующий список:
>>> nums = [ 1 , 3 , 5 , 7 , 8 , 13 , 20 ]
Затем можно выполнить нарезку, используя нотацию, аналогичную извлечению элемента:
>>> nums [ 3 ] # без нарезки 7 >>> nums [: 3 ] # от индекса 0 (включительно) до индекса 3 (исключая) [1, 3, 5] >>> nums [ 1 : 5 ] [3 , 5, 7, 8] >>> НУМС [ - 3 :] [8, 13, 20]
Обратите внимание, что Python допускает использование отрицательных индексов списка. Индекс -1 представляет последний элемент, -2 - предпоследний элемент и т. Д. Python также допускает свойство step, добавляя дополнительное двоеточие и значение. Например:
>>> nums [ 3 :] [7, 8, 13, 20] >>> nums [ 3 ::] # == nums [3:] [7, 8, 13, 20] >>> nums [:: 3 ] # начиная с индекса 0 и получая каждый третий элемент [1, 7, 20] >>> nums [ 1 : 5 : 2 ] # от индекса 1 до индекса 5 и получая каждый второй элемент [3, 7]
Синтаксис stride ( nums[1:5:2]
) был введен во второй половине 1990-х годов в результате запросов, выдвинутых научными пользователями в Python "matrix-SIG" (группа особого интереса). [2]
Семантика срезов потенциально различается в зависимости от объекта; новая семантика может быть введена при перегрузке оператора индексации. В стандартных списках Python (которые представляют собой динамические массивы ) каждый фрагмент является копией. Срезы массивов NumPy , напротив, представляют собой представления одного и того же базового буфера.
1992: Fortran 90 и выше
В Fortran 90 фрагменты задаются в виде
lower_bound : upper_bound [: шаг ]
Обе границы являются включительными и могут быть опущены, и в этом случае они по умолчанию соответствуют объявленным границам массива. По умолчанию значение шага равно 1. Пример:
вещественный , размер ( m , n ) :: a ! объявление матрицы print * , a (:, 2 ) ! второй столбец print * , a ( m , :) ! последняя строка печати * , (: 10 , : 10 ) ! ведущая подматрица 10 на 10
1994: Аналитика
Каждое измерение значения массива в Analytica идентифицируется индексной переменной. При нарезке или подписке синтаксис определяет измерение (а), по которому вы выполняете нарезку или подпись, путем именования измерения. Такой как:
Индекс I: = 1..5 {Определение числового индекса}Индекс J: = ['A', 'B', 'C'] {Определение индекса с текстовым значением}Переменная X: = Array (I, J, [[10, 20, 30], [1, 2, 3], ....]) {Определение двумерного значения}X [I = 1, J = 'B'] -> 20 {Индекс для получения единственного значения}X [I = 1] -> Array (J, [10, 20, 30]) {Вырезать одномерный массив. }X [J = 2] -> Array (I, [20, 2, ....]) {Вырезать одномерный массив по другому измерению. }X [I = 1..3] {Вырежьте первые четыре элемента над I со всеми элементами над J}
Именование индексов при нарезке и индексировании аналогично именованию параметров в вызовах функций вместо того, чтобы полагаться на фиксированную последовательность параметров. Одно из преимуществ именования индексов при нарезке состоит в том, что программисту не нужно запоминать последовательность индексов в многомерном массиве. Более глубокое преимущество состоит в том, что выражения обобщаются автоматически и безопасно, не требуя перезаписи при изменении количества измерений X.
1998: S-Lang
Нарезка массивов появилась в версии 1.0. Более ранние версии не поддерживали эту функцию.
Предположим, что A - это одномерный массив, такой как
A = [1:50]; % A = [1, 2, 3, ... 49, 50]
Затем можно создать массив B из первых 5 элементов A, используя
B = A [[: 4]];
Точно так же B может быть назначен массиву из последних 5 элементов A через:
B = A [[- 5:]];
Другие примеры 1-мерного нарезания включают:
A [-1]% Последний элемент A A [*]% Все элементы A A [[:: 2]]% Все четные элементы A A [[1 :: 2]]% Все нечетные элементы A A [[- 1 :: - 2]]% Все четные элементы в обратном порядке A [[[0: 3], [10:14]]]% Элементы 0–3 и 10–14
Нарезка многомерных массивов работает аналогично:
A [-1, *]% Последняя строка A Массив [[1: 5], [2: 7]]% 2d с использованием строк 1–5 и столбцов 2–7. A [[5: 1: -1], [2: 7]]% То же, что и выше, за исключением того, что строки перевернуты
Индексы массивов также могут быть массивами целых чисел. Например, предположим, что I = [0:9]
это массив из 10 целых чисел. То A[I]
эквивалентно массиву из первых 10 элементов A
. Практическим примером этого является такая операция сортировки, как:
I = сортировка_массивов (A); % Получить список индексов сортировки B = A [I]; % B - отсортированная версия A C = A [сортировка_массивов (A)]; % То же, что и выше, но более лаконично.
1999: D
Рассмотрим массив:
int [] a = [ 2 , 5 , 7 , 3 , 8 , 6 , 4 , 1 ];
Отрежьте от этого кусочек:
int [] b = a [ 2 .. 5 ];
и содержимое b
будет [7, 3, 8]
. Первый индекс среза - включающий, второй - исключающий.
auto c = a [$ - 4 .. $ - 2 ];
означает, что динамический массив c
теперь содержит, [8, 6]
потому что внутри [] $
символ указывает длину массива.
Срезы массива D имеют псевдонимы исходного массива, поэтому:
b [ 2 ] = 10 ;
означает, что a
теперь есть содержимое [2, 5, 7, 3, 10, 6, 4, 1]
. Чтобы создать копию данных массива, а не только псевдоним, выполните:
авто б = а [ 2 .. 5 ]. dup ;
В отличие от Python, границы среза D не насыщаются, поэтому код, эквивалентный этому коду Python, является ошибкой в D:
>>> d = [ 10 , 20 , 30 ] >>> d [ 1 : 5 ] [20, 30]
2004: Суперколлайдер
В языке программирования SuperCollider реализованы некоторые концепции J / APL . Нарезка выглядит следующим образом:
a = [ 3 , 1 , 5 , 7 ] // присваиваем массив переменной a a [ 0 .. 1 ] // возвращаем первые два элемента a a [.. 1 ] // возвращаем первые два элемента a: ноль можно опустить a [ 2 ..] // вернуть элемент с 3 до последнего a [[ 0 , 3 ]] // вернуть первый и четвертый элементыa [[ 0 , 3 ]] = [ 100 , 200 ] // заменяем первый и четвертый элементы a [ 2 ..] = [ 100 , 200 ] // заменяем два последних элемента a// присваиваем многомерный массив переменной a a = [[ 0 , 1 , 2 , 3 , 4 ], [ 5 , 6 , 7 , 8 , 9 ], [ 10 , 11 , 12 , 13 , 14 ], [ 15 , 16 , 17 , 18 , 19 ]]; а . ломтик ( 2 , 3 ); // берем срез с координатами 2 и 3 (возвращает 13) a . срез ( ноль , 3 ); // берем ортогональный срез (возвращает [3, 8, 13, 18])
2005: рыба
Массивы в fish всегда основаны на единице, поэтому индексы нового среза будут начинаться с единицы , независимо от предыдущих индексов.
> set A ( seq 3 2 11 ) # $ A - это массив со значениями 3, 5, 7, 9, 11 > echo $ A [( seq 2 )] # Вывести первые два элемента $ A 3 5 > set B $ A [ 1 2 ] # $ B содержит первый и второй элементы $ A, т.е. 3, 5 > set -e A [ $ B ] ; echo $ A # Сотрите третий и пятый элементы $ A, выведите $ A 3 5 9
2006: Кобра
Cobra поддерживает нарезку в стиле Python. Если у вас есть список
nums = [ 1 , 3 , 5 , 7 , 8 , 13 , 20 ]
тогда первые 3 элемента, средние 3 элемента и последние 3 элемента будут:
nums [: 3 ] # равно [1, 3, 5] nums [ 2 : 5 ] # равно [5, 7, 8] nums [ - 3 :] # равно [8, 13, 20]
Cobra также поддерживает синтаксис в стиле нарезки для 'numeric for loops':
for i in 2 : 5 print i # выводит 2, 3, 4for j in 3 print j # выводит 0, 1, 2
2006: Windows PowerShell
В PowerShell массивы начинаются с нуля и могут быть определены с помощью оператора запятой:
PS> $ a = 2 , 5 , 7 , 3 , 8 , 6 , 4 , 1 PS> # Вывести первые два элемента $ a: PS> " $ ( $ a [ 0 , 1 ]) " 2 5 PS> # Возьмите срез с помощью оператора диапазона: PS> " $ ( $ a [ 2 .. 5 ]) " 7 3 8 6 PS> # Получите последние 3 элемента: PS> " $ ( $ a [- 3 ..- 1 ]) " 6 4 1 PS> # Вернуть содержимое массива в обратном порядке: PS> " $ ( $ a [( $ a . Length - 1 ) .. 0 ]) " # Длина - это свойство из System.Object [] 1 4 6 8 3 7 5 2
2009: Вперед
Go поддерживает синтаксис нарезки в стиле Python (за исключением того, что отрицательные индексы не поддерживаются). Массивы и срезы можно разрезать. Если у вас есть кусок
nums : = [] int { 1 , 3 , 5 , 7 , 8 , 13 , 20 }
тогда первые 3 элемента, средние 3 элемента, последние 3 элемента и копия всего среза будут:
nums [: 3 ] // равно [] int {1, 3, 5} nums [ 2 : 5 ] // равно [] int {5, 7, 8} nums [ 4 :] // равно [] int {8 , 13, 20} nums [:] // равно [] int {1, 3, 5, 7, 8, 13, 20}
Срезы в Go являются ссылочными типами, что означает, что разные срезы могут относиться к одному и тому же базовому массиву.
2010: Cilk Plus
Cilk Plus поддерживает синтаксис для нарезки массива как расширение для C и C ++.
array_base [ нижняя_ граница : длина [ : шаг ]] *
Нарезка Cilk Plus выглядит следующим образом:
A [ : ] // Весь вектор A B [ 2 : 6 ] // Элементы с 2 по 7 вектора B C [ : ] [ 5 ] // Столбец 5 матрицы C D [ 0 : 3 : 2 ] // Элементы 0, 2, 4 вектора D
Нарезка массива Cilk Plus отличается от Fortran двумя способами:
- второй параметр - это длина (количество элементов в срезе) вместо верхней границы, чтобы соответствовать стандартным библиотекам C;
- нарезка никогда не производит временного, и поэтому никогда не требует выделения памяти. Назначения должны быть либо неперекрывающимися, либо полностью перекрывающимися, в противном случае результат не определен.
2012: Юлия
Нарезка массива Julia похожа на MATLAB , но использует квадратные скобки. Пример:
julia> x = rand ( 4 , 3 ) 4x3 Массив {Float64,2}: 0,323877 0,186253 0,600605 0,404664 0,894781 0,0955007 0,223562 0,18859 0,120011 0,149316 0,779823 0,0690126julia> x [ : , 2 ] # получаем второй столбец. 4-элементный массив {Float64,1}: 0,186253 0,894781 0,18859 0,779823джулия> х [ 1 , : ] # получить первую строку. 1x3 Массив {Float64,2}: 0,323877 0,186253 0,600605julia> x [ 1 : 2 , 2 : 3 ] # получаем подматрицу, охватывающую строки 1,2 и столбцы 2,3 2x2 Array {Float64,2}: 0,186253 0,600605 0,894781 0,0955007
Смотрите также
- Сравнение языков программирования (массив) # Нарезка
Рекомендации
- ^ Чжан, Цзэминь; Аэрон, Щучин (15.03.2017). «Точное тензорное завершение с использованием t-SVD» . Транзакции IEEE по обработке сигналов . Институт инженеров по электротехнике и радиоэлектронике (IEEE). 65 (6): 1511–1526. DOI : 10.1109 / tsp.2016.2639466 . ISSN 1053-587X .
- ^ Миллман, К. Джаррод; Айвазис, Майкл (2011). «Python для ученых и инженеров» . Вычислительная техника в науке и технике . 13 (2): 9–12.