Definiowanie struktur danych

Odpowiedz Nowy wątek
2018-12-19 08:24
0

Jako że jestem zielony z programowania, do niedawna byłem pewny że tablica, lista, kolejka, stos to synonimy. Po uzupełnieniu wiedzy chciałbym przetestować te struktury. Jak je zdefiniować w Pythonie? (lista powiązana, kolejka, stos i inne które mogą się przydać)

tablica = array, lista = list, kolejka = queue, stos = stack. Wpisujesz w Google python [angielska nazwa struktury danych] i w odpowiedzi masz setki artykułów opisujących jak to działa. Ew. wpisuj po prostu samą angielską nazwę i implementuj na własną rękę (w celach naukowych). - Patryk27 2018-12-19 08:26
[ ] to tablica, czy lista? - Gymard 2018-12-19 08:27
Wielkie dzięki. Mam jeszcze jedno pytanie: Czytałem że list powiązanych nie można indeksować np. list_variable[4], ponieważ w każdej komórce pamięci umieszczony jest adres następnej,a komórki nie znajdują się w pobliżu siebie. Dlaczego w Pythonie można to zrobić? - Gymard 2018-12-19 08:44
lista w znaczeniu lista jednokierunkowa nie jest tym samym, co lista w Pythonie - w przypadku Pythona lista jest odpowiednikiem tablicy (z nieco inny zachowaniem, tak jak zostało opisane w tamtym artykule). Wracając jednak do list jednokierunkowych: jak najbardziej można je indeksować (czy też "iterować po nich") - nie zawsze jest to jednak tak wydajne, jak w przypadku tablic, gdyż dostęp do dowolnego elementu tablicy następuje w czasie O(1), podczas gdy w przypadku listy jedno/dwukierunkowej mowa o pesymistycznym czasie O(n). - Patryk27 2018-12-19 08:49
Btw, jeśli masz jakieś dalsze pytania, umieszczaj je w postach - komentarze służą do dyskusji poza głównym wątkiem. - Patryk27 2018-12-19 08:49

Pozostało 580 znaków

2018-12-19 08:57
młody kot
1

A ja dam taki inny przykład. Bo w tamtym nie da się wykonać ostatniego przypadku z dzieleniem z przyczyn logicznych ale może nie widocznych w znacznym stopniu.
Drugra sprawa zwróć uwagę w jakim pythonie szukasz odpowiedzie 2.7 czy 3.x tak na przyszłość.

from numpy import array

dynamic_variable = 'testtt'
print('As a %s %s' % ('string', dynamic_variable))
dynamic_variable = 111
print('As a %s %s' % ('number', dynamic_variable))
dynamic_variable = array([3, 6, 9, 12])
print('As a %s %s' % ('array', dynamic_variable))
dynamic_variable = dynamic_variable * 3
print('As a %s %s' % ('array * 3', dynamic_variable))
dynamic_variable = [3, 6, 9, 12]
print('As a %s %s' % ('list', dynamic_variable))
dynamic_variable = dynamic_variable * 3
print('As a %s %s' % ('list * 3', dynamic_variable))

output

Pozostało 580 znaków

2018-12-19 09:58

Za dawnych czasów mojej dawno zapomnianej młodości, było takie rozróżnienie -- implementacja (reprezentacja) a interfejs (sposób/protokół dostępu). I wtedy słowa "lista" (było ich wiele "lista jednokierunkowa", "lista dwukierunkowa", "lista cykliczna"...) oraz "tablica" mówiły o tym, jak coś jest zaimplementowane. Natomiast słowa "stos" i "kolejka" oznaczały sposób dostępu czyli interfejs...

Wtedy:

  • "Tablica" oznaczała taką reprezentację danych w pamięci, żeby dostęp był do każdego w czasie stałym, a więc, żeby mógł być wyliczony na podstawie indeksu. W takiej reprezentacji usuwanie lub dodawanie czegoś w środku było powolne, ale już dodawanie na końcu (lub czasem na początku) mogło być w miarę szybkie (jeśli robimy sobie zapasowe miejsce). Tak działa w C++ vector.
  • "Lista" oznaczała rozrzucone w niewiadomy sposób po pamięci pudełka, które przechowywały pojedynczą daną oraz wskaźnik (adres) na następną (lista jednokierunkowa) lub na dwie sąsiednie (lista dwukierunkowa). Dostęp oczywiście do poszczególnych elementów nie jest szybki (bo musimy chodzić po liście, żeby gdzieś dojść), ale za to dokładanie/usuwanie w miejscu, w którym jesteśmy jest szybkie. Tak działają list i forward_list w C++.
  • "Stos" oznaczał taki dostęp do danych, w którym nie mamy możliwości ich dowolnego dostawiania/usuwania/przeglądania, tylko na jednym końcu (dodajemy z tej samej strony ciągu, co usuwamy i sprawdzamy). Tak działa stack w C++ , który może być adapterem do różnych kontenerów (i wektora i listy).
  • "Kolejka" to z kolei :) taki interfejs, gdzie możemy wstawiać rzeczy tylko z jednego końca, ale usuwać i podglądać tylko z przeciwnego. Tak działa adapter queue w C++.

I (jak to wynika z powyższego i z przykładów C++), możemy mieć na przykład:

  • listową implementację stosu,
  • listową implementację kolejki,
  • tablicową implementację kolejki,
  • tablicową implementację stosu,
    i tak dalej...

A co do Pythona -- strasznie lubię ten język, ale Guido wprowadził moim zdaniem niepotrzebne zamieszanie nazywając list to, co działa właściwie jak tablica...

edytowany 1x, ostatnio: koszalek-opalek, 2018-12-19 09:58
To chyba najmniejszy problem (że lista jest zaimplementowana jako dynamiczna tablica). - lion137 2018-12-19 11:53
@lion137: Jak napisałem wyżej, to problem czysto nazewniczy -- mam tylko o to pretensję, że wprowadza trochę w błąd i już wiele miałem o to pytań (gdzie są tablice w Pythonie? czy można użyć listy zamiast tablicy? itp.). :) - koszalek-opalek 2018-12-19 13:26
Prawda, to co wszędzie jest nazywane vector w Pythonie jest listą:). Natomiast listy jako takiej nie ma, ewentualnie deque. - lion137 2018-12-19 13:38

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0