Dlaczego szkoły uczą tablic nad Listą? [Zamknięte]

36

Większość zadań w mojej szkole na początkowych zajęciach z programowania wymagała ode mnie używania tablic. Pracuję teraz na pełny etat i nigdy nie użyłem tablicy dla żadnego projektu, nad którym pracowałem. Nawet w istniejących projektach nigdzie nie widziałem zastosowania tablic. Moim zdaniem Lista jest łatwiejsza w użyciu i jest standardem. Dlaczego profesorowie mówią uczniom, aby używali tablic w swoich zadaniach? Czy to po to, aby uczniowie rozumieli podstawy?

Ponieważ większość uniwersytetów uczy języka Java, pytanie to dotyczy języka Java.

Wycie Hagrid
źródło
7
Tablice są bardziej fundamentalne.
user253751,
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Inżynier świata

Odpowiedzi:

120

Ponieważ tablice uczą takich pojęć, jak indeksowanie i granice, dwa fundamentalnie ważne pojęcia w programowaniu komputerowym.

Listy nie są „standardem”. Istnieje wiele różnych miejsc problemowych, do których idealnie pasują tablice.

Robert Harvey
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Inżynier świata
48

Prawdopodobnie chcieli zacząć od struktury danych, która najdokładniej odzwierciedla sposób działania komputera, więc znasz podstawy, zanim zaczną wprowadzać abstrakcje wyższego poziomu, takie jak Listy, które ułatwiają pracę. W przeciwnym razie nie byłbyś w stanie zrozumieć, dlaczego określona struktura lub algorytm działa wolno / szybko dla niektórych operacji, a nie dla innych; gdyby pamięć komputera faktycznie została utworzona z połączonych list, świat byłby zupełnie innym miejscem.

Z tego samego powodu, moja pierwsza klasa programowania w college'u była w C, a reszta zajęć była w C ++, Java i innych językach. Nie chodzi o to, że C jest w jakiś sposób lepszy lub łatwiejszy, to o to, że C (i Array) niczego przed tobą nie ukrywa.

Ixrec
źródło
7
Z listą łatwiej jest pracować w prawdziwym kodzie, ale tablica jest łatwiejsza (całkowicie) do zrozumienia i ważniejsza do zrozumienia, ponieważ są one podstawowe i uniwersalne, podczas gdy lista (Java) nie jest. Przynajmniej taka jest moja opinia.
Ixrec,
21
Przypisanie, w którym przechowujesz rzeczy w tablicy i uzyskujesz do nich dostęp później, jest przypisaniem struktury danych . Być może po prostu nie zdawałeś sobie z tego sprawy. Musisz zadać sobie pytanie, co produkuje lepszych inżynierów, rozumienie podstawowych modeli obliczeniowych lub naukę standardowej biblioteki języka? Ogólny concensus (i zgadzam się, fwiw) jest taki, że nie zrozumiesz dużo zawartości biblioteki bez wcześniejszego zrozumienia podstaw obliczeń.
Kent A.
12
LinkedList, ArrayList, OrdersList itp. Której listy powinieneś się nauczyć najpierw? Jak byś docenił to, co dla ciebie robią, jeśli nie rozumiesz, dlaczego one istnieją?
Kent A.
10
+1 do @KentAnderson. Szkoły muszą produkować inżynierów, którzy rozumieją struktury danych na niskim poziomie; idealnie, produkując inżynierów, którzy mogą łatwo wdrożyć podstawowe struktury w C. Każdy inny program jest jedynie JavaSchool.
Christian Willman,
2
„Prawdopodobnie chcieli zacząć od struktury danych, która najdokładniej odzwierciedla sposób działania komputera” - a co z komputerami z pamięcią o strukturze listy lub o strukturze obiektowej? „Nie chodzi o to, że C jest w jakiś sposób lepszy lub łatwiejszy, ale to, że C (i Array) niczego przed tobą nie ukrywa”. - Chyba że twój komputer nie ma wskaźników, takich jak AS / 400, gdzie C zasadniczo działa na maszynie wirtualnej i ukrywa prawie wszystko dla ciebie.
Jörg W Mittag,
21

Powyższe odpowiedzi są świetne, ale mam na myśli inną. main()Metoda Java oznacza, że ​​uczniowie spotykają się z podstawowymi tablicami bardzo wcześnie, często już pierwszego dnia zajęć. Czemu?

public static void main(String[] args)

To pierwsza rzecz, z którą będziesz musiał się zmierzyć, aby napisać Hello World i nie tylko. (Widziałem, że niektóre kursy używają na początku nauczania IDE, takich jak BlueJ, które pozwalają na wskazywanie i klikanie w celu uruchomienia dowolnych metod, ale odłożymy je na bok ...) Chociaż może być wskazane, aby przeforsować niektóre z nich te słowa kluczowe przez jakiś czas, wcześniej czy później większość nauczycieli będzie chciała je wyjaśnić. Rzeczywiście, klasycznym pytaniem testowym dla początkujących jest poproszenie uczniów o podanie znaczenia każdego słowa kluczowego w podstawowym programie Hello World. A co znajdujemy jako część naszej głównej sygnatury metody? Tablica (Przyczyna tego jest częściowo historyczna. ArrayList nie istniał w Javie 1.0). Tablice są częścią tego podstawowego zestawu wiedzy. Lista nie jest.

To powiedziawszy, nie jest niczym niezwykłym, że klasy wprowadzają ArrayList nieco później w kursie, szczególnie po omówieniu obiektów i ich użycia. Nawet program nauczania informatyki AP dla Java zawiera ArrayList (wiem, że kiedyś to robił, a Google wydaje się wskazywać, że nadal tak robi), chociaż ignoruje fakt, że ArrayList implementuje List i resztę Frameworkm kolekcjonowania.

Wreszcie, z mojego doświadczenia wynika, że ​​uniwersyteckie programy CS używają Javy jako środka do eksploracji CS i koncepcji programistycznych, zamiast uczyć studentów, jak zostać dobrymi programistami Java. Niektóre programy mogą bardziej koncentrować się na rezygnacji z profesjonalnych programistów, podczas gdy inne koncentrują się bardziej na teorii, ale w obu przypadkach jest wiele do nauczenia się, jak używać Javy w prawdziwej pracy zawodowej, której nie uczy się w większości programów nauczania na studiach. Obejmuje to zarówno wzorce projektowe i techniki, takie jak w Effective Java , jak i frameworki, takie jak Spring, Hibernate lub JUnit, a nawet bardziej popularne rzeczy, takie jak JSP lub JDBC. Mając na uwadze tę filozofię, podkreślanie tablic w stosunku do częściej używanych ArrayList ma nieco więcej sensu.

Zach Lipton
źródło
3
@Deduplicator na pewno. To po prostu nie miało znaczenia w moim punkcie dotyczącym tablic, więc go pominąłem. Nie dodałem także System.out.println („Hello World!”); zarówno.
Zach Lipton,
+1 za koncepcje a skuteczne techniki dla „prawdziwego świata”. Nikt też nie uczył kontroli wersji, przynajmniej nie kiedy byłem w szkole - ale wtedy jestem starożytny :)
David
Wziąłem klasę systemów operacyjnych, w której musieliśmy zaimplementować różne elementy, takie jak harmonogram; skupialiśmy się na jednym takim kawałku na raz (wyłącznie), ponieważ w tym momencie nie byliśmy w stanie zrobić więcej . Ale myślenie o próbie uruchomienia wszystkich tych elementów w tym samym czasie dało mi (początki) zrozumienie złożoności „rzeczywistego” rozwoju / „programowania w dużym”.
David
14

Jednym z powodów, dla których klasy programowania pierwszego roku używają tablic, jest spuścizna: tak właśnie profesorowie nauczyli się tego, zanim zaczęliśmy używać standardowych bibliotek z dynamicznymi listami wypalonymi. Używanie prymitywnych typów danych ma również bardziej ogólne zastosowanie: tablice istnieją na prawie każdym komputerze język pod słońcem (i może być zaimplementowany w kilku instrukcjach montażu). Kiedy uczyłem się programowania, jednym z zadań było wdrożenie listy połączonej.

O wiele łatwiej jest zacząć od podstawowych zasad, a następnie powiedzieć „To jest podstawowa struktura. Ten język (lub jego biblioteki) zapewnia tę strukturę danych wysokiego poziomu, która robi wszystko, ale daje ci x, y i z” niż to znaczy „Więc to te struktury danych wysokiego poziomu, oto co jest pod maską”. Uczenie się, jak korzystać z LinkedList vs. ArrayList (lub HashSet vs. TreeSet) jest zwykle drugim lub trzecim rokiem kursu algorytmów. Listy i mapy mają te same interfejsy i dają te same wyniki, ale mogą mieć radykalnie różne zachowania w aplikacji dowolnej wielkości. Po wyjściu z programowania 101 nie ma gwarancji, że programowanie 102 będzie używać tego samego języka. Jeśli zaczniesz od koncepcji tablicy, możesz po prostu powiedzieć „

Innym powodem, dla którego preferuje się „tablicę” nad „listą” w kursie wprowadzającym jest to, że tablice są zasadniczo łatwe do zrozumienia: tablica 20 byteszajmuje 20 bajtów (plus kilka, aby wskazać koniec tablicy lub długość, w zależności od implementacji ).

„Lista” jest zupełnie innym kotłem rybnym i może być zaimplementowana na wiele różnych sposobów (ArrayList, LinkedList i pewnie kilka, o których zapomniałem), z zasadniczo różnymi cechami wydajności. Bez zrozumienia wnętrzności co różne zajęcia Lista robią, nie można mieć znaczący dyskusję kiedy należy użyć List foo = new ArrayList()kontra List foo = new LinkedList(). Jeśli spróbujesz zmusić ucznia do użycia implementacji listy, ktoś zapyta, dlaczego używasz ArrayList zamiast jednej z innych implementacji. A „ArrayList” zawiera słowo „Array” i jest przez nie poparte, więc tak naprawdę nie jest to ogromny skok logiczny z „tablicy” do „ArrayList”.

Wbrew powszechnemu przekonaniu, istnieją sytuacje, w których sensowne jest używanie tablic nad listami, szczególnie gdy mamy do czynienia z listą wielkości statycznej. Oto kilka:

  • Wyszukiwanie i iteracja są nieco szybsze, ponieważ nie masz do czynienia z narzutem wywołania metody: foo[n]dereferencje i niektóre zakulisowe operacje arytmetyczne na wskaźnikach, podczas gdy foo.get(n)trzeba je wyrejestrować, wykonać wywołanie metody, zrobić drugie dereferencje, a następnie może zrobić arytmetykę wskaźnika (jeśli używasz ArrayList; LinkedLists potencjalnie potrzebuje iteracji po każdym elemencie listy).
  • Inicjalizacja jest znacznie czystsza: w int[] foo = new int[]{1, 2, 3, 4, 5}porównaniu z sugestiami zawartymi w kolejnym pytaniu StackOverflow
Carl C.
źródło
Innym scenariuszem, w którym tablice masowo biją tablice, jest to, gdy sekwencja, w której elementy stają się dostępne, odpowiada sekwencji, w której ich końcowe pozycje staną się znane, ale nie pasuje do końcowej sekwencji. Jeśli permjest to int[256]permutacja, można ją łatwo odwrócić za pomocą tablicy: int[] inv = new int[256]; for (int i=0; i<256; i++) inv[perm[i]]=i; nie sądzę, aby cokolwiek, co można napisać za pomocą, ArrayList<>byłoby tak czyste.
supercat
@ superuper To nie jest tak naprawdę problem z dynamicznymi tablicami, tylko konkretna implementacja; ArrayListmógł łatwo otrzymać konstruktor, który tworzy domyślnie inicjowaną listę o określonym rozmiarze.
Doval
Czy masz źródła, które potwierdzają twierdzenie, że lista tablic ma do czynienia z narzutem wywołania metody? Teoretycznie tak, ale w praktyce byłbym zaskoczony, gdyby geti setnie daj się inlined.
Doval
@Doval: Nie ma powodu, dla którego dobrze zaprojektowany język / framework nie powinien dostarczać typu dynamicznej tablicy, który może wygodnie dodawać elementy poza kolejnością, ale Java nie zapewnia takiego typu.
supercat
@Doval: Nawet jeśli geti setmoże być wbudowany , coś takiego myList.set(23,myList.get(23)+1)nie będzie tak wydajne jak myArray[23]+=1. Co więcej, nawet dla typów, które nie wymagałyby boksu, byłbym bardzo zaskoczony, gdyby każdy JITter mógł cokolwiek równoważnego do for (i=0; i<1000; i++) myList2.set(i+2000,myList2.get(i+3000));czegoś, co jest blisko gdziekolwiek blisko. System.arrayCopy(myArray1,3000,myArray2,2000,1000); Nie ma powodu, aby dynamiczny typ tablicy frameworka nie oferował szybkiego działania w zakresie kopiowania, ale Java nie.
supercat
7

Java umożliwia przechowywanie zmiennych dowolnego typu w tablicach. Natomiast ArrayListpozwala tylko na przechowywanie referencji. Nie można zatem pożytecznie dyskutować ArrayListbez uprzedniego omówienia , w jaki sposób auto-boxowanie przekształci prymitywy w typy referencyjne, i jak auto-rozpakowanie czasami przekształci typy referencyjne w prymitywy:

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

Gdyby kod używał int[3]raczej niż an ArrayList, nie byłoby niespodzianek. Wszystkie trzy elementy byłyby ido siebie równe . Używając ArrayListjednak, mimo że wszystkie trzy elementy listy zawsze będą się porównywać równe i, a pierwszy i trzeci zawsze będą porównywać się równe, pierwsze dwa elementy będą sobie równe tylko, gdy iwynosi 1, 10 lub 100, ale (w większości implementacji) nie wtedy, gdy iwynosi 1000 lub 10000.

supercat
źródło
Czy możesz wyjaśnić, dlaczego liczby 0 i nr 1 będą równe, gdy będą miały wartość 1, 10 lub 100? Kontynuowałem do tego momentu.
Mateusz
2
@MatthewRead: IntegerKlasa zagnieżdżona o nazwie klasa, IntegerCachektóra przechowuje wstępnie zainicjowane Integerobiekty dla zakresu wartości, które zwykle rozciągają się na -128..127; boksowanie wartości spoza tego zakresu będzie wymagało utworzenia nowego obiektu, ale boksowanie wartości w zbuforowanym zakresie zwróci po prostu odwołanie do jednego z wstępnie zainicjowanych obiektów przechowywanych w IntegerCache.cache. Każdy dobry programista Java musi być świadomy, że Integerzmienne dwóch typów enkapsulujące tę samą wartość mogą, ale nie muszą się równać, ale zbyt wczesne wprowadzenie tego pomysłu może spowodować, że studenci uciekną z przerażenia.
supercat
Huh, nigdy bym nie przypuszczał, że to z powodu wstępnie zainicjowanych obiektów. Dzięki za informację!
Mateusz
1
@MatthewRead: Chciałbym, aby Java nie zezwalała na pewne rodzaje niejawnej konwersji ==. Biorąc pod uwagę możliwość, że automatyczne rozpakowywanie może rzucić, byłbym skłonny całkowicie to zabronić, ale jego zachowanie ==jest szczególnie okropne. ==Operator zachowuje się też źle w takich przypadkach 16777217==16777216f[Raporty true], a konwersje niejawne dla long v=Math.Round(123456789), w=Math.Round(123456789012345)są w stanie być nieoczekiwany [można się domyślać, co te wyrażenia przyniesie?]
SuperCat
Co do tego IntegerCache, z pewnością są chwile, kiedy może to pomóc w wydajności, ale często może powodować, że kod, który jest po prostu zły, nie działa. W pewnym sensie chciałbym, aby istniał tryb, w którym boks quasi-losowo zwraca obiekty z dwóch liczb całkowitych pamięci podręcznej i quasi-losowo zamienia elementy pamięci podręcznej na nowe, tak aby kod polegający na zachowaniu boksu wartości -128..127 byłby bardzo mało prawdopodobne, aby odniosło sukces bardzo długo.
supercat
6

Myślę, że sensowne jest nauczenie, jak najpierw korzystać z tablic, ponieważ ArrayListwewnętrznie korzysta z tablicy. ArrayListKlasa ma zmienną składową o nazwie elementData, która jest Objecttablicą.

Z ArrayList kodu źródłowego 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;

Kiedy dodajesz, aktualizujesz, pobierasz lub usuwasz elementy z ArrayList, używa tej wewnętrznej tablicy do wykonywania tych operacji. Jak zauważył już użytkownik Ixrec - ArrayListto tylko abstrakcja wyższego poziomu, z którą zwykle łatwiej jest pracować.

Derek W.
źródło
Ale tablica wewnętrznie używa wskaźnika do bloku pamięci. Po co zaczynać na tym poziomie abstrakcji?
Pytanie jest oznaczone jako Java- Zadawało pytanie, dlaczego uczyć tablic, kiedy zwykle można ich używać ArrayList. Java nie ma wskaźników. Dobrze czy źle, uważam, że C / C ++ jest lepszym językiem dla początkujących niż Java. Wiele tematów programowania można lepiej zrozumieć dzięki znajomości C / C ++.
Derek W
3

Zakładając, że lista jest rzeczywiście łatwiejsza do pracy, jak mówisz - to naprawdę nie ma znaczenia. Uczenie się dotyczy bardziej „podstawowego do złożonego” niż „łatwego do trudnego”. Gdyby podstawy nie były ważne, informatyka nie byłaby dziedziną akademicką. Możesz po prostu nauczyć się, jak klikać razem aplikacje przy użyciu istniejących platform / bibliotek z samouczków online. (Oczywiście, ktoś musi napisać te biblioteki ... i ktoś musi ArrayListprzede wszystkim zaimplementować ...)

Matthew Read
źródło
W wielu przypadkach z tym korzystaniem ArrayListmożna lepiej korzystać, używając osobnej tablicy i licznika „liveItems”, z wyjątkiem tego, że nie ma wygodnego sposobu pracy z tablicą i liczenia razem, z wyjątkiem ich agregacji.
supercat
2

Jest tak, ponieważ najważniejszą rzeczą w edukacji akademickiej jest nauczenie cię używania właściwej terminologii do opisywania swoich działań.

Lista jest czymś innym niż tablica. i Nie możesz używać java.util.Listw Javie, ponieważ jest to interfejs. Zazwyczaj używasz tego, java.util.ArrayListktóry jest implementacją listy, nie jest listą, ale jest opakowaniem obiektu wokół dynamicznej tablicy. Mówisz więc, że używasz „Listy”, ale używasz tablicy.

Bardzo rozsądnym jest ominąć chaos terminologiczny i po prostu użyć tablic, aby nauczyć uczniów, czym jest tablica. Jeśli używasz tablic w Javie, przynajmniej używasz tablic.

Szczerze mówiąc, jest to również argument, dlaczego nauczanie programowania w Javie nie jest dobrym pomysłem. Trudno jest poprawnie nauczyć się podstawowych pojęć programowania.

Żeglarz naddunajski
źródło
co z hashmap? tablica jest swego rodzaju skrótem, w pewnym sensie ..
Thufir,
@Thufir, jak tablica może być skrótem? To są zupełnie różne struktury danych.
Danubian Sailor
możesz reprezentować tablicę za pomocą mapy skrótów. co jest bardziej „fundamentalne”? Twierdziłbym, że hashmap jest bardziej interesujący pod względem koncepcyjnym.
Thufir
1
@Thufir nie, nie możesz. Możesz tylko emulować. Wewnętrznie każda struktura danych będzie taka, jaka jest. To są fundamentalnie i koncepcyjnie różne rzeczy. Dlatego złym pomysłem jest rozpoczęcie nauki programowania w tak abstrakcyjnych językach, jak Java czy JavaScript. Nie jest jasne, jakie naprawdę są struktury danych.
Danubian Sailor
1

Dosłownie nigdy nie widziałeś ani nie używałeś żadnych tablic? Używamy ich cały czas, oprócz list. Zwykle nie używamy Javy, ale używamy wielu innych języków, które wykazują oczywiste podobieństwa.

Pomiędzy tablicami i listami jeden jest lżejszy, a dodatkowo bardziej konkretny, podczas gdy drugi ma większą funkcjonalność. Zasadniczo w programowaniu, gdy istnieją dwa podobne typy, które są zasadniczo podzielone wzdłuż tych linii, powinieneś wybrać lekką, chyba że naprawdę potrzebujesz bardziej wymyślnego. Oprócz zmniejszenia narzutu, pomaga to utrzymać porządek i stan programu, a zwłaszcza jego kodu . Jeśli coś pójdzie nie tak podczas testowania, masz mniej miejsc do patrzenia; a co ważniejsze, w przypadku tablic vs. list, ludzie mają lepsze pojęcie o ograniczonym zakresie tego, do czego faktycznie go używasz i próbują z tym zrobić.

I tak, z akademickiego punktu widzenia istnieje dodatkowy powód, aby uczyć studentów podstaw. Jednak idzie to nieco głębiej. Tablice i listy są dobrym przykładem typów nieporęcznych, często budowanych na wierzchu, a często po prostu owijających, leżące u podstaw wystąpienia mniejszych typów. Nawet jeśli Listy nie mają podstawowych tablic, zachowują się na zewnątrz tak, jak mają. Częścią uczenia kogoś, czym jest lista, byłoby nauczenie jej, czym jest tablica.

Widziałem, jak to wymyka się spod kontroli w języku takim jak C ++, w którym tablice w zasadzie nie mogą być bardziej rozbierane niż są w rzeczywistości, ale w językach wyższego poziomu prawie same są listami. Jeśli idealnie pasują do twoich potrzeb w danej sytuacji, dlaczego miałbyś chcieć użyć czegoś innego?

Panzercrisis
źródło
Nie powiedziałbym, że lista ma „więcej” funkcjonalności, tak samo jak ma „inną” funkcjonalność. Nowy T[]będzie gotowy, zaraz po przejściu przez bramę, do przyjmowania przedmiotów w dowolnej kolejności, natomiast ArrayList<T>wymaga dodania przedmiotów w kolejności, zanim będą mogły zostać zmodyfikowane. A T[]może skopiować dowolny zakres przedmiotów do podobnego rozmiaru innego innego T[]stosunkowo szybko, podczas gdy ArrayList<T>wymagałoby to odczytania pojedynczych elementów z jednej listy i przechowywania ich na drugiej - znacznie wolniej i mniej wygodnie.
supercat