LISP - zestaw

Common Lisp nie zapewnia ustawionego typu danych. Jednak zapewnia szereg funkcji, które pozwalają na wykonywanie operacji na liście.

Możesz dodawać, usuwać i wyszukiwać elementy na liście na podstawie różnych kryteriów. Możesz również wykonywać różne operacje na zbiorach, takie jak: suma, przecięcie i różnica zestawów.

Zestawy implementacyjne w LISP

Zestawy, podobnie jak listy, są generalnie implementowane w kategoriach komórek wad. Jednak właśnie z tego powodu operacje na zbiorach stają się coraz mniej wydajne, im większe są zbiory.

Plik adjoinFunkcja pozwala na zbudowanie zestawu. Pobiera element i listę reprezentującą zestaw i zwraca listę reprezentującą zestaw zawierający element i wszystkie elementy z oryginalnego zestawu.

Plik adjoinfunkcja najpierw szuka pozycji na podanej liście, jeśli zostanie znaleziona, to zwraca oryginalną listę; w przeciwnym razie tworzy nową komórkę wad z jejcar jako element i cdr wskazuje oryginalną listę i zwraca tę nową listę.

Plik adjoin funkcja również zajmuje :key i :testargumenty słów kluczowych. Te argumenty służą do sprawdzania, czy element znajduje się na oryginalnej liście.

Ponieważ funkcja adjoin nie modyfikuje oryginalnej listy, aby dokonać zmiany w samej liście, należy albo przypisać wartość zwracaną przez adjoin do oryginalnej listy, albo użyć makra pushnew aby dodać element do zestawu.

Przykład

Utwórz nowy plik kodu źródłowego o nazwie main.lisp i wpisz w nim następujący kod.

; creating myset as an empty list
(defparameter *myset* ())
(adjoin 1 *myset*)
(adjoin 2 *myset*)

; adjoin did not change the original set
;so it remains same
(write *myset*)
(terpri)
(setf *myset* (adjoin 1 *myset*))
(setf *myset* (adjoin 2 *myset*))

;now the original set is changed
(write *myset*)
(terpri)

;adding an existing value
(pushnew 2 *myset*)

;no duplicate allowed
(write *myset*)
(terpri)

;pushing a new value
(pushnew 3 *myset*)
(write *myset*)
(terpri)

Po wykonaniu kodu zwraca następujący wynik -

NIL
(2 1)
(2 1)
(3 2 1)

Sprawdzanie członkostwa

Członkowie grupy funkcji pozwalają sprawdzić, czy element jest członkiem zestawu, czy nie.

Poniżej przedstawiono składnie tych funkcji -

member item list &key :test :test-not :key 
member-if predicate list &key :key 
member-if-not predicate list &key :key

Funkcje te przeszukują podaną listę pod kątem danej pozycji, która spełnia test. Jeśli nie zostanie znaleziony żaden taki element, funkcja zwracanil. W przeciwnym razie zwracany jest koniec listy z elementem jako pierwszym elementem.

Wyszukiwanie jest prowadzone tylko na najwyższym poziomie.

Te funkcje mogą być używane jako predykaty.

Przykład

Utwórz nowy plik kodu źródłowego o nazwie main.lisp i wpisz w nim następujący kod.

(write (member 'zara '(ayan abdul zara riyan nuha)))
(terpri)
(write (member-if #'evenp '(3 7 2 5/3 'a)))
(terpri)
(write (member-if-not #'numberp '(3 7 2 5/3 'a 'b 'c)))

Po wykonaniu kodu zwraca następujący wynik -

(ZARA RIYAN NUHA)
(2 5/3 'A)
('A 'B 'C)

Ustaw Union

Grupa sumująca funkcji umożliwia wykonanie sumy set na dwóch listach dostarczonych jako argumenty do tych funkcji na podstawie testu.

Poniżej przedstawiono składnie tych funkcji -

union list1 list2 &key :test :test-not :key 
nunion list1 list2 &key :test :test-not :key

Plik unionfunkcja przyjmuje dwie listy i zwraca nową listę zawierającą wszystkie elementy obecne na jednej z list. Jeśli występują duplikaty, tylko jedna kopia członka zostanie zachowana na liście zwróconej.

Plik nunion funkcja wykonuje tę samą operację, ale może zniszczyć listy argumentów.

Przykład

Utwórz nowy plik kodu źródłowego o nazwie main.lisp i wpisz w nim następujący kod.

(setq set1 (union '(a b c) '(c d e)))
(setq set2 (union '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
       
(setq set3 (union '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Po wykonaniu kodu zwraca następujący wynik -

(A B C D E)
(#(F H) #(5 6 7) #(A B) #(G H))
(#(A B) #(5 6 7) #(F H) #(5 6 7) #(A B) #(G H))

Proszę zanotować

Funkcja unii nie działa zgodnie z oczekiwaniami bez :test-not #'mismatchargumenty dla listy trzech wektorów. Dzieje się tak, ponieważ listy składają się z komórek wad i chociaż wartości wyglądają dla nas tak samo, rozszerzeniecdrczęść komórek nie pasuje, więc nie są one dokładnie takie same, jak interpreter / kompilator LISP. To jest powód; implementowanie dużych zbiorów nie jest zalecane przy użyciu list. Działa jednak dobrze w przypadku małych zestawów.

Ustaw przecięcie

Grupa funkcji przecięcia pozwala na wykonanie przecięcia na dwóch listach podanych jako argumenty do tych funkcji na podstawie testu.

Poniżej przedstawiono składnie tych funkcji -

intersection list1 list2 &key :test :test-not :key 
nintersection list1 list2 &key :test :test-not :key

Te funkcje przyjmują dwie listy i zwracają nową listę zawierającą wszystkie elementy obecne na obu listach argumentów. Jeśli którakolwiek z list zawiera zduplikowane wpisy, nadmiarowe wpisy mogą pojawić się w wyniku lub nie.

Przykład

Utwórz nowy plik kodu źródłowego o nazwie main.lisp i wpisz w nim następujący kod.

(setq set1 (intersection '(a b c) '(c d e)))
(setq set2 (intersection '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
       
(setq set3 (intersection '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Po wykonaniu kodu zwraca następujący wynik -

(C)
(#(A B) #(5 6 7))
NIL

Funkcja przecięcia jest destrukcyjną wersją przecięcia, tj. Może zniszczyć oryginalne listy.

Ustaw różnicę

Grupa funkcji różnica nastaw pozwala na wykonanie różnicy nastaw na dwóch listach podanych jako argumenty do tych funkcji na podstawie testu.

Poniżej przedstawiono składnie tych funkcji -

set-difference list1 list2 &key :test :test-not :key 
nset-difference list1 list2 &key :test :test-not :key

Funkcja różnicy zestawów zwraca listę elementów pierwszej listy, które nie pojawiają się na drugiej liście.

Przykład

Utwórz nowy plik kodu źródłowego o nazwie main.lisp i wpisz w nim następujący kod.

(setq set1 (set-difference '(a b c) '(c d e)))
(setq set2 (set-difference '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
(setq set3 (set-difference '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Po wykonaniu kodu zwraca następujący wynik -

(A B)
(#(F H))
(#(A B) #(5 6 7) #(F H))