Почему школы учат массивы по списку? [закрыто]

36

Большинство заданий в моей школе для начальных классов программирования требовало от меня использования массивов. Сейчас я работаю полный рабочий день, и я никогда не использовал массив для любого проекта, над которым я работал. Даже в существующих проектах я нигде не видел использования массивов. На мой взгляд, список проще в использовании и является стандартным. Почему профессора говорят студентам использовать массивы в своих заданиях? Это просто, чтобы студенты понимали основы?

Поскольку большинство университетов преподают Java, этот вопрос специфичен для Java.

Вой Хагрида
источник
7
Массивы являются более фундаментальными.
user253751
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Мировой инженер

Ответы:

120

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

Списки не являются "стандартом". Существует множество проблемных областей, для которых массивы идеально подходят.

Роберт Харви
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Мировой инженер
48

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

По той же самой причине мой первый класс программирования в колледже был на C, а остальные классы были на C ++, Java и других языках. Дело не в том, что C как-то лучше или проще, а в том, что C (и Array) ничего не скрывают от вас.

Ixrec
источник
7
Со списком легче работать в реальном коде, но массив легче (полностью) понять, и его важнее понять, поскольку они фундаментальны и универсальны, в то время как (Java) List - нет. По крайней мере, это мое мнение.
Иксрек
21
Назначение, в котором вы храните материал в массиве и получаете к нему доступ позже, является назначением структуры данных . Вы просто, возможно, не поняли это. Вы должны спросить себя: что делает лучше инженеров, понимает основные вычислительные модели или изучает стандартную библиотеку языка? Общее мнение (и я согласен, fwiw) состоит в том, что вы не поймете много содержимого библиотеки без предварительного понимания основ вычислений.
Кент А.
12
LinkedList, ArrayList, OrderedList и т. Д. Какой список вы должны изучить в первую очередь? Как бы вы оценили то, что они для вас делают, если не понимаете, почему они существуют?
Кент А.
10
+1 к @KentAnderson. Школы должны создавать инженеров, которые понимают структуры данных на низком уровне; в идеале, создание инженеров, которые могут легко реализовать базовые структуры в C. Любая другая программа - это просто JavaSchool.
Кристиан Уиллман
2
«Они, вероятно, хотели начать со структуры данных, которая наиболее точно отражает работу компьютера». Итак, как насчет компьютеров со структурой памяти со списком или объектами? «Дело не в том, что C как-то лучше или проще, а в том, что C (и Array) ничего не скрывают от вас». - Если на вашем компьютере нет указателей, таких как AS / 400, где C по сути работает в виртуальной машине и скрывает почти все для вас.
Йорг Миттаг
21

Ответы выше велики, но я имею в виду другое. main()Метод Java означает, что учащиеся сталкиваются с базовыми массивами очень рано, часто уже в первый день занятий. Зачем?

public static void main(String[] args)

Это первое, с чем вам придется иметь дело, чтобы написать Hello World и не только. (Я видел, что в некоторых курсах сначала используются обучающие IDE, такие как BlueJ, которые позволяют указывать и нажимать для запуска произвольных методов, но мы отложим их в сторону ...) Хотя, возможно, стоит потрудиться над некоторыми из Эти ключевые слова на какое-то время рано или поздно большинству учителей захочется их объяснить. Действительно, классический тестовый вопрос для начинающих состоит в том, чтобы попросить студентов объяснить значение каждого ключевого слова в базовой программе Hello World. И что мы находим как часть сигнатуры нашего основного метода? Массив (причина этого отчасти историческая. ArrayList не существовал в Java 1.0). Массивы являются частью этого базового набора знаний. Список нет.

Тем не менее, это не редкость, когда классы вводят ArrayList чуть позже в курс, особенно после того, как объекты и их использование были рассмотрены. Даже учебная программа AP Computer Science для Java включает в себя ArrayList (я знаю, что раньше, и Google, кажется, указывает, что он все еще делает), хотя он игнорирует тот факт, что ArrayList реализует List и остальную часть Collections Framework.

Наконец, мой опыт показывает, что университетские CS-программы используют Java как средство для изучения CS и концепций программирования, а не для обучения студентов тому, как стать хорошими Java-разработчиками. Некоторые программы могут быть более сфокусированы на привлечении профессиональных разработчиков, в то время как другие больше фокусируются на теории, но в любом случае, есть много, чтобы узнать о том, как использовать Java в реальной профессиональной работе, которая не будет преподаваться в большинстве учебных программ колледжа. Это варьируется от шаблонов проектирования и методов, подобных тем, которые используются в Effective Java, до таких сред, как Spring, Hibernate или JUnit, или даже от более распространенных вещей, таких как JSP или JDBC. Учитывая эту философию, выделение массивов над более часто используемым ArrayList имеет немного больше смысла.

Зак Липтон
источник
3
@ Дедупликатор уверен. Это просто не имело отношения к моей точке зрения о массивах, поэтому я опустил это. Я также не включил System.out.println («Привет, мир!»); или.
Зак Липтон
+1 за концепции против эффективных методов для "реального мира". Никто тоже не учил управлению версиями, по крайней мере, когда я был в школе - но тогда я уже древний :)
Дэвид
Я взял класс операционных систем, где мы должны были реализовать различные части, такие как планировщик; мы сосредоточились на одной такой части за раз (исключительно), потому что в тот момент мы были не в состоянии сделать больше . Но размышления о попытках заставить все эти части работать одновременно были тем, что дало мне (начало) понимание сложности разработки "реального мира" / "программирования в целом".
Дэвид
14

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

Гораздо проще начать с первых принципов, а затем сказать: «Это базовая структура. Этот язык (или его библиотеки) дает вам эту высокоуровневую структуру данных, которая делает все это, но дает вам x, y и z», чем это значит: «Таковы эти высокоуровневые структуры данных, а теперь вот что скрыто». Обучение рассуждать о том, использовать ли LinkedList против ArrayList (или HashSet против TreeSet), обычно является курсом Алгоритмов второго или третьего курса. Списки и карты имеют одинаковые интерфейсы и дают одинаковые результаты, но могут иметь разное поведение в приложении любого размера. И как только вы выйдете из программирования 101, нет никакой гарантии, что в программировании 102 будет использоваться один и тот же язык. Если вы начинаете с концепции массива, вы можете просто сказать:

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

«Список» - это совершенно другой источник рыбы и может быть реализован разными способами (ArrayList, LinkedList и, возможно, парой, которую я забыл), с принципиально разными характеристиками производительности. Не понимая начинку , что различные классы Списка делают, вы не можете иметь содержательную дискуссию о том, когда следует использовать List foo = new ArrayList()против List foo = new LinkedList(). Если вы попытаетесь заставить студента использовать реализацию List, кто-то спросит, почему вы используете ArrayList вместо одной из других реализаций. И «ArrayList» включает в себя слово «Array» и поддерживается одним, так что это действительно не огромный логический переход от «массива» к «ArrayList».

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

  • Поиск и итерация немного быстрее, потому что вы не имеете дело с накладными расходами при вызове метода: foo[n]разыменовываете и выполняет некоторую арифметику указателей за кадром, в то время как foo.get(n)должен разыменовать, выполнить вызов метода, сделать вторую разыменование, а затем, возможно, сделать арифметику указателя (если вы используете ArrayList; потенциально LinkedLists должен выполнять итерации по каждому элементу списка).
  • Инициализация намного чище: int[] foo = new int[]{1, 2, 3, 4, 5}против предложений в другом вопросе StackOverflow
Карл С.
источник
Другой сценарий, когда массивы массивно бьют массивы, - это когда последовательность, в которой становятся доступными элементы, соответствует последовательности, в которой станут известны их конечные позиции, но не соответствует конечной последовательности. Если permэто int[256]содержит перестановку, можно легко инвертировать ее с помощью массива: int[] inv = new int[256]; for (int i=0; i<256; i++) inv[perm[i]]=i; я не думаю, что что-либо, что можно написать с помощью, ArrayList<>будет таким же чистым.
суперкат
@supercat Это не совсем проблема с динамическими массивами, просто конкретная реализация; ArrayListможно было бы легко получить конструктор, который создает инициализированный по умолчанию список определенного размера.
Доваль
Есть ли у вас источники, подтверждающие утверждение о том, что список массивов связан с накладными расходами при вызове метода? Теоретически так и есть, но на практике я бы удивился, если бы getи setне вставал.
Доваль
@Doval: Нет причин, чтобы хорошо спроектированный язык / фреймворк не должен предоставлять тип динамического массива, который может удобно добавлять элементы вне последовательности, но Java не предоставляет такой тип.
суперкат
@Doval: Даже если getи setможет быть встроено , что-то вроде myList.set(23,myList.get(23)+1)будет далеко не так эффективно, как myArray[23]+=1. Кроме того, даже для типов, которые не нуждаются в упаковке, я был бы очень удивлен, если бы любой JITter мог что-либо эквивалентно for (i=0; i<1000; i++) myList2.set(i+2000,myList2.get(i+3000));чему-либо, чья производительность была бы где-то рядом. System.arrayCopy(myArray1,3000,myArray2,2000,1000); Нет причины, по которой тип динамического массива фреймворка не должен предлагать быструю операцию копирования диапазона, но ява нет.
суперкат
7

Java позволяет хранить переменные любого типа в массивах. Напротив, ArrayListпозволяет только хранение ссылок. Таким образом, можно бесполезно обсуждать ArrayListбез предварительного рассмотрения того, как автобокс преобразует примитивы в ссылочные типы и как автоматическая распаковка иногда преобразует ссылочные типы в примитивы:

for (int i=10; i<=10000; i*=10)
{
    ArrayList<Integer> l = new ArrayList<Integer>();
    l.add(i);
    l.add(i);
    l.add(l.get(0));
    System.out.print("i=" + i);
    System.out.print(" #0==i:" + (l.get(0)==i));
    System.out.print(" #1==i:" + (l.get(1)==i));
    System.out.print(" #2==i:" + (l.get(2)==i));
    System.out.print(" #0=#1:" + (l.get(0)==l.get(1)));
    System.out.print(" #1=#2:" + (l.get(1)==l.get(2)));
    System.out.println(" #0=#2:" + (l.get(0)==l.get(2)));
}

Если бы код использовал int[3]скорее вместо ArrayList, то не было бы никаких сюрпризов. Все три элемента будут сравниваться iдруг с другом. Используя ArrayList, однако, даже если все три элемента списка будут всегда сравниваться равными i, а первый и третий всегда будут сравниваться равными друг другу, первые два элемента будут равны друг другу только тогда, когда i1, 10 или 100, но (на большинстве реализаций) не когда i1000 или 10000.

Supercat
источник
Не могли бы вы объяснить, почему # 0 и # 1 будут равны, когда они 1 или 10 или 100? Я следил до этого момента.
Мэтью Рид
2
@MatthewRead: Integerкласс имеет вложенный класс, IntegerCacheкоторый называется предварительно инициализированными Integerобъектами для диапазона значений, который обычно расширяется -128..127; для помещения значения за пределы этого диапазона потребуется создать новый объект, но помещение значения в пределах кэшированного диапазона просто вернет ссылку на один из предварительно инициализированных объектов, хранящихся в IntegerCache.cache. Любой хороший Java-программист должен знать, что Integerпеременные двух типов, инкапсулирующие одно и то же значение, могут сравниваться или не совпадать, но слишком раннее внедрение этой идеи может заставить студентов бежать в ужасе.
суперкат
Да, никогда бы не подумал, что это из-за предварительно инициализированных объектов. Спасибо за информацию!
Мэтью Рид
1
@ MatthewRead: Я бы хотел, чтобы Java не разрешал некоторые виды неявного преобразования с ==. Учитывая вероятность того, что автоматическое распаковывание может сработать, я был бы склонен полностью его запретить, но его поведение ==особенно ужасно. ==Оператор также плохо ведет себя в подобных случаях 16777217==16777216f[отчетам истинных], и неявные преобразования для long v=Math.Round(123456789), w=Math.Round(123456789012345)склонны к неожиданным [вы можете догадаться , что эти выражения будут давать?]
Supercat
Что касается IntegerCache, конечно, бывают моменты, когда это может помочь производительности, но это может часто вызывать код, который просто прост для работы. В некотором смысле мне хотелось бы, чтобы существовал режим, в котором бокс квазислучайно возвращал объекты из двух целочисленных кешей и квазислучайно заменял элементы кеша новыми, чтобы код, основанный на поведении бокса значений -128..127, был бы вряд ли удастся очень долго.
суперкат
6

Я думаю, что имеет смысл научить сначала использовать массивы из-за того, что ArrayListиспользует массив внутри. У ArrayListкласса есть переменная-член, elementDataкоторая называется Objectмассивом.

Из ArrayList исходного кода JDK :

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer.
 */
private transient Object[] elementData;

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

Дерек W
источник
Но массив использует указатель на блок памяти внутри. Зачем начинать именно с этого уровня абстракции?
Вопрос был помечен как Java- Он спрашивал, зачем учить массивы, когда обычно вы можете использовать ArrayList. У Java нет указателей. Правильно или нет, я придерживаюсь мнения, что C / C ++ - лучший язык для начинающих, чем Java. Многие темы в программировании могут быть лучше поняты благодаря знанию C / C ++.
Дерек W
3

Если предположить, что с этим списком действительно легче работать, это не имеет значения. Обучение - это больше «от базового к сложному», чем от «простого к сложному». Если бы основы не были важны, то информатика не была бы академической областью. Вы можете просто научиться объединять приложения, используя существующие фреймворки / библиотеки, из онлайн-учебников. (Конечно, кто-то должен писать эти библиотеки ... а кто-то должен реализовывать ArrayListв первую очередь ....)

Мэтью Рид
источник
Во многих случаях такое использование ArrayListможет быть лучше обработано с использованием отдельного массива и счетчика «liveItems», за исключением того, что нет удобного способа работать с массивом и считать вместе, кроме как путем их агрегирования.
суперкат
2

Это потому, что самое важное в академическом образовании - научить вас использовать правильную терминологию для описания того, что вы делаете.

Список - это нечто иное, чем этот массив. и вы не можете использовать java.util.Listв Java, потому что это интерфейс. Вы обычно используете, java.util.ArrayListкоторый является реализацией List, это не список, а объектная оболочка вокруг динамического массива. Итак, вы говорите, что используете «Список», но вы используете массив.

Разумно пропустить этот терминологический хаос и просто использовать массивы, чтобы узнать, что такое массив. Если вы используете массивы в Java, по крайней мере, вы используете массивы.

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

Дунайский моряк
источник
как насчет hashmap? В некотором смысле массив - это просто тип hashmap.
Thufir
@Thufir, как массив может быть hashmap? Это совершенно разные структуры данных.
Дунайский моряк
Вы можете представить массив с помощью hashmap. что является более "фундаментальным"? Я бы сказал, что hashmap более концептуально интересен.
Thufir
1
@ Туфира нет, ты не можешь. Вы можете только подражать. Внутренне каждая структура данных будет такой, какая она есть. Это принципиально и концептуально разные вещи. Вот почему плохая идея начать изучать программирование с таких очень абстрактных языков, как Java или JavaScript. Там неясно, что на самом деле представляют собой структуры данных.
Дунайский моряк
1

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

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

И да, с академической точки зрения, есть дополнительная причина обучения студентов основам. Однако это идет немного глубже. Массивы и списки являются хорошим примером более объемных типов, которые часто просто строятся поверх базовых экземпляров более легких типов, а часто просто оборачиваются вокруг них. Даже если списки не имеют базовых массивов, они ведут себя внешне так же, как и они. Одна часть обучения кого-либо тому, что такое List, состоит в том, чтобы научить его, что такое массив.

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

Panzercrisis
источник
Я бы не сказал, что список обладает «большей» функциональностью, так же как и «другой». Новый T[]будет готов, прямо у ворот, принимать элементы в любом порядке, в то время как новый ArrayList<T>требует, чтобы элементы были добавлены по порядку, прежде чем они могут быть изменены. A T[]может T[]относительно быстро скопировать произвольный диапазон элементов в другой схожий по размеру диапазон , при ArrayList<T>этом потребуется считывать элементы по отдельности из одного списка и сохранять их в другом - гораздо медленнее и менее удобно.
Суперкат