W tablicach przechowujemy listy klientów, zakupów, towaru w sklepie czy listę napisów filmowych dostępnych dla wybranego pliku. Podczas pisania aplikacji Subget natknąłem się na problem posortowania tablicy według innej tablicy czy jeszcze lepiej – wedlug wielu tablic. Problem jak każdy inny – do rozwiązania, w artykule poznacie jedną z metod sortowania bardziej skomplikowanych tablic.
Przykład będzie się opierać o prostą listę napisów filmowych, podzieloną na trzy kolumny.
Język | Tytuł | Serwis |
es | Piel que habito, La | opensubtitles.org |
pl | Borat | napiprojekt.pl |
en | Skóra w której żyję | opensubtitles.org |
pl | Borat | opensubtitles.org |
Sortowanie w tym przykładzie będzie polegać na ułożeniu listy według serwisu, a następnie według języka.
Krok #1
Pierwszym krokiem jest nadanie priorytetu poszczególnym danym w sortowanych kolumnach.
Język:
pl – 1
en – 2
es – 3
Serwis:
napiprojekt.pl – 1
opensubtitles.org – 2
Krok #2
Drugim krokiem jest połączenie priorytetów w jeden ciąg – uwaga, kolejność ma znaczenie!
| Kolumna wysokiego priorytetu | Kolumna niskiego priorytetu |
„pl” + „napiprojekt.pl” = 1 + 1 = „11”
„pl” + „opensubtitles.org” = 1 + 2 = „12”
„en” + „opensubtitles.org” = 2 + 2 = „22”
„es” + „opensubtitles.org” = 3 + 2 = „32”
Krok #3
Każdy wynik połączenia priorytetów należy zamienić na format liczbowy i dodać do tablicy, jako nowa komórka o nazwie np. „priorytet”.
Następnie należy uruchomić standardową funkcję sortującą i posortować tablicę według kolumny priorytet.
Wynik sortowania przykładowej tabelki:
Język | Tytuł | Serwis | Priorytet |
pl | Borat | napiprojekt.pl | 11 |
pl | Borat | opensubtitles.org | 12 |
en | Skóra, w której żyję | opensubtitles.org | 22 |
es | Piel que habito, La | opensubtitles.org | 32 |
Dlaczego kolejność priorytetów ma znaczenie i dlaczego nie można zsumować priorytetów jako liczb?
Zsumowanie dwóch liczb np. 1+1 będzie równe 2, przemienność matematyczna uniemożliwi uznania danej kolumny za ważniejszą.
Odwrotne połączenie kolumn daje całkowicie inny wynik przy łączeniu ciągów i 2 + 1 będzie się równać 21, a 1 + 2 = 12 – dzięki temu można posortować tablicę według kilku kolumn na raz określając jednocześnie która z kolumn jest ważniejsza. Te ważniejsze są zawsze z przodu ciągu znaków.
A co, jeśli będziesz miał 11 serwisów i 11 języków?
1 + 11 = 111
11 + 1 = 111
Więc Ogólna metoda to przemnożenie części językowej przez liczbę większą od ilości serwisów w bazie, np:
1*100 + 11 = 111
11*100 + 1 = 1101
Ale to wymusza narzucenie z góry założenia, ile może być maksymalnie różnych serwisów.
Nie łatwiej rozdzielić te wartości do osobnych kolumn? I sortować po obu z nich?
Poza tym, jeśli w bazie masz już serwis "a.com" i "c.com" z przypisanymi odpowiednio wartościami 1 i 2, to jak oznaczysz serwis "b.com"?
Sortowanie powinno odbywać się po samych danych. Bo nie jesteś w stanie tych danych "skrócić" do prostszej postaci (tu: priorytetu) zachowując jednocześnie ich unikalność i logiczne uporządkowanie.
Mam nadzieję, że autor postara się obronić swój pomysł (tym bardziej, że wątpię by był w stanie).
Widac ze jestes programista z Naszej-klasy :D
Chyba, że wcześniej wyciągasz informacje z z tej tablicy, wybierasz unikalne i sortujesz. W ten sposób tworzysz tablice, po których następuje sortowanie. Czyli tablice te są tymczasowe i niezmienne.
Ale wtedy to IMHO nadal średnie rozwiązanie.
Przedstawiasz rozwiązanie proceduralne skupiające się na algorytmie zamiast na logice. A od czego masz obiektowość?
Każdy rekord w tej tabeli to obiekt. Więc powinien mieć swoją klasę, która przechowywałaby jego dane jak język i serwis.
Następnie definiujesz prostą metodę tej klasy służącą do porównania danego obiektu z innym obiektem tego typu:
int isGreater(Rekord other&)
{
if (this.jezyk != other.jezyk)
return this.jezyk > other.jezyk;
return this.serwis > other.serwis;
}
Porównywanie stringów – to już zależy jakich stringów używasz. Zawsze można użyć zwykłych funkcji porównujących, choć fajnie, jak stringi też są obiektami z przeciążonymi operatorami, jak to jest w Qt.
Teraz zostaje wywołać metodę sortowania z użyciem tego porównania dostępną w wielu bibliotekach (np. Qt).
Albo taką metodę samemu napisać, co trudne nie jest, ale raczej nie powinno się odkrywać Ameryki na nowo, szczególnie, że lepiej się tego nie zaimplementuje (a prędzej znacznie gorzej).
@o_O
Każdy rekord w tabeli to encja, a że encja to obiekt to już inna sprawa ;-). To tak gwoli ścisłości.
A co do sortowania stringów, to nie wiem dlaczego się na nich skupiłeś, lecz one w tym przypadku nie są istotne. Istotne jest to jak dany string jest ważniejszy od drugiego, czyli ich pozycje w tabeli czy tam priorytet. W twoim kodzie jeśli założymy, ze to są int co porównujesz to można powiedzieć, że działa to ok. Pomijając ten błąd z nawiasem. Co jeszcze razi, metoda zaczyna się od if zwraca int z boolean… może w C to przejdzie ale i wygląda to nie miło.
Pozdrawiam
Fakt, z tym intem i zwracaniem boola to niedopatrzenie i nigdzie nie powinno przejść ;)
Co do porównywania stringów, to napisałem, że QString z Qt przeciąża operatory, co jest bardzo wygodne. Dla tradycyjnych nazw domen czy oznaczeń języków wystarczy, ale generalnie lepiej użyć QString::localeAwareCompare().
Oczywiście można zawsze porównywać tradycyjnie albo ręcznie.
@O_o
Zaimplementowałem algorytm tylko w Pythonie, w C/C++ go nie testowałem.
Operuję na zwykłych ciągach (str) i liczbach (int).
Nie jestem programistką, ale czytając wasze komentarze czegoś zawsze się nauczę :)
Dla takiego małego zestawu danych, takie sortowanie można przeprowadzić na baze danych. Klauzula order by jest wykonywana na końcu przez co ma dostep do aliasowanych kolumn. Zwykły case w selekcie by załatwił problem. Case by działał tak; jeśli napi.org to 1, napi.pl to 2. Analogicznie dla drugiej kolumny. na końcu tylko sortujemy po nowych kolumnach i mamy rezultat.
Natomiast jeśli nie mamy dostępu do bazy i działamy w aplikacji. To też jest łatwo.
Możemy wykorzysta enumeracje, tablice bądź listę.
Osobiście wybrałbym enumerację do przechowywania stałych, natomiast listę do przechowywania pozycji co umożliwi nam łatwą zmianę oczekiwanych kryterium. (Tablica jest analogiczna, tylko musimy dodać metodę do wyszukiwania która iteruje wszystkie elementy i zwraca pozycję jeśli znaleziona -1 w przypadku braku).
Reasumując pozycja na liście będzie określała nam priorytet.
int compare(Subbtitle self, Subbtitle other) {
if(self == other) return 0;
if(self.language.equals(other.language)) {
return serviceList.indexOf(self.service) – serviceList.indexOf(other.service);
}
return languageList.indexOf(self.language) – languageList.indexOf(other.language);
}
Dziękuję za krytykę, zapomniałem napisać o kilku rzeczach w samym artykule, ale O_o zauważył to oraz kilka innych rzeczy za co mu dziękuję.
@O_o
Niestety zapomniałem o tym napisać (śpieszyło mi się), że całość ma sortować tylko znane już elementy ponieważ dokładnie o to mi chodziło w moim projekcie Subget.