Массивы java задания. Как загрузить элементы в массив? Один размерный массив
Начнем, пожалуй, последнюю не очень приятную и интересную, но очень важную и полезную тему в теории языка Java — массивы. Далее будет более интересный и увлекательный материал, который можно будет использовать для более практичных задач. Но, чтобы начать интересную часть явы нужно выучить неинтересную)) которая и является основой языка и без которой невозможно дальше учить программирование.
Все предыдущие темы, который мы рассматривали: , являются основами программирования. С их изучения Вы будете начинать любой другой язык программирования. Массивы тоже относятся к такой теме. На чем бы Вы не решили начать программировать, Вы вряд ли сможете обойтись без массивов. Поэтому, я советую очень хорошо освоить данный и прошлый материал, если Вы хотите преуспеть в программировании.
Теперь перейдем к массивам.
Массив — это структура данных, которая предназначена для хранения однотипных данных.
Допустим, Вам нужно создать 5 целочисленных переменных и задать им некоторое значение. Как Вы это будете делать? Не зная массивов, Вы скорее всего начнете писать вот так: int a = 2, b = 3, c = 5, d = 21, e = 2;
Имея в арсенале такой тип данных как массивы, Вы можете писать так: int a = {2, 3, 5, 21, 2};
Это очень удобно, когда имеет место обработка этих данных. Например, теперь Вам нужно к каждой переменной добавить 3. Если бы Вы использовали первый способ объявления, то такая операция заняла бы у Вас достаточно много времени. Тогда как имея в арсенале массивы и , мы можем обрабатывать огромное количество данных не прибегая к монотонному коду.
Перед тем как использовать, массив нужно:
- Объявить;
- Создать;
- Инициализировать.
Запомните это порядок действий и никогда не нарушайте его.
Объявление массивов:
char s;
String p;
или
char s;
String p;
Создание массивов:
s = new char;
p = new String;
В квадратных скобках указано количество элементов массива. Это количество нельзя
будет поменять потом.
Инициализация массивов:
после создания – поэлементно: int a = {1,2,3,4,5};
при объявлении/создании – массив целиком: int b = new int {2, 4 ,6};.
Если массив явно не проинициализирован, то после его создания все
элементы равны:
0 – в числовых массивах
false – в boolean-массивах
null – в массивах объектов
Границы массивов:
У всех массивов есть поле length – длина массива (в элементах)
Первый элемент всегда имеет индекс 0 (не путать со значением).
Последний элемент всегда имеет индекс length-1.
После такого количества теории, думаю, нужно немного практики:
public class ArraysInJava {
int intArray; //объявление массива
intArray = new int [ 10] ; //инициализация массива
intArray[ 0] = 1 ; //первому элементу массива даем значение 1
intArray[ 1] = 2 ; //второму значение 2
intArray[ 6] = 7 ; //остальные значения массива, которым мы
//не задали значений будут по умолчанию 0
//соответствует значению в квадратных скобках при инициалазации.
for (int i = 0 ; i < intArray.length ; i++ ) {
for (int i = 0 ; i < intArray.length ; i++ ) {
intArray[ i] = 45 ; //каждый элемент массива может быть изменен
Результат выполнения кода:
Мы рассмотрели одномерные массивы в Java. Сейчас пришла очередь двумерных.
Как Вы уже могли догадаться двумерный массив — это массив массивов. Не нужно пугаться. Все намного проще, чем кажется.
int twoDim = new int — вот так можно объявить двумерный массив с размерностью 4 на 4. Будет 4 элемента по вертикали и 4 по горизонтали. Задать значение таком массиву так же просто как и одномерному: twoDim = 3. Эта запись будет означать, что мы задали нашему элементу массива, которых находится во втором ряде (индекс начинается с 0) и 3 столбике. На рисунке это будет вот так: 
Кстати, вот пример кода:
Многомерные массивы могут иметь сколько угодно размерностей. Объявление, инициализация и работа с ними идентична одномерным массивам. Если Вы научитесь работать с одномерными и двумерными массивами, то с трехмерными и выше проблем не будет.
Еще пример. Точнее задание. Я хочу, чтобы Вы подумали и написали приложение, которое выводит числа в таком порядке: 
Подсказка: System.out.println(); — печатает с новой строки, тогда как: System.out.print() — печатает в той самой строке.
Прежде, чем смотреть на решение, попробуйте написать его сами. Это очень закрепляет пройденный материал.
Для тех, кто не осилил, предлагаю решение. Не огорчайтесь. Программирование требует времени и терпения.
public class FormatMatrixPrint {
int size = 5 ;
Инициализаторы массивов и безымянные массивы
В языке Java есть средство для одновременного создания массива и его инициализации. Вот пример такой синтаксической конструкции: int smallPrimes = { 2 , 3 , 5 , 7 , 11 , 13 } ; Отметим, что в этом случае не нужно применять оператор new . Кроме того, можно даже инициализировать безымянный массив: new int { 16 , 19 , 23 , 29 , 31 , 37 } Это выражение выделяет память для нового массива и заполняет его числами, указанными в фигурных скобках. При этом подсчитывается их количество и, соответственно, определяется размер массива. Эту синтаксическую конструкцию удобно применять для повторной инициализации массива без образования новой переменной. Например, выражение smallPrimes = new int { 17 , 19 , 23 , 29 , 31 , 37 } ; представляет собой укороченную запись выражения int anonymous = { 17 , 19 , 23 , 29 , 31 , 37 } ; smallPrimes = anonymous; Можно создать массив нулевого размера. Такой массив может оказаться полезным при написании метода, вычисляющего некий массив, который оказывается пустым. Массив нулевой длины объявляется следующим образом: new тип Элементов Заметим, что такой массив не эквивалентен объекту null .Копирование массивов arrays
Один массив можно скопировать в другой, но при этом обе переменные будут ссылаться на один и тот же массив. int luckyNumbers = smallPrimes; luckyNumbers[ 5 ] = 12 ; //Теперь элемент smallPrimesтакже равен 12 Результат показан на рис. 3.1. Если необходимо скопировать все элементы одного массива в другой, следует использовать метод arraycopy из класса System . Его вызов выглядит следующим образом: System. arraycopy (from, fromlndex, to, tolndex, count) ; Массив to должен иметь достаточный размер, чтобы в нем поместились все копируемые элементы.
Рис.3.1. Копирование массива
Например, показанные ниже операторы, результаты работы которых изображены на рис. 3.2, создают два массива, а затем копируют последние четыре элемента первого массива во второй. Копирование начинается со второй позиции в исходном массиве, а копируемые элементы помещаются в целевой массив, начиная с третьей позиции.
int
smallPrimes =
{
2
,
3
,
5
,
7
,
11
,
13
}
;
int
luckyNumbers =
{
1001
,
1002
,
1003
,
1004
,
1005
,
1006
,
1007
}
;
System.
аrrаусору(smallPrimes,
2
,
luckyNumbers,
3
,
4
)
;
for
(int
i =
0
;
i <
luckyNumbers.
length;
i++
)
System.
out.
println
(i +
": "
+
luckyNumbers[
i]
)
;
Выполнение этих операторов приводит к следующему результату.
0
:
1001
1
:
1002
2
:
1003
3
:
5
4
:
7
5
:
11
6
:
13
Рис. 3.2. Копирование элементов массива
Массив в языке Java значительно отличается от массива в языке C++. Однако он практически совпадает с указателем на динамический массив. Это значит, что оператор
int
a =
new
int
[
100
]
;
//Java
эквивалентен оператору
int
*
=
new
int
[
100
]
;
//C++,
а не
int
a[
100
]
;
//C++
В языке Java оператор пo умолчанию проверяет диапазон изменения индексов. Кроме того, в языке Java нет арифметики указателей - нельзя увеличить указатель а, чтобы обратиться к следующему элементу массива.
Ссылка на перво
Массив (англ. Array) это объект, хранящий в себе фиксированное количество значений одного типа. Другими словами, массив — это нумерованный набор переменных. Переменная в массиве называется элементом массива , а ее позиция в массиве задается индексом . Например, нам нужно хранить 50 различных имен, согласитесь, неудобно для каждого имени создавать отдельную переменную, поэтому мы будем использовать массив. Нумерация элементов массива начинается с 0, а длинна массива устанавливается в момент его создания и фиксируется.
Для наглядности картинка, взятая мною с The Java Tutorial .
Для того чтобы создать массив нужно его объявить, зарезервировать для него память и инициализировать.
Объявление массива в Java
При создании массива в Java первым делом его нужно объявить. Это можно сделать следующим образом:
Int myFirstArray;
Можно также объявить массив так:
Int mySecondArray;
Однако, это не приветствуется соглашением по оформлению кода в Java, поскольку скобки обозначают то, что мы имеем дело с массивом и логичнее, когда они находятся рядом с обозначением типа.
Исходя из данного примера, мы объявили 2 массива с именами myFirstArray и mySecondArray . Оба массива будут содержать элементы типа int .
Подобным образом можно объявить массив любого типа:
Byte anArrayOfBytes; short anArrayOfShorts; long anArrayOfLongs; float anArrayOfFloats; double anArrayOfDoubles; boolean anArrayOfBooleans; char anArrayOfChars; String anArrayOfStrings; ...
Тип массива задается следующим образом type, где type это тип данных содержащихся в нем элементов. Скобки являются специальным обозначением того, что переменные содержатся в массиве. Имя массива может быль любым, однако, оно должно соответствовать .
Массивы можно создавать не только из переменных базовых типов, но и из произвольных объектов.
При объявлении массива в языке Java не указывается его размер и не резервируется память для него. Происходит лишь создание ссылки на массив.
Резервация памяти для массива и его инициализация.
Int myFirstArray; myFirstArray = new int;
В нашем примере мы создали массив из 15 элементов типа int и присвоили его ранее объявленной переменной myFirstArray .
Объявлять имя массива и резервировать для него память также можно на одной строке.
Int myArray = new int;
При создании массива с помощью ключевого слова new , все элементы массива автоматически инициализированы нулевыми значениями. Для того, чтобы присвоить элементам массива свои начальные значения, необходимо провести его инициализацию . Инициализацию можно проводить как поэлементно
MyFirstArray = 10; // инициализация первого элемента myFirstArray = 20; // инициализация второго элемента myFirstArray = 30; // и т.д.
так и в цикле, с помощью индекса проходя все элементы массива и присваивая им значения.
For(int i = 0; i < 15; i++){ myFirstArray[i] = 10; }
Как видно из предыдущих примеров, для того, чтобы обратиться к элементу массива, нужно указать его имя и, затем, в квадратных скобках — индекс элемента. Элемент массива с конкретным индексом ведёт себя также, как и переменная.
Рассмотрим создание и инициализацию массива на следующем примере. В нем мы создаем массив, содержащий цифры 0-9 и выводим значения на консоль.
//создание и инициализация массива int numberArray = new int; for(int i = 0; i < 10; i++){ numberArray[i] = i; } //вывод значений на консоль for(int i = 0; i < 10; i++){ System.out.println((i+1) + "-й элемент массива = " + numberArray[i]); }
Упрощенная форма записи
Для создания и инициализации массива можно также использовать упрощенную запись. Она не содержит слово new , а в скобках перечисляются начальные значения массива.
Int myColor = {255, 255, 0};
Здесь длина массива определяется числом значений, расположенных между скобками и разделенных запятыми. Такая запись больше подходит для создания небольших массивов
Определение размера массива
Размер массива не всегда очевиден, поэтому для того, чтобы его узнать следует использовать свойство length, которое возвращает длину массива.
MyColor.length;
Данный код поможет нам узнать, что длина массива myColor равна 3.
Пример: Задано 4 числа, необходимо найти минимальное
Int numbers = {-9, 6, 0, -59}; int min = numbers; for(int i = 0; i < numbers.length; i++){ if(min>numbers[i]) min = numbers[i]; } System.out.println(min);
Упражнения на тему одномерные массивы в Java:
- Создайте массив, содержащий 10 первых нечетных чисел. Выведете элементы массива на консоль в одну строку, разделяя запятой.
- Дан массив размерности N, найти наименьший элемент массива и вывести на консоль (если наименьших элементов несколько — вывести их все).
- В массиве из задания 2. найти наибольший элемент.
- Поменять наибольший и наименьший элементы массива местами. Пример: дан массив {4, -5, 0, 6, 8}. После замены будет выглядеть {4, 8, 0, 6, -5}.
- Найти среднее арифметическое всех элементов массива.
19 ответов
Вы можете использовать объявление массива или литерал массива (но только когда вы сразу объявляете и влияете на переменную, литералы массива не могут использоваться для переназначения массива).
Для примитивных типов:
Int myIntArray = new int; int myIntArray = {1,2,3}; int myIntArray = new int{1,2,3};
Для классов, например String , это то же самое:
String myStringArray = new String; String myStringArray = {"a","b","c"}; String myStringArray = new String{"a","b","c"};
Третий способ инициализации полезен, когда вы сначала объявляете массив, а затем инициализируете его. Приведение необходимо здесь.
String myStringArray; myStringArray = new String{"a","b","c"};
Существует два типа массива.
Один размерный массив
Синтаксис значений по умолчанию:
Int num = new int;
Или (менее предпочтительный)
Int num = new int;
Синтаксис с указанными значениями (инициализация переменной/поля):
Int num = {1,2,3,4,5};
Или (менее предпочтительный)
Int num = {1, 2, 3, 4, 5};
Примечание. Для удобства int num предпочтительнее, потому что в нем четко сказано, что вы говорите здесь о массиве. Иначе никакой разницы. Совсем нет.
Многомерный массив
Декларация
int num = new int;Int num = new int;
Int num = new int;
Инициализация
num=1; num=2; num=1; num=2; num=1; num=2; num=1; num=2; num=1; num=2;Int num={ {1,2}, {1,2}, {1,2}, {1,2}, {1,2} };
Ragged Array (или непрямоугольный массив)
int num = new int; num = new int; num = new int; num = new int; num = new int;Итак, здесь мы явно определяем столбцы.
Другой способ:
Int num={ {1}, {1,2}, {1,2,3,4,5}, {1,2}, {1,2,3} };
Для доступа:
for (int i=0; i<(num.length); i++) { for (int j=0;jFor (int a: num) { for (int i: a) { System.out.println(i); } }
Type variableName = new Type; Type variableName = {comma-delimited values}; Type variableName = new Type; Type variableName = {comma-delimited values};
также действителен, но я предпочитаю скобки после типа, потому что легче видеть, что тип переменной на самом деле является массивом.
Ниже показано объявление массива, но массив не инициализирован:
Int myIntArray = new int;
Ниже показано объявление, а также инициализация массива:
Int myIntArray = {1,2,3};
Теперь следующее также показывает объявление, а также инициализацию массива:
Int myIntArray = new int{1,2,3};
Но этот третий показывает свойство анонимного создания массива-объекта, которое указывается ссылочной переменной "myIntArray", поэтому, если мы пишем только "new int {1,2,3};" то это может быть анонимный массив-объект.
Если мы просто напишем:
Int myIntArray;
это не объявление массива, но следующий оператор делает следующее выражение завершенным:
MyIntArray=new int;
Я считаю полезным, если вы понимаете каждую часть:
Type name = new Type;
Type - это тип переменной, называемой именем ("имя" называется идентификатором). Литеральный "Тип" - это базовый тип, а скобки означают, что это тип массива этой базы. Типы массивов в свою очередь являются собственными, что позволяет создавать многомерные массивы типа Type (тип массива Type ). Ключевое слово new говорит о распределении памяти для нового массива. Число между скобкой говорит о том, насколько большой будет новый массив и сколько памяти будет выделено. Например, если Java знает, что базовый тип Type занимает 32 байта, и вам нужен массив размером 5, ему необходимо внутренне выделить 32 * 5 = 160 байт.
Вы также можете создавать массивы с уже имеющимися значениями, такими как
Int name = {1, 2, 3, 4, 5};
который не только создает пустое пространство, но и заполняет его этими значениями. Java может сказать, что примитивы являются целыми числами и что их 5, поэтому размер массива может быть определен неявно.
Кроме того, если вы хотите что-то более динамичное, есть интерфейс List. Это не будет работать, но более гибко:
List
Существует два основных способа создания массива:
Этот, для пустого массива:
Int array = new int[n]; // "n" being the number of spaces to allocate in the array
И этот, для инициализированного массива:
Int array = {1,2,3,4 ...};
Вы также можете создавать многомерные массивы, например:
Int array2d = new int[x][y]; // "x" and "y" specify the dimensions int array2d = { {1,2,3 ...}, {4,5,6 ...} ...};
Возьмите примитивный тип int , например. Существует несколько способов объявления и массив int:
Int i = new int; int i = new int {value1, value2, value3, etc}; int i = {value1, value2, value3, etc};
где во всех этих случаях вы можете использовать int i вместо int i .
С отражением вы можете использовать (Type) Array.newInstance(Type.class, capacity);
Обратите внимание, что в параметрах метода... отображается variable arguments . По сути, любое количество параметров в порядке. Это проще объяснить с помощью кода:
Public static void varargs(int fixed1, String fixed2, int... varargs) {...} ... varargs(0, "", 100); // fixed1 = 0, fixed2 = "", varargs = {100} varargs(0, "", 100, 200); // fixed1 = 0, fixed2 = "", varargs = {100, 200};
Внутри метода varargs рассматривается как нормальный int . Type... может использоваться только в параметрах метода, поэтому int... i = new int {} не будет компилироваться.
Обратите внимание, что при передаче int методу (или любому другому Type) вы не можете использовать третий способ. В заявлении int i = *{a, b, c, d, etc}* компилятор предполагает, что {...} означает int . Но это потому, что вы объявляете переменную. При передаче массива методу декларация должна быть либо new Type , либо new Type {...} .
Многомерные массивы
Многомерные массивы гораздо сложнее справиться. По существу, 2D-массив представляет собой массив массивов. int означает массив int s. Ключ состоит в том, что если int объявлен как int[x][y] , максимальный индекс равен i . По существу, прямоугольник int равен:
Объявление массива ссылок на объекты:
Class Animal {} class Horse extends Animal { public static void main(String args) { /* * Array of Animal can hold Animal and Horse (all subtypes of Animal allowed) */ Animal a1 = new Animal; a1 = new Animal(); a1 = new Horse(); /* * Array of Animal can hold Animal and Horse and all subtype of Horse */ Animal a2 = new Horse; a2 = new Animal(); a2 = new Horse(); /* * Array of Horse can hold only Horse and its subtype (if any) and not allowed supertype of Horse nor other subtype of Animal. */ Horse h1 = new Horse; h1 = new Animal(); // Not allowed h1 = new Horse(); /* * This can not be declared. */ Horse h2 = new Animal; // Not allowed } }
Массив - это последовательный список элементов
Int item = value; int one_dimensional_array = { value, value, value, .., value }; int two_dimensional_array = { { value, value, value, .. value }, { value, value, value, .. value }, .. .. .. .. { value, value, value, .. value } };
Если это объект, то это же понятие
Object item = new Object(); Object one_dimensional_array = { new Object(), new Object(), .. new Object() }; Object two_dimensional_array = { { new Object(), new Object(), .. new Object() }, { new Object(), new Object(), .. new Object() }, .. .. .. { new Object(), new Object(), .. new Object() } };
В случае объектов вам нужно либо назначить его null для инициализации с помощью new Type(..) , классы, такие как String и Integer , являются особыми случаями, которые будут обрабатываться как следующие
String a = { "hello", "world" }; // is equivalent to String a = { new String({"h","e","l","l","o"}), new String({"w","o","r","l","d"}) }; Integer b = { 1234, 5678 }; // is equivalent to Integer b = { new Integer(1234), new Integer(5678) };
В общем случае вы можете создавать массивы, которые M мерные
Int .. array = // ^ M times brackets {{..{ // ^ M times { bracket // this is array.. // ^ M times }}..} // ^ M times } bracket ;
Стоит отметить, что создание размерного массива M является дорогостоящим с точки зрения Space. Поскольку при создании массива M с N во всех измерениях общий размер массива больше, чем N^M , так как каждый массив имеет ссылку, а в M-размерности есть (M -1) -мерный массив ссылок. Общий размер выглядит следующим образом
- Tutorial
Думаю, мало кто из готовящихся к своему первому интервью, при приеме на первую работу в должности (pre)junior программиста, ответит на этот вопрос отрицательно. Или хотя бы усомнится в положительном ответе. Конечно, такая простая структура данных с прямым доступом по индексу - никаких подвохов! Нет, в некоторых языках типа JavaScript или PHP массивы, конечно, реализованы очень интересно и по сути являются много большим чем просто массив. Но речь не об этом, а о «традиционной» реализации массивов в виде «сплошного участка памяти». В этом случае на основании индексов и размера одного элемента просто вычисляется адрес и осуществляется доступ к соответствующему значению. Что тут сложного?
Давайте разберемся. Например, на Java. Просим ничего не подозревающего претендента создать массив целых чисел n
x n
. Человек уверено пишет что-то в духе:
int g = new int[n][n];
Отлично. Теперь просим инициализировать элементы массива чем-нибудь. Хоть единицами, хоть суммой индексов. Получаем:
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
g[i][j] = i + j;
}
}
Даже чаще пишут
for(int i = 0; i < g.length; i++) {
for(int j = 0; j < g[i].length; j++) {
g[i][j] = i + j;
}
}
что тоже повод для беседы, но сейчас речь о другом. Мы ведь пытаемся выяснить, что человек знает и посмотреть, как он думает. По этому обращаем его внимание на тот факт, что значения расположены симметрично и просим сэкономить на итерациях циклов. Конечно, зачем пробегать все значения индексов, когда можно пройти только нижний треугольник? Испытуемый обычно легко соглашается и мудро выделяя главную диагональ старательно пишет что-то в духе:
for(int i = 0; i < n; i++) {
g[i][i] = 2* i;
for(int j = 0; j < i; j++) {
g[j][i] = g[i][j] = i + j;
}
}
Вместо g[i][i] = 2* i;
часто пишут g[i][i] = i + i;
или g[i][i] = i << 1;
и это тоже повод поговорить. Но мы идем дальше и задаем ключевой вопрос: На сколько быстрее станет работать программа?
. Обычные рассуждения такие: почти в 2 раза меньше вычислений индексов; почти в 2 раза меньше вычислений значений (суммирование); столько же присваиваний. Значит быстрее процентов на 30. Если у человека за плечами хорошая математическая школа, то можно даже увидеть точное количество сэкономленных операций и более аргументированную оценку эффективности оптимизации.
Теперь самое время для главного удара. Запускаем оба варианта кода на каком-нибудь достаточно большом значении n
(порядка нескольких тысяч), например, так .
Код с контролем времени
class A {
public static void main(String args) {
int n = 8000;
int g = new int[n][n];
long st, en;
// one
st = System.nanoTime();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
g[i][j] = i + j;
}
}
en = System.nanoTime();
System.out.println("\nOne time " + (en - st)/1000000.d + " msc");
// two
st = System.nanoTime();
for(int i = 0; i < n; i++) {
g[i][i] = i + i;
for(int j = 0; j < i; j++) {
g[j][i] = g[i][j] = i + j;
}
}
en = System.nanoTime();
System.out.println("\nTwo time " + (en - st)/1000000.d + " msc");
}
}
Что же мы видим? Оптимизированный вариант работает в 10-100 раз медленнее! Теперь самое время понаблюдать за реакцией претендента на должность. Какая будет реакция на необычную (точнее обычную в практике разработчика) стрессовую ситуацию. Если на лице подзащитного изобразился азарт и он стал жать на кнопочки временно забыв о Вашем существовании, то это хороший признак. До определенной степени. Вы ведь не хотите взять на работу исследователя, которому плевать на результат проекта? Тогда не задавайте ему вопрос «Почему?». Попросите переделать второй вариант так, чтобы он действительно работал быстрее первого.
Теперь можно смело заниматься некоторое время своими делами. Через пол часа у Вас будет достаточно материала, для того, чтобы оценить основные личностные и профессиональные качества претендента.
Кстати, когда я коротко описал эту задачку на своем рабочем сайте, то наиболее популярный комментарий был «Вот такая эта Ваша Java кривая». Специально для них выкладываю код на Великом и Свободном. А счастливые обладатели Free Pascal под Windows могут заглянуть
под спойлер
program Time;
uses
Windows;
var
start, finish, res: int64;
n, i, j: Integer;
g: Array of Array of Integer;
begin
n:= 10000;
SetLength(g, n, n);
QueryPerformanceFrequency(res);
QueryPerformanceCounter(start);
for i:=1 to n-1 do
for j:=1 to n-1 do
g := i + j;
QueryPerformanceCounter(finish);
writeln("Time by rows:", (finish - start) / res, " sec");
QueryPerformanceCounter(start);
for i:=1 to n-1 do
for j:=1 to n-1 do
g := i + j;
QueryPerformanceCounter(finish);
writeln("Time by cols:", (finish - start) / res, " sec");
end.
В приведенном коде на Паскале я убрал «запутывающие» моменты и оставил только суть проблемы. Если это можно назвать проблемой.
Какие мы в итоге получаем вопросы к подзащитному?
1. Почему стало работать медленнее? И поподробнее…
2. Как сделать инициализацию быстрее?
Если есть необходимость копнуть глубже именно в реализацию Java, то просим соискателя понаблюдать за временем выполнения для небольших значений n
. Например, на ideone.com для n=117 «оптимизированный» вариант работает вдвое медленнее. Но для следующего значения n=118 он оказывается уже в 100 (сто) раз быстрее не оптимизированного! Предложите поэкспериментировать на локальной машине. Пусть поиграет с настройками.
Кстати, а всем понятно, что происходит?
Несколько слов в оправдание
Хочу сказать несколько слов в оправдание такого способа собеседования при найме. Да, я не проверяю знание синтаксиса языка и владение структурами данных. Возможно, при цивилизованном рынке труда это все работает. Но в наших условиях тотальной нехватки квалифицированных кадров, приходится оценивать скорее перспективную адекватность претендента той работе с которой он столкнется. Т.е. способность научиться, прорваться, разобраться, сделать.
По духу это похоже на «собеседованию» при наборе легионеров в древнем Риме. Будущего вояку сильно пугали и смотрели краснеет он или бледнеет. Если бледнеет, то в стрессовой ситуации у претендента кровь отливает от головы и он склонен к пассивной реакции. Например, упасть в обморок. Если же соискатель краснел, то кровь у него к голове приливает. Т.е. он склонен к активным действиям, бросаться в драку. Такой считался годным.
Ну и последнее. Почему я рассказал об этой задаче всем, а не продолжаю использовать её на собеседованиях? Просто, эту задачу уже «выучили» потенциальные соискатели и приходится использовать другие.
Собственно на этот эффект я обратил внимание именно в связи с реальной задачей обработки изображений. Ситуация была несколько запутанная и я не сразу понял почему у меня так просел fps после рефакторинга. А вообще таких чуднЫх моментов наверное много накопилось у каждого.
Пока лидирует версия, что «виноват» кэш процессора. Т.е. последовательный доступ в первом варианте работает в пределах хэша, который обновляется при переходе за определенную границу. При доступе по столбцам хэш вынужден постоянно обновляться и это занимает много времени. Давайте проверим эту версию в самом чистом виде. Заведем массив и сравним, что быстрее - обработать все элементы подряд или столько же раз обработать элементы массива со случайным номером? Вот эта программа - ideone.com/tMaR2S . Для 100000 элементов массива случайный доступ обычно оказывается заметно быстрее. Что же это означает?
Тут мне совершенно справедливо указали (Big_Lebowski), что перестановка циклов меняет результаты в пользу последовательного варианта. Пришлось для чистоты эксперимента поставить цикл для разогрева. Заодно сделал несколько повторов, чтобы вывести среднее время работы как советовал leventov. Получилось так ideone.com/yN1H4g . Т.е. случайный доступ к элементам большого массива на ~10% медленнее чем последовательный. Возможно и в правду какую-то роль может сыграть кэш. Однако, в исходной ситуации производительность проседала в разы. Значит есть еще что-то.
Постепенно в лидеры выходит версия про дополнительные действия при переходе от одной строки массива к другой. И это правильно. Осталось разобраться, что же именно там происходит.
Теги: Добавить метки
Загрузка...
