24 maj 23:19
24 maj 23:28
fil:
Tak bym przykladowo rozbil pierwsza klase. Nie mam gwarancji ze bedzie dawac taki sam efekt jak
pierwotnie. Jednak aby dokladnie do zrobic trzeba miec dobra znajomosci C# (ktorej az tak nie
posiadam).
namespace DoublyLinkedList {
template<typename T>
class Link {
private:
T Data;
Link<T>* Next;
Link<T>* Previous;
public:
T getData() const {
return Data;
}
void setData(T value) {
Data = value;
}
Link<T>* getNext() const {
return Next;
}
void setNext(Link<T>* value) {
Next = value;
}
Link<T>* getPrevious() const {
return Previous;
}
void setPrevious(Link<T>* value) {
Previous = value;
}
Link() {
setNext(nullptr);
setPrevious(nullptr);
}
Link(T d)
{
setData(d);
setNext(nullptr);
setPrevious(nullptr);
}
void DisplayLink() {
std::wcout << getData().ToString() << L" ";
}
int CompareTo(Link<T>* other) {
return getData().CompareTo(other−>getData());
}
int CompareTo(T other) override {
return getData().CompareTo(other);
}
};
}
25 maj 09:02
fil: Widze ze druga jest spora, wiec moze w partiach by sie to udalo jakos przerobic
25 maj 09:03
fil: Mozesz ten online poszukac konwerterow z C# na C++ − moga nie dzialac w 100% ale moga
nakierowac
25 maj 09:11
fil:
Co do 7 linijki z linku ktory wyslales:
"where T : IComparable<T>"
Nie jestem pewny, ale mozna to zapisyc chyba jako:
https://pastebin.com/DC2QPzcP
25 maj 09:21
Mariusz:
Ja na początku myślałem o utworzeniu klasy komparatora z której można byłoby
dziedziczyć i zastępowałaby interfejs IComparable
ale nie wiem czy to byłby dobry pomysł
W szkole miałem Javę a nie C# a ta wersja listy powstała na podstawie
listy którą znalazłem w Javie (ta w Javie przechowywała dane typu long int)
oraz tego co znalazłem na anglojęzycznych forach
Tutaj funkcja wstawiająca do listy uporządkowanej nie jest zoptymalizowana
brakuje wstawiania węzła przed elementem o danym kluczu
oraz brakuje sortowania
25 maj 11:40
fil: Dokladnie, oraz metody wydaja sie krotkie. Mozna tez poszukac implementacji w cpp (na pewno sa)
i laczyc wersje c# i cpp w jedna calosc.
Moja propozycja przykladowo na metoda insertFirst() −−− nie wiem czy poprawna
void insertFirst(T element) {
Link<T>* newitem = new Link<T>;
newitem−>Data = element;
if (top == null) {
top = newitem;
newitem−>Previous = NULL;
newitem−>Data = element;
newitem−>Next = NULL;
tail = newitem;
} else {
newitem−>Previous = tail;
tail−>Next = newitem;
newitem−>Next = NULL;
tail = newitem;
}
}
25 maj 12:03
fil: Przy okazji, jak bys napisal sortowanie?
25 maj 12:07
25 maj 12:11
Mariusz:
fil to zależy od tego jakiego algorytmu sortującego chcesz użyć
np w C#
takie coś powinno działać
public void QuickSort(ref Link<T> head, ref Link<T> tail)
{
Link<T> lowf, lowl;
Link<T> midf, midl;
Link<T> highf, highl;
Link<T> pivot;
Link<T> y;
if (head != tail)
{
//Podlisty na które rozdzielana jest oryginalna lista są początkowo puste
lowf = null; lowl = null;
midf = null; midl = null;
highf = null; highl = null;
//Wybieramy element rozdzielający − najszybszy dostęp mamy do głowy i do ogona
pivot = tail;
//Dopóki nie opróżnimy oryginalnej listy
while (head != null)
{
//zdejmujemy węzeł z głowy listy
y = head;
if (head.Next == null)
tail = null;
else
head.Next.Previous = null;
head = head.Next;
/* i wstawiamy na koniec podlisty wybranej na podstawie wyniku porównania
klucza
* zdjętego węzła z kluczem elementu rozdzielającego
*/
if (y.CompareTo(pivot) < 0)
{
y.Next = null;
if (lowf == null)
lowf = y;
else
lowl.Next = y;
y.Previous = lowl;
lowl = y;
}
else if (y.CompareTo(pivot) == 0)
{
y.Next = null;
if (midf == null)
midf = y;
else
midl.Next = y;
y.Previous = midl;
midl = y;
}
else
{
y.Next = null;
if (highf == null)
highf = y;
else
highl.Next = y;
y.Previous = highl;
highl = y;
}
}
/*Wywołujemy rekurencyjnie funkcję sortującą dla podlist
* kluczach różnych niż klucz elementu rozdzielającego
*/
QuickSort(ref lowf, ref lowl);
QuickSort(ref highf, ref highl);
//Łączymy podlisty w jedną listę − tutaj wystarczy konkatenacja
if (tail != null)
tail.Next = lowf;
else
head = lowf;
if (lowf != null)
{
lowf.Previous = tail;
tail = lowl;
}
if (tail != null)
tail.Next = midf;
else
head = midf;
if (midf != null)
{
midf.Previous = tail;
tail = midl;
}
if (tail != null)
tail.Next = highf;
else
head = highf;
if (highf != null)
{
highf.Previous = tail;
tail = highl;
}
}
First = head;
Last = tail;
}
25 maj 14:14
fil: Wlasnie sie zastanawilem czy bedzie w tym przypadku jakis optymalny algorytm sortowania
25 maj 14:27
fil: Widze ze roznie uzywaja, raz bubblesort, raz insertionsort
25 maj 14:31
Mariusz:
Dość dobrym wyborem jest sortowanie przez scalanie
Sortowanie drzewem poszukiwań binarnych daje tę samą złożoność co
sortowanie przez podział czyli tzw quick sort
tyle że można próbować użyć zrównoważonego drzewa takiego jak
Red Black Tree lub АВЛ дерево
tylko że wprowadzenie zrównoważonego drzewa może wiązać się
z koniecznością wprowadzenia dodatkowego wskaźnika do struktury węzła
Myślę że najlepiej sprawdzi się sortowanie przez scalanie
chociaż gdybyś chciał napisać wersję iteracyjną to możesz stracić
stabilność algorytmu (algorytm może nie zachowywać kolejności powtarzających się kluczy)
Widziałeś kod w wątku
https://matematykaszkolna.pl/forum/388089.html ?
25 maj 14:46
fil: Widzialem, w tym kodzie uzyles mergesorta
25 maj 17:12
fil: Probowales inne sortowania implementowac?
25 maj 17:17
Mariusz:
No jeszcze Tree Sorta
W ostatnim wpisie tam dałem propozycję usprawnienia
tego kodu merge sorta
Spróbowałbyś zmodyfikować kod tego merge sorta
25 maj 18:43
25 maj 18:58
fil: Jasne, postaram sie cos napisac na dniach, ale kiepsko u mnie z czasem bo w tym roku matura a
niektore rzeczy u mnie leza
. Przy okazji, znasz sie co nieco na placement−new?
25 maj 19:43
fil: Zlozonosc obliczeniowa mergesorta to bedzie O(nlogn)?
26 maj 10:32
fil: Patrze na twoje sortowanie z kodu z tego watku co podeslales − na pierwszy rzut oka wydaje sie
dlugie. Co prawda nie pisalem sortowania do doubly linked list. Jedynie do singly linked list
26 maj 10:38
Mariusz:
No nie wiem jak mógłbyś ten kod jeszcze skrócić
Lista dwukierunkowa posiada także wskaźniki na poprzedników
więc pewnie dałoby się wyrugować jakąś zmienną lokalną
Kod będzie poprawny jak wyrzucisz tę instrukcję warunkową z funkcji sortującej
(jeśli rozdzielanie i scalanie będą wykonywane parami wtedy nie będzie problemu z destruktorami
w ostatnim wpisie z tamtego wątku masz propozycję na pewne usprawnienie tego algorytmu)
Czytałeś opis tego algorytmu
np tutaj
https://forum.pasja-informatyki.pl/219457/sortowanie-linii-w-pliku?show=224549#a224549
" Zlozonosc obliczeniowa mergesorta to bedzie O(nlogn)?"
Tak a jeśli użyjesz iteracyjnego mergesorta to będziesz miał też stałą złożoność pamięciową
bo wiadomo że rekursja wymaga pamięci
26 maj 11:12
fil: Chodzi o ten?
Przez serię w pliku będę miał na myśli uporządkowane linie − np. dla
a
b
c
x
a
h
y
jedną serią będzie a b c x, natomiast drugą a h y.
Najpierw dzielisz plik z tekstem na dwa tymczasowe pliki w następujący sposób (sortowanie
rosnące):
pobierasz z pliku pierwszą linię i zapisujesz ją do do pierwszego pliku
dopóki nie natrafisz na koniec pliku wykonaj:
pobierz linię z pliku
jeżeli jej wartość jest większa od poprzedniej, zapisujesz ją w tym samym pliku, co poprzednią
w przeciwnym zmieniasz plik docelowy na ten drugi, do którego nie zapisałeś poprzedniej linii.
Jak masz już podzielony plik na dwie części, przechodzimy do scalania. To, co trzeba zrozumieć
i zwrócić uwagę to fakt, że jak wczytujesz kolejne linie z plików pomocniczych, to
rozpoczynasz czytanie nowej serii dopiero jak skończyłeś czytać aktualnie sortowanie serie z
obu plików (przynajmniej mi zrozumienie tego przysporzyło sporo kłopotów, może tobie pójdzie
łatwiej):
pobierz z obu plików pomocniczych ich pierwsze linie;
dopóki oba pliki nie będą puste:
dopóki aktualnie sortowane serie w pliku nie są przeczytane:
wybierz linię o mniejszej wartości i wpisz ją do pliku docelowego;
z pliku, z którego pochodziła mniejsza linia pobierz kolejną linię (o ile jeszcze jakaś została
− jeżeli nie przepisujesz do pliku docelowego resztę serii z drugiego pliku i zaczynasz
wracasz do głównej pętli);
pobierz z obu plików nowe linie
Obie te fazy powtarzasz tak długo, aż podczas fazy podziału cała zawartość pliku źródłowego
została przepisana tylko do jednego pliku pomocniczego − to znaczy, że masz tylko jedną serię
i plik jest posortowany. Co prawda warunek nie jest do końca zogdny z teoretycznimi
założeniami algorytmu, ale co działa
26 maj 23:58
27 maj 00:00
Mariusz:
Tak to o ten chodzi
Ja przystosowałem ten algorytm do sortowania list
bo on pokazał mi go jako algorytm sortowania plików
Zdaje się że go widziałem
Napisz mi czy rozumiesz jak działa ten algorytm
27 maj 00:36