Как зная длину массива определить размер шага
Перейти к содержимому

Как зная длину массива определить размер шага

  • автор:

Как задать массиву длину по заполнению?

Как задать массиву длину по заполняемым данным? К примеру, генерируем случайные числа в массив i от 1 до 100 . создаем цикл for и который перебирает эти числа в массиве i и если есть одинаковые числа if (x == y) то переводит эти данные в новый массив K Проблема: Новый массив K не знает количество совпавших чисел в массиве i — следовательно, нельзя изначально указать ему его размер. Как создать функцию, где при новом найденном элементе из массива i генерировалась новая ячейка в массиве K ?

Отслеживать
user420361
задан 20 авг 2018 в 3:50
Yuriy Ivanishchev Yuriy Ivanishchev
35 11 11 бронзовых знаков

Т.е. если i[x] == i[y]( == i[z] и т.п., у нас же рандом, хоть все числа в массиве будут равны), то K[x] = i[x]?

20 авг 2018 в 4:37

Да. Но проблема в том, что массив K[x] = может быть до 10 элементов например. А нашло случайных одинаковых чисел 11.

20 авг 2018 в 4:39
Аааа, понятно. Используйте ArrayList, он динамический. habr.com/post/128269
20 авг 2018 в 4:44

принцип простой, изначально создаем массив определенной длины, например (25) и добавляем числа, пока не заполнится, если он будет полон, то создаем новый массив, с увеличением допустим n*2, и копируем туда данные, меняем ссылки. Такой же принцип используют динамические классы, либо применяют динамические структуры данных (односвязные списки, двусвязные списки) ArraList и ряд других классов

20 авг 2018 в 4:53
Но вместо того что бы так *******, просто почитай про коллекции(я кидал ссылку выше) и используй их.
20 авг 2018 в 5:09

3 ответа 3

Сортировка: Сброс на вариант по умолчанию

public static void main(String[] args) < int[] arr = new int[0]; for (int i = 0; i < 10; i++) < arr = extendArray(arr, i); >System.out.println(Arrays.toString(arr)); > public static int[] extendArray(int[] arr, int value)

Отслеживать
ответ дан 20 авг 2018 в 6:15
aleshka-batman aleshka-batman
2,868 10 10 серебряных знаков 21 21 бронзовый знак

Я предлагаю не использовать функцию System.arraycopy из предложенного ранее ответа, вместо чего можно создать временный массив размером как исходный, а потом записать в него только нужные значения в результате чего мы еще можем и подсчитать количество этих значений — это и будет размером результирующего массива, а его элементами — те, что мы записали во временный. Похожее решение уже предлагал в комментариях @Евгений-Федак. Генерацию чисел я пропущу, реализацию проверки одинаковости элементов массива тоже лучше использовать свою. Предположим, что указанный массив уже будет подан на вход следующему методу:

public int[] getEqualDigits(int[] i) < int resultCount = 0; // количество элементов в результирующем массиве K int[] tempArray = new int[i.length]; // создаем временный массив размером как исходный for (int j = 0; j < i.length; j++) < // перебираем последовательно все элементы массива if (i[j] == i[j++]) < // условие отбора может быть любым, реализация взята из вопроса tempArray[resultCount] = i[j]; // элементом временного массива будет тот, который удовлетворяет нашим требованиям resultCount++; >> int[] K = new int[resultCount]; // создаем результирующий массив нужного нам размера, полученного на предыдущем шаге for (int n = 0; n < resultCount; n++) < K[n] = tempArray[n]; // последовательно перепишем элементы из временного массива в результирующий >return K; > 

Отслеживать
ответ дан 2 янв 2020 в 18:34
1 1 1 бронзовый знак

Знать заранее количество элементов в массиве не обязательно, это зависит от алгоритма. Например, в данном случае количество элементов заранее не известно, и для данного алгоритма этим можно пренебречь:

// создаем новый массив на 100 элементов // и заполняем случайными числами от 1 до 100 int[] arr1 = IntStream.range(0, 100) .map(i -> (int) (1 + Math.random() * 100)) .toArray(); // выкидываем из первого массива // повторяющиеся элементы // и получаем второй массив int[] arr2 = Arrays.stream(arr1) .distinct() .toArray(); // количество элементов в первом // массиве больше, чем во втором System.out.println(arr1.length > arr2.length); // true 

Array.prototype.fill()

This feature is well established and works across many devices and browser versions. It’s been available across browsers since September 2015 .

Метод fill() заполняет все элементы массива от начального до конечного индексов одним значением.

Интерактивный пример

Синтаксис

arr.fill(value[, start = 0[, end = this.length]])

Параметры

Значение, заполняющее массив.

Необязательный параметр. Начальный индекс.

Необязательный параметр. Конечный индекс.

Возвращаемое значение

Описание

Элементы заполняются в полузакрытом интервале [ start , end ).

Метод fill принимает до трёх аргументов — value , start и end . Аргументы start и end являются необязательными со значениями по умолчанию, равными 0 и length объекта this соответственно.

Если аргумент start является отрицательным, он трактуется как length+start , где length — это длина массива. Если аргумент end является отрицательным, он трактуется как length+end .

Метод fill намеренно является обобщённым, он не требует, чтобы значение this внутри него было объектом Array .

Метод fill является изменяющим методом, он изменит объект this и вернёт его, а не просто вернёт копию.

Если аргумент value является объектом, то метод fill заполнит массив ссылками на этот объект.

Примеры

[1, 2, 3].fill(4); // [4, 4, 4] [1, 2, 3].fill(4, 1); // [1, 4, 4] [1, 2, 3].fill(4, 1, 2); // [1, 4, 3] [1, 2, 3].fill(4, 1, 1); // [1, 2, 3] [1, 2, 3].fill(4, 3, 3); // [1, 2, 3] [1, 2, 3].fill(4, -3, -2); // [4, 2, 3] [1, 2, 3].fill(4, NaN, NaN); // [1, 2, 3] [1, 2, 3].fill(4, 3, 5); // [1, 2, 3] Array(3).fill(4); // [4, 4, 4] [].fill.call(< length: 3 >, 4); // // Объекты заполняются по ссылке. var arr = Array(3).fill(<>) // [<>, <>, <>]; arr[0].hi = "hi"; // [< hi: "hi" >, < hi: "hi" >, < hi: "hi" >]

Полифил

if (!Array.prototype.fill) < Object.defineProperty(Array.prototype, 'fill', < value: function(value) < // Шаги 1-2. if (this == null) < throw new TypeError('this is null or not defined'); >var O = Object(this); // Шаги 3-5. var len = O.length >>> 0; // Шаги 6-7. var start = arguments[1]; var relativeStart = start >> 0; // Шаг 8. var k = relativeStart < 0 ? Math.max(len + relativeStart, 0) : Math.min(relativeStart, len); // Шаги 9-10. var end = arguments[2]; var relativeEnd = end === undefined ? len : end >> 0; // Шаг 11. var final = relativeEnd < 0 ? Math.max(len + relativeEnd, 0) : Math.min(relativeEnd, len); // Шаг 12. while (k < final) < O[k] = value; k++; >// Шаг 13. return O; > >); >

Если вам нужно поддерживать действительно устаревшие движки JavaScript, которые не поддерживают Object.defineProperty, то лучше вообще не использовать полифилы для методов Array.prototype, так как вы не можете сделать их не перечисляемыми.

Спецификации

Specification
ECMAScript Language Specification
# sec-array.prototype.fill

Совместимость с браузерами

BCD tables only load in the browser

Смотрите также

  • Array
  • TypedArray.prototype.fill()

Стоит ли сохранять длину массива в локальную переменную в C#

Пишут они это в надежде ускорить цикл, думая что создавая локальную переменную избавляют CLR от необходимости вызывать каждый раз геттер для Array.Length. Я решил раз и навсегда для себя понять стоит так делать или можно сэкономить своё время и написать без временной переменной.

Для начала рассмотрим два метода на C#:

public int WithoutVariable() < int sum = 0; for (int i = 0; i < array.Length; i++) < sum += array[i]; >return sum; > public int WithVariable() < int sum = 0; int length = array.Length; for (int i = 0; i < length; i++) < sum += array[i]; >return sum; >

И давайте посмотрим на код, который получается после JIT компиляции в релизе на .NET Framework 4.7.2 под LegacyJIT-x86:

WithoutVariable()
;int sum = 0;
xor edi , edi
;int i = 0;
xor esi , esi
;int[] localRefToArray = this.array;
mov edx , dword ptr [ ecx + 4 ]
;int arrayLength = localRefToArray.Length;
mov ecx , dword ptr [ edx + 4 ]
;if (arrayLength == 0) return sum;
test ecx , ecx
jle exit
;int arrayLength2 = localRefToArray.Length;
mov eax , dword ptr [ edx + 4 ]
;if (i >= arrayLength2)
; throw new IndexOutOfRangeException();
loop :
cmp esi , eax
jae 056e2d31
;sum += localRefToArray[i];
add edi , dword ptr [ edx + esi * 4 + 8 ]
;i++;
inc esi
;if (i < arrayLength) goto loop
cmp ecx , esi
jg loop
;return sum;
exit :
mov eax , edi
WithVariable()
;int sum = 0;
xor esi , esi
;int[] localRefToArray = this.array;
mov edx , dword ptr [ ecx + 4 ]
;int arrayLength = localRefToArray.Length;
mov edi , dword ptr [ edx + 4 ]
;int i = 0;
xor eax , eax
;if (arrayLength == 0) return sum;
test edi , edi
jle exit
;int arrayLength2 = localRefToArray.Length;
mov ecx , dword ptr [ edx + 4 ]
;if (i >= arrayLength2)
; throw new IndexOutOfRangeException();
loop :
cmp eax , ecx
jae 05902d31
;sum += localRefToArray[i];
add esi , dword ptr [ edx + eax * 4 + 8 ]
;i++;
inc eax
;if (i < arrayLength) goto loop
cmp eax , edi
jl loop
;return sum;
exit :
mov eax , esi

Скриншот сравнения в Meld

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

  • чтобы проверить на 0 (arrayLength);
  • и во временную переменную для проверки в условии цикла (arrayLength2);

Приведённый выше ассемблерный код навёл меня на некоторые мысли и я решил проверить ещё пару методов:

public int WithoutVariable() < int sum = 0; for(int i = 0; i < array.Length; i++) < sum += array[i] + array.Length; >return sum; > public int WithVariable() < int sum = 0; int length = array.Length; for(int i = 0; i < length; i++) < sum += array[i] + length; >return sum; >

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

WithoutVariable()
int sum = 0 ;
xor edi , edi
int i = 0 ;
xor esi , esi
int [ ] localRefToArray = this . array ;
mov edx , dword ptr [ ecx + 4 ]
int arrayLength = localRefToArray . Length ;
mov ebx , dword ptr [ edx + 4 ]
if ( arrayLength == 0 ) return sum ;
test ebx , ebx
jle exit
int arrayLength2 = localRefToArray . Length ;
mov ecx , dword ptr [ edx + 4 ]
if ( i >= arrayLength2 )
throw new IndexOutOfRangeException ( ) ;
loop :
cmp esi , ecx
jae 05562d39
int t = array [ i ] ;
mov eax , dword ptr [ edx + esi * 4 + 8 ]
t + = sum ;
add eax , edi
t + = arrayLength ;
add eax , ebx
sum = t ;
mov edi , eax
i ++ ;
inc esi
if ( i < arrayLength ) goto loop
cmp ebx , esi
jg loop
return sum ;
exit :
mov eax , edi
WithVariable()
int sum = 0 ;
xor esi , esi
int [ ] localRefToArray = this . array ;
mov edx , dword ptr [ ecx + 4 ]
int arrayLength = localRefToArray . Length ;
mov ebx , dword ptr [ edx + 4 ]
int i = 0 ;
xor ecx , ecx
if ( arrayLength == 0 ) ( return sum 😉
test ebx , ebx
jle exit
int arrayLength2 = localRefToArray . Length ;
mov edi , dword ptr [ edx + 4 ]
if ( i >= arrayLength2 )
throw new IndexOutOfRangeException ( ) ;
loop :
cmp ecx , edi
jae 04b12d39
int t = array [ i ] ;
mov eax , dword ptr [ edx + ecx * 4 + 8 ]
t + = sum ;
add eax , esi
t + = arrayLength ;
add eax , ebx
sum = t ;
mov esi , eax
i ++ ;
inc ecx
if ( i < arrayLength ) goto loop
cmp ecx , ebx
jl loop
return sum ;
exit :
mov eax , esi

Скриншот сравнения в Meld

Количество инструкций у этих двух методов и сами инструкции почти абсолютно одинаковые, опять различие есть только в порядке инициализации переменных и проверке на продолжение цикла. Причём можно заметить, что в расчёте sum учитывается только тот array.Length, который был взят самым первым. Очевидно что вот это:

int arrayLength2 = localRefToArray . Length ;
mov edi , dword ptr [ edx + 4 ]
if ( i >=arrayLength2 ) throw new IndexOutOfRangeException ( ) ;
cmp ecx , edi
jae 04b12d39

во всех четырёх методах — заинлайниная проверка на выход за пределы массива и она выполняется для каждого элемента массива.

Можно сделать уже первый вывод о том, что заводить дополнительную переменную чтобы пытаться ускорить выполнение цикла это пустая трата времени, т.к. компилятор всё сделает за нас. Заводить переменную с длиной цикла имеет смысл только чтобы увеличить читабельность кода.

Совершенно другая ситуация с ForEach. Возьмём три метода:

public int ForEachWithoutLength() < int sum = 0; foreach (int i in array) < sum += i; >return sum; > public int ForEachWithLengthWithoutLocalVariable() < int sum = 0; foreach (int i in array) < sum += i + array.Length; >return sum; > public int ForEachWithLengthWithLocalVariable() < int sum = 0; int length = array.Length; foreach (int i in array) < sum += i + length; >return sum; >

И посмотрим на их код после JIT:

ForEachWithoutLength()

;int sum = 0;
xor esi , esi
;int[] localRefToArray = this.array;
mov ecx , dword ptr [ ecx + 4 ]
;int i = 0;
xor edx , edx
;int arrayLength = localRefToArray.Length;
mov edi , dword ptr [ ecx + 4 ]
;if (arrayLength == 0) goto exit;
test edi , edi
jle exit
;int t = array[i];
loop :
mov eax , dword ptr [ ecx + edx * 4 + 8 ]
;sum+=i;
add esi , eax
;i++;
inc edx
;if (i < arrayLength) goto loop
cmp edi , edx
jg loop
;return sum;
exit :
mov eax , esi

ForEachWithLengthWithoutLocalVariable()

;int sum = 0;
xor esi , esi
;int[] localRefToArray = this.array;
mov ecx , dword ptr [ ecx + 4 ]
;int i = 0;
xor edx , edx
;int arrayLength = localRefToArray.Length;
mov edi , dword ptr [ ecx + 4 ]
;if (arrayLength == 0) goto exit
test edi , edi
jle exit
;int t = array[i];
loop :
mov eax , dword ptr [ ecx + edx * 4 + 8 ]
;sum+=i;
add esi , eax
;sum+=localRefToArray.Length;
add esi , dword ptr [ ecx + 4 ]
;i++;
inc edx
;if (i < arrayLength) goto loop
cmp edi , edx
jg loop
;return sum;
exit :
mov eax , esi

ForEachWithLengthWithLocalVariable()

;int sum = 0;
xor esi , esi
;int[] localRefToArray = this.array;
mov edx , dword ptr [ ecx + 4 ]
;int length = localRefToArray.Length;
mov ebx , dword ptr [ edx + 4 ]
;int i = 0;
xor ecx , ecx
;int arrayLength = localRefToArray.Length;
mov edi , dword ptr [ edx + 4 ]
;if (arrayLength == 0) goto exit;
test edi , edi
jle exit
;int t = array[i];
loop :
mov eax , dword ptr [ edx + ecx * 4 + 8 ]
;sum+=i;
add esi , eax
;sum+=length ;
add esi , ebx
;i++;
inc ecx
;if (i < arrayLength) goto loop
cmp edi , ecx
jg loop
;return sum;
exit :
mov eax , esi

Первое что бросается в глаза это то, что получилось меньше ассемблерных инструкций, по сравнению с циклом for (например для простого суммирования элементов вышло в foreach 12 инструкций, в for 15).

Скриншот сравнения For и ForEach

В самом деле, если написать бенчмарк for vs foreach на 1 000 000 элементов массива, то получится такая картина для

sum+=array[i];
Method ItemsCount Mean Error StdDev Median Ratio RatioSD
ForEach 1000000 1.401 ms 0.2691 ms 0.7935 ms 1.694 ms 1.00 0.00
For 1000000 1.586 ms 0.3204 ms 0.9447 ms 1.740 ms 1.23 0.65
sum+=array[i] + array.Length;
Method ItemsCount Mean Error StdDev Median Ratio RatioSD
ForEach 1000000 1.703 ms 0.3010 ms 0.8874 ms 1.726 ms 1.00 0.00
For 1000000 1.715 ms 0.2859 ms 0.8430 ms 1.956 ms 1.13 0.56

ForEach для массивов отрабатывает быстрее чем For. Почему так происходит? Чтобы это понять нужно сравнивать код после JIT.

Скриншот сравнения всех трёх вариантов foreach

Посмотрим на ForEachWithoutLength. В нём длина массива запрашивается только один раз и не происходит никаких проверок на выход элементов за пределы массива. Так происходит потому что цикл ForEach во-первых запрещает изменение коллекции внутри цикла, а во-вторых точно не будет выходить за пределы коллекции. Из-за этого JIT может себе позволить вообще убрать проверки на выход за пределы массива.

Теперь посмотрим внимательно на метод ForEachWithLengthWithoutLocalVariable. В его коде есть только один странный момент в том, что sum+=length происходит не с сохранённой ранее локальной переменной arrayLength, а с новой, которую программа спрашивает каждый раз из памяти. Получается, что обращений к памяти за длиной массива будет N + 1, где N — длина массива.

Осталось рассмотреть метод ForEachWithLengthWithLocalVariable. Его код ничем не отличается от ForEachWithLengthWithoutLocalVariable, кроме работы с длинной массива. Компилятор опять сгенерировал локальную переменную arrayLength, с помощью которой проверяет что массив не пустой, но при этом компилятор честно сохранил нашу явную локальную переменную length и сложение в теле цикла происходит уже с ней. Получается, что этот метод всего дважды обращается к памяти для определения длины массива. Эту разницу в количестве обращений к памяти в реальных приложениях очень сложно заметить.

Ассемблерный код рассмотренных методов получился такой простой потому что сами методы простые. Будь в методе больше параметров, там была бы уже работа со стеком, переменные хранились бы не только в регистрах и возможно было бы больше проверок, но основная логика осталась бы такая же: введение локальной переменной с длиной массива может иметь смысл только для повышения читабельности кода. Кроме того, оказалось, что Foreach по массиву часто выполняется быстрее чем For.

Когда стоит сохранять длину массива в локальную переменную в C#

Читая Хабр, я наткнулся на статью «Стоит ли сохранять длину массива в локальную переменную в C#?» (которая была в разделе «лучшее»). Мне кажется глупый вопрос, не совсем корректные измерения (почему нет измерений для вложенных циклов?) и странный вывод.

Длину массива в С# стоит сохранять в отдельную переменную в случае когда у нас несколько вложенных циклов, ниже пример.

Вот простой тестовый код без сохранения длины массива в переменную:

Random rnd1 = new Random(DateTime.UtcNow.Millisecond); int[,] arr1 = new int[Int16.MaxValue, Byte.MaxValue]; for (int i = 0; i < arr1.GetLength(0); i++) < for (int j = 0; j < arr1.GetLength(1); j++) < arr1[i, j] = rnd1.Next(Int32.MinValue, Int32.MaxValue); >>

Вот тот же код c сохранением длины массива в переменную:

Random rnd1 = new Random(DateTime.UtcNow.Millisecond); int[,] arr1 = new int[Int16.MaxValue, Byte.MaxValue]; int len1 = arr1.GetLength(0), len2 = arr1.GetLength(1); for (int i = 0; i < len1; i++) < for (int j = 0; j < len2; j++) < arr1[i, j] = rnd1.Next(Int32.MinValue, Int32.MaxValue); >>

Код с сохранением длины массива в переменную (второй вариант) выполняется примерно на 15% быстрее.

Подобный ответ можно найти в более-менее толстых книжках по C# или .Net, но при этом умный человек постит это на Хабре и никто в комментариях не указал ему что длину массива в С# сохраняют в переменную обычно для вложенных циклов и там это действительно имеет смысл.

Я просто хотел оставить там комментарий, но без регистрации не смог, а после регистрации оказалось — что я и после регистрации не могу оставить там комментарий (так как прошло более 10 дней с момента публикации). Может кто-то заметит эту заметку и скопирует ее туда в виде комментария или вроде того.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *