Pourquoi les écoles enseignent des tableaux sur la liste? [fermé]

36

La plupart des tâches de mon école pour les cours de programmation initiaux m'obligeaient à utiliser des tableaux. Je travaille à plein temps maintenant et je n'ai jamais utilisé de tableau pour aucun projet sur lequel j'ai travaillé. Même dans les projets existants, je n’ai jamais vu l’utilisation de tableaux de données où que ce soit. À mon avis, List est plus facile à utiliser et constitue un standard. Pourquoi les professeurs disent-ils aux étudiants d'utiliser des tableaux dans leurs travaux? Est-ce juste pour que les étudiants comprennent les bases?

Comme la plupart des universités enseignent Java, cette question est spécifique à Java.

Hurle Hagrid
la source
7
Les tableaux sont plus fondamentaux.
user253751
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter .
Ingénieur du monde

Réponses:

120

Parce que les tableaux enseignent des concepts tels que l'indexation et les limites, deux concepts fondamentalement importants en programmation informatique.

Les listes ne sont pas un "standard". Il existe une grande variété d'espaces problématiques pour lesquels les tableaux conviennent parfaitement.

Robert Harvey
la source
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter .
Ingénieur mondial
48

Ils voulaient probablement commencer par la structure de données qui représente le plus fidèlement le fonctionnement d'un ordinateur. Vous devez donc vous familiariser avec les principes fondamentaux avant de commencer à introduire des abstractions de niveau supérieur, telles que des listes, qui facilitent le travail. Sinon, vous n'auriez aucun moyen de comprendre pourquoi une structure ou un algorithme donné est lent / rapide pour certaines opérations et pas pour d'autres; si la mémoire de l'ordinateur était réellement constituée de listes chaînées, le monde serait très différent.

Pour la même raison, ma première classe de programmation à l'université était en C et les autres classes étaient toutes en C ++, Java et d'autres langages. Ce n'est pas que C soit meilleur ou plus facile, c'est que C (et Array) ne vous cache rien.

Ixrec
la source
7
Il est plus facile de travailler avec une liste dans un code réel, mais un tableau est plus facile à comprendre (et tout à fait), et plus important à comprendre car il est fondamental et universel, alors que List (Java) ne l’est pas. Au moins c'est mon avis.
Ixrec
21
Une affectation dans laquelle vous stockez des éléments dans un tableau et y accédez ultérieurement est une affectation de structure de données . Vous ne l'avez peut-être pas compris. Vous devez vous demander ce qui produit de meilleurs ingénieurs, comprenant les modèles informatiques de base ou apprenant la bibliothèque standard d'une langue? Le consensus général (et je suis d'accord, fwiw) est que vous ne comprendrez pas beaucoup le contenu de la bibliothèque sans d'abord comprendre les bases du calcul.
Kent A.
12
LinkedList, ArrayList, OrderedList, etc. Quelle liste devriez-vous apprendre en premier? Comment apprécieriez-vous ce qu’ils font pour vous si vous ne comprenez pas pourquoi ils existent au départ?
Kent A.
10
+1 à @KentAnderson. Les écoles doivent former des ingénieurs qui comprennent les structures de données à un niveau bas; idéalement, produire des ingénieurs capables d’implémenter facilement les structures de base en C. Tout autre programme est simplement un JavaSchool.
Christian Willman
2
"Ils voulaient probablement commencer par la structure de données qui représente le mieux le fonctionnement d'un ordinateur" - Alors, qu'en est-il des ordinateurs avec une mémoire à structure de liste ou à objet? "Ce n'est pas que C soit meilleur ou plus facile, c'est que C (et Array) ne te cache rien." - À moins que votre ordinateur ne possède pas de pointeurs, comme l'AS / 400, où C s'exécute essentiellement dans une machine virtuelle et cache quasiment tout pour vous.
Jörg W Mittag
21

Les réponses ci-dessus sont excellentes, mais j'en ai une autre en tête. La main()méthode de Java signifie que les étudiants se familiarisent très tôt avec des tableaux de base, souvent dès le premier jour de classe. Pourquoi?

public static void main(String[] args)

C'est la première chose à laquelle vous devrez faire face pour écrire Hello World et au-delà. (J'ai vu certains cours utiliser des IDE d'enseignement tels que BlueJ au début, qui vous permettent de pointer et de cliquer pour exécuter des méthodes arbitraires, mais nous les mettrons de côté ...) Bien qu'il puisse être intéressant de passer manuellement certaines Ces mots-clés pour un peu de temps, tôt ou tard, la plupart des enseignants vont vouloir les expliquer. En effet, une question classique du niveau débutant consiste à demander aux étudiants de donner la signification de chaque mot clé dans un programme Hello World de base. Et que trouvons-nous dans la signature de notre méthode principale? Un tableau (la raison en est en partie historique. ArrayList n’existait pas dans Java 1.0). Les tableaux font partie de cet ensemble de connaissances de base. La liste n'est pas.

Cela dit, il n'est pas rare que les classes introduisent ArrayList un peu plus tard dans le cours, en particulier une fois que les objets et leur utilisation ont été traités. Même le programme d’apprentissage d’AP Computer Science pour Java inclut ArrayList (je le sais bien, et Google semble le confirmer), bien qu’il ignore le fait que ArrayList implémente List et le reste de Collections Framework.

Enfin, j’ai appris que les programmes universitaires CS utilisent Java pour explorer les concepts CS et de programmation plutôt que d’enseigner aux étudiants comment devenir de bons développeurs Java. Certains programmes peuvent être plus axés sur le recrutement de développeurs professionnels alors que d'autres sont davantage axés sur la théorie, mais dans les deux cas, il y a beaucoup à apprendre sur l'utilisation de Java dans un travail professionnel réel qui ne sera pas enseigné dans la plupart des programmes universitaires. Cela va des modèles de conception et des techniques telles que celles de Effective Java aux frameworks tels que Spring, Hibernate ou JUnit, voire des éléments plus courants tels que JSP ou JDBC. Avec cette philosophie à l’esprit, mettre l’accent sur les tableaux plutôt que sur la liste ArrayList plus communément utilisée a un peu plus de sens.

Zach Lipton
la source
3
@ Déduplicateur, bien sûr. Ce n'était tout simplement pas pertinent pour mon point concernant les tableaux, alors je l'ai omis. Je n'ai pas non plus inclus System.out.println ("Hello World!"); non plus.
Zach Lipton
+1 pour les concepts par rapport aux techniques efficaces pour le "monde réel". Personne n’apprenait le contrôle de version non plus, du moins pas quand j’étais à l’école - mais je suis un ancien :)
David
J'ai suivi un cours sur les systèmes d'exploitation où nous avons dû implémenter divers éléments, comme un planificateur; nous nous sommes concentrés (exclusivement) sur une telle pièce à la fois, car à ce moment-là, nous ne pouvions pas en faire plus . Mais penser à essayer de faire fonctionner tous ces éléments en même temps, c’est ce qui m’a donné (à ses débuts) une idée de la complexité du développement / de la "programmation dans le monde réel".
David
14

L'une des raisons pour lesquelles les classes de programmation de première année utilisent des tableaux est héritée: c'est ainsi que les professeurs l'avaient apprise avant d'utiliser des bibliothèques standard avec des listes dynamiques. L'utilisation des types de données primitifs est également plus généralement applicable: les tableaux existent dans à peu près n'importe quel ordinateur. langage sous le soleil (et peut être mis en œuvre dans une poignée d'instructions de montage). Lorsque j'ai appris la programmation, la mise en place d'une liste chaînée faisait partie des tâches assignées.

Il est beaucoup plus facile de commencer par les principes de base, puis de dire: "Voilà la structure de base. Ce langage (ou ses bibliothèques) vous donne cette structure de données de haut niveau qui fait tout cela, mais vous donne x, y et z", c'est dire "Voilà donc ces structures de données de haut niveau, maintenant voici ce qu'il y a sous le capot." Apprendre à raisonner sur l'utilisation d'une LinkedList par rapport à un ArrayList (ou à un HashSet par rapport à un TreeSet) est généralement un cours d'algorithmes de deuxième ou troisième année. Les listes et les cartes ont les mêmes interfaces et donnent les mêmes résultats, mais peuvent avoir des comportements très différents dans une application de toute taille. Et une fois que vous avez quitté Programmation 101, rien ne garantit que Programmation 102 utilisera le même langage. Si vous partez du concept de tableau, vous pouvez simplement dire "

Une autre raison de préférer "tableau" à "liste" dans un cours d'introduction est que les tableaux sont fondamentalement faciles à comprendre: un tableau de bytes20 octets prend 20 octets (plus un couple pour indiquer la fin du tableau ou sa longueur, en fonction de l'implémentation ).

Une "liste" est une combinaison de poissons complètement différente et peut être mise en œuvre de différentes manières (ArrayList, LinkedList et probablement un couple que j'ai oublié), avec des caractéristiques de performance fondamentalement différentes. Sans comprendre le courage de ce que les différentes classes de la liste font, vous ne pouvez pas avoir une discussion significative quand vous devez utiliser List foo = new ArrayList()contre List foo = new LinkedList(). Si vous essayez d'amener l'étudiant à utiliser une implémentation de List, quelqu'un vous demandera pourquoi vous utilisez ArrayList au lieu d'une des autres implémentations. Et "ArrayList" inclut le mot "Array" et est soutenu par un, ce n'est donc pas un énorme saut logique entre "array" et "ArrayList".

Contrairement à la croyance populaire, il existe des situations dans lesquelles il est judicieux d'utiliser des tableaux sur des listes, en particulier lorsqu'il s'agit d'une liste de taille statique. Voici un couple:

  • La recherche et l'itération sont légèrement plus rapides car vous ne traitez pas de surcharge d'invocation de méthode: foo[n]déréférencez et foo.get(n)faites de l' arithmétique de pointeur en coulisse, tout en devant déréférencer, faire une invocation de méthode, faire une deuxième déréférencement, puis peut - être faire de l'arithmétique de pointeur (Si vous utilisez une ArrayList; LinkedLists doit potentiellement itérer sur chaque élément de la liste).
  • L'initialisation est beaucoup plus propre: par int[] foo = new int[]{1, 2, 3, 4, 5}rapport aux suggestions de la question Another StackOverflow
Carl C.
la source
Un autre scénario où les tableaux battent massivement les tableaux est lorsque la séquence dans laquelle les éléments deviennent disponibles correspond à la séquence dans laquelle leurs positions finales seront connues, mais ne correspond pas à la séquence finale. Si permc'est un int[256]qui tient une permutation, on peut facilement l'inverser avec un tableau: int[] inv = new int[256]; for (int i=0; i<256; i++) inv[perm[i]]=i; Je ne pense pas que tout ce que l'on pourrait écrire avec un ArrayList<>serait aussi net.
Supercat
@supercat Ce n'est pas vraiment un problème avec les tableaux dynamiques, juste l'implémentation particulière; ArrayListaurait pu facilement recevoir un constructeur qui crée une liste par défaut initialisée d'une certaine taille.
Doval
Avez-vous des sources pour sauvegarder l'affirmation selon laquelle une liste de tableaux doit faire face à une surcharge d'invocation de méthode? En théorie , il le fait, mais en pratique , je serais surpris si getet setne soit pas inline.
Doval
@Doval: Il n'y a aucune raison pour qu'un langage / framework bien conçu ne fournisse pas un type de tableau dynamique pouvant facilement ajouter des éléments hors séquence, mais Java ne fournit pas un tel type.
Supercat
@Doval: Même si getet setpeut être aligné, quelque chose comme myList.set(23,myList.get(23)+1)sera loin d'être aussi efficace que myArray[23]+=1. De plus, même pour les types qui n'auraient pas besoin de boxe, je serais très surpris qu'un JITter puisse trouver quelque chose d'équivalent for (i=0; i<1000; i++) myList2.set(i+2000,myList2.get(i+3000));dans quelque chose dont les performances sont proches System.arrayCopy(myArray1,3000,myArray2,2000,1000); l'une de l'autre. mais Java ne le fait pas.
Supercat
7

Java permet de stocker des variables de tout type dans des tableaux. En revanche, ArrayListn'autorise que le stockage de références. On ne peut donc pas discuter utilement ArrayListsans d'abord expliquer comment la box automatique convertira les primitives en types de référence et comment le déballage automatique convertira parfois les types de référence en primitives:

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)));
}

Si le code avait utilisé un int[3]plutôt qu'un ArrayList, il n'y aurait pas de surprises. Les trois éléments se comparent égaux iet réciproques. L' utilisation ArrayList, cependant, même si les trois éléments de la liste sera toujours comparer égale à i, et le premier et le troisième compareront toujours égal à l'autre, les deux premiers éléments seront seulement égaux entre eux quand iest de 1, 10 ou 100, mais (sur la plupart des implémentations) pas quand iest 1000 ou 10000.

supercat
la source
Pourriez-vous expliquer pourquoi # 0 et # 1 seront égaux quand ils auront 1, 10 ou 100? J'ai suivi jusqu'à ce point.
Matthew Lu
2
@MatthewRead: la Integerclasse a une classe imbriquée appelée IntegerCachequi contient des Integerobjets pré-initialisés pour une plage de valeurs qui s'étend généralement de -128..127; La mise en boîte d'une valeur en dehors de cette plage nécessitera la création d'un nouvel objet, mais la mise en boîte d'une valeur dans la plage mise en cache renverra simplement une référence à l'un des objets pré-initialisés stockés dans IntegerCache.cache. Tout bon programmeur Java doit savoir que deux Integervariables de type encapsulant la même valeur peuvent se comparer ou non, mais introduire cette idée trop tôt risque de faire fuir les étudiants dans la terreur.
Supercat
Euh, je n'aurais jamais deviné que c'était dû à des objets pré-initalisés. Merci pour l'info!
Matthew Lu
1
@ MatthewRead: J'aurais aimé que Java n'autorise pas certains types de conversion implicite avec ==. Compte tenu de la possibilité que l'auto-unboxing puisse lancer, je serais enclin à le rejeter complètement, mais son comportement ==est particulièrement horrible. L' ==opérateur se comporte également mal dans des cas tels que 16777217==16777216f[rapports vrais], et les conversions implicites long v=Math.Round(123456789), w=Math.Round(123456789012345)sont susceptibles d'être inattendues [pouvez-vous deviner ce que ces expressions vont donner?]
supercat
Pour IntegerCachece qui est des performances, cela peut certes être bénéfique, mais cela peut souvent provoquer un code qui est tout simplement mauvais pour un travail en quelque sorte. D'une certaine manière, j'aimerais qu'il existe un mode dans lequel la boxe renverrait des objets de deux caches entiers de manière quasi-aléatoire et remplacerait de manière quasi-aléatoire les éléments de cache par de nouveaux, de sorte que le code reposant sur le comportement de boxing des valeurs -128..127 serait peu de chances de réussir très longtemps.
Supercat
6

Je pense qu'il est logique d'apprendre à utiliser d'abord les tableaux en raison du fait qu'il ArrayListutilise un tableau en interne. La ArrayListclasse a une variable membre appelée elementDataqui est un Objecttableau.

A partir du ArrayList code source 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;

Lorsque vous ajoutez, mettez à jour, récupérez ou supprimez des éléments d'un ArrayListil utilise ce tableau interne pour effectuer ces opérations. Comme l’ a déjà souligné l’ utilisateur, Ixrec n’est en ArrayListfait qu’une abstraction de niveau supérieur sur laquelle il est généralement plus facile de travailler.

Derek W
la source
Mais un tableau utilise un pointeur sur un bloc de mémoire, en interne. Pourquoi commencer à ce niveau d'abstraction?
La question est étiquetée Java- Elle demandait pourquoi enseigner aux tableaux alors que vous pouvez généralement les utiliser ArrayList. Java n'a pas de pointeurs. Vrai ou faux, j'estime que le C / C ++ est un meilleur langage pour commencer les étudiants que Java. De nombreux sujets de programmation peuvent être mieux compris en ayant une connaissance de C / C ++.
Derek W
3

En supposant que cette liste soit effectivement plus facile à utiliser, comme vous le dites, cela n'a pas vraiment d'importance. L'apprentissage est plus "simple à complexe" que "facile à difficile". Si les fondamentaux n'étaient pas importants, alors l'informatique ne serait pas un domaine académique. Vous pouvez simplement apprendre à cliquer sur des applications en utilisant des frameworks / bibliothèques existants à partir de tutoriels en ligne. (Bien sûr, il faut que quelqu'un écrive ces bibliothèques ... et que quelqu'un d'autre implémente ArrayList...)

Matthew Read
la source
Dans de nombreux cas, cette utilisation ArrayListpourrait être mieux gérée en utilisant un tableau séparé et un nombre "liveItems", sauf qu'il n'existe aucun moyen pratique de travailler avec le tableau et le comptage ensemble, sauf en les agrégeant.
Supercat
2

C'est parce que la chose la plus cruciale dans l'enseignement universitaire est de vous apprendre à utiliser la terminologie correcte pour décrire ce que vous faites.

La liste est autre chose que ce tableau. et vous ne pouvez pas utiliser java.util.ListJava car c'est une interface. Vous utilisez généralement java.util.ArrayListune implémentation List, ce n'est pas une liste mais un wrapper d'objet autour d'un tableau dynamique. Donc, vous dites que vous utilisez une liste mais que vous utilisez un tableau.

Il est très raisonnable d'éviter ce chaos terminologique et d'utiliser simplement des tableaux pour apprendre aux étudiants ce qu'est un tableau. Si vous utilisez des tableaux en Java, vous utilisez au moins des tableaux.

Honnêtement, c'est également l'argument pour lequel enseigner la programmation avec Java n'est pas une bonne idée. Il est difficile d'apprendre correctement les concepts de base de la programmation.

Marin danubien
la source
Qu'en est-il de hashmap? un tableau est juste un type de hashmap, en quelque sorte ..
Thufir
@Thufir comment un tableau peut-il être une hashmap? Ce sont des structures de données complètement différentes.
Danubian Sailor
vous pouvez représenter un tableau avec un hashmap. qui est plus "fondamental"? Je dirais que hashmap est plus intéressant conceptuellement.
Thufir
1
@ Thufir non, vous ne pouvez pas. Vous pouvez seulement émuler. En interne, chaque structure de données sera ce qu'elle est. Ce sont des choses fondamentalement et conceptuellement différentes. C'est pourquoi il est déconseillé de commencer à apprendre à programmer avec des langages aussi abstraits que Java ou JavaScript. On ne sait pas vraiment quelles sont les structures de données.
Danubian Sailor
1

Vous avez littéralement jamais vu ou utilisé des tableaux du tout? Nous les utilisons tout le temps, en plus des listes. Nous n'utilisons généralement pas Java, mais nous utilisons beaucoup d'autres langages qui dessinent des similitudes évidentes.

Entre les tableaux et les listes, l'un est plus léger et, en plus, plus précis, tandis que l'autre a plus de fonctionnalités. En règle générale, en programmation, quand il y a deux types similaires qui sont essentiellement divisés de la sorte, vous devriez opter pour le plus léger, sauf si vous avez réellement besoin du plus sophistiqué. En plus de réduire les frais généraux, cela permet de mieux contrôler la quantité d'encombrement et d'état dans le programme et en particulier dans son code . Si quelque chose ne va pas pendant le test, vous avez moins de lieux à regarder; et plus important encore dans le cas de tableaux vs listes, les gens ont une meilleure idée de la portée limitée de l'utilisation que vous en faites et de ce que vous essayez de faire.

Et oui, d'un point de vue académique, il y a la raison supplémentaire d'enseigner les bases aux étudiants. Cependant, cela va un peu plus loin. Les tableaux et les listes sont un bon exemple de types plus volumineux souvent construits simplement au-dessus, et souvent tout simplement, autour d'instances sous-jacentes de types plus légers. Même lorsque les listes ne comportent pas de tableaux sous-jacents, elles se comportent extérieurement comme elles le font. Enseigner à une personne ce qu'est une liste consisterait en partie à lui apprendre ce qu'est un tableau.

Je pouvais voir que cela devenait peut-être hors de contrôle dans un langage tel que C ++, où les tableaux ne pouvaient en principe pas être plus dépouillés qu’ils ne le sont, mais dans les langages de niveau supérieur, ils sont presque des listes à part. S'ils répondent parfaitement à vos besoins dans une situation donnée, pourquoi devriez-vous utiliser autre chose?

Panzercrisis
la source
Je ne dirais pas qu'une liste comporte "plus" de fonctionnalités, à la différence des fonctionnalités "différentes". Un nouveau T[]sera prêt, dès la sortie de la porte, à accepter les articles dans n'importe quel ordre, alors qu'un ArrayList<T>exige que les articles soient ajoutés, dans l'ordre, avant de pouvoir être modifiés. A T[]peut copier T[]assez rapidement une plage d’articles quelconque dans une plage de taille similaire , tout en ArrayList<T>nécessitant de lire des articles individuellement dans une liste et de les stocker dans l’autre - beaucoup plus lentement et moins facilement.
Supercat