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.

Podobne artykuły

Linux Tux

przez -
1 126
  • o_O

    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.

    • Druedain

      Mam nadzieję, że autor postara się obronić swój pomysł (tym bardziej, że wątpię by był w stanie).

    • Janek

      Widac ze jestes programista z Naszej-klasy :D

    • o_O

      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).

    • Vash

      @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

    • o_O

      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).

  • Kasia Nowicka

    Nie jestem programistką, ale czytając wasze komentarze czegoś zawsze się nauczę :)

  • Vash

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

    }

  • webnull-mobile

    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.