Strona używa cookies (ciasteczek). Dowiedz się więcej o celu ich używania i zmianach ustawień. Korzystając ze strony wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki.    X

Proste sortowanie tablic według wielu kolumn metodą priorytetów

Tablice w programowaniu są nośnikiem danych zdołającym przechować wszelkiego typu dane w jednym wymiarze lub w wielu wymiarach.

Metoda sortowania według priorytetu pozwala tylko i wyłącznie na sortowanie już wcześniej znanych elementów i o to właśnie nam chodzi.

W przykładzie utworzymy sobie tabelkę z listą dostępnych napisów filmowych.

Etap pierwszy

Skupimy się na sortowaniu tabelki według języka oraz serwisu hostującego napisy.
Najważniejszy będzie dla nas język ponieważ możemy oglądać film z niezsynchronizowanymi napisami mając dostępną funkcję dopasowywania napisów "w locie" (SMPlayer). Serwis hostujący będzie sprawą drugorzędną ponieważ jedne dopasowywują napisy do filmów po treści (algorytm skrótu) a drugie po prostu po nazwach gdzie jak można się domyślić te pierwsze są bardziej trafne.

Nadajemy elementom języka priorytet

Język:
pl - 1
en - 2
es - 3

Ten sam krok należy powtórzyć w przypadku drugiej kolumny - "serwis"

Serwis:
napiprojekt.pl - 1
opensubtitles.org - 2

Ustalamy która kolumna ma mieć większe znaczenie

1. Język 2. Serwis

Tak więc już wiemy, że język jest najważniejszy - zatem na liście priorytetów musi mieć on największe znaczenie.

| Język | Serwis | Priorytet |
"pl" + "napiprojekt.pl" = (1*1) + (1*2) = "12"
"pl" + "opensubtitles.org" = (1*1) + (2*2) = "14"
"en" + "opensubtitles.org" = (2*1) + (2*2) = "24"
"es" + "opensubtitles.org" = (3*1) + (2*2) = "34"

Po obliczeniu priorytetów i zamienieniu ich z ciągu znaków w typ liczbowy należy uruchomić zwykłą funkcję sortującą według kolumny priorytetu.

Algorytm wymyślony na kolanie, na pewno wiele osób go znało przede mną. Zapewne posiada wiele błędów które możecie wypisywać w komentarzach. Jednak poprawiać artykułu nie będę - stwórzcie sobie forka ;-)

Licencja: Creative Commons z uznaniem autorstwa na tych samych warunkach. Można dowolnie rozprowadzać, modyfikować, cytować i wyśmiewać się z z tekstu, zezwolenie na użycie komercyjne i niekomercyjne. 

Komentarze

0 nowych
Druedain   14 #1 09.10.2011 13:45

Sam wiesz najlepiej czemu ten algorytm nie ma prawa bytu i nie rozumiem po co to tu umieściłeś…

drobok   14 #2 09.10.2011 20:55

Sortujemy wg języka, jeśli język taki sam bierzemy pod uwagę drugi czynnik, potem następny itd. Nie ma sensu brać tego, bo wykonujesz dużo zbędnych obliczeń :)

GL1zdA   12 #3 09.10.2011 21:27

Łapanie się prawą ręką, za lewe ucho. To co ludzie chcą, to posortować kolumnami od tej z najniższym priorytetem korzystając z dowolnie wybranego stabilnego algorytmu sortowania.

  #4 09.10.2011 22:37

Banalny ten algorytm.
Równie dobrze można podczas pobierania danych ustalić wg czego i w jakiej kolejności chcemy sortować.

djfoxer   18 #5 09.10.2011 22:45

Plus, że Ci się chciało odkrywać kwadratowe koło :P Tylko nikt nie używa kwadratowych kół :P

Pigmej   5 #6 09.10.2011 23:27

heh

a teraz 'problem' 12 jezykow i 12 serwisow
pierwszy rekord: jezyk #1 serwis #6
drugi rekord: jezyk #11 serwis #1

pierwszy rekord: 1*1 + 2*6 = "112"
drugi rekord: 11*1 + 2*1 = "112"

a wystarczy... nie cudować i nie zbijać wszystkiego do stringa i trzymać priorytety (lub generować) jako listy... zadziala zawsze.


Pozatym tego rodzaju "algorytmy" to nic nowego, na przyklad w CouchDB to podstawa podstaw.

Druedain   14 #7 10.10.2011 07:53

Lubię blog webnulla i jego samego bo miałem okazję go poznać, ale tym razem autor jasno daje do zrozumienia, że tego wpisu i czytelników nie traktuje poważnie. Nie ma tu zresztą zbyt wiele miejsca na dyskusję, bo najprostszy argument, czyli ten Pigmeja wszystko wyciąga na wierzch.
W związku z tym nie mogę się nadziwić czemu ten wpis trafił na główną… Myślę, że sporo by wyjaśniało takim skonfundowanym czytelnikom jak ja kilka słów argumentacji od redakcji. System uzasadniania wrzucania na główną wpisów mógłby wnieść pewną nową jakość do tego działu serwisu. Choć pozostaje pytanie, czy o wszystkim redakcja chciała by nam mówić, patrząc na niektóre potworki jakie w zeszłym miesiącu były najbardziej komentowane (ogólne wrażenie było chyba takie, że ilość komentarzy była odwrotnie proporcjonalna do poziomu merytorycznego wpisów… A w końcu ktoś tamte wpisu na głównej umieszczał).

PS Słowa krytyki uzasadniam przede wszystkim tym, że ten wpis pojawił się niedawno na portalu osworld i użytkownicy klarownie wytknęli wtedy błędy w rozumowaniu webnullowi, więc miał on sporo czasu do namysłu.

  #8 10.10.2011 07:54

"Algorytm wymyślony na kolanie, na pewno wiele osób go znało przede mną. Zapewne posiada wiele błędów które możecie wypisywać w komentarzach. Jednak poprawiać artykułu nie będę - stwórzcie sobie forka"

przejaw skrajnej ignorancji :D, ale ok, masz dzięki mnie jeden komentarz więcej...

Ardziej   5 #9 10.10.2011 15:10

Lekka zniewaga i pogarda, ale i tak cenię webnulla za jego wiedzę :)
Chłopak zgarnął już wszystko zatem motywacja podupadła :)
PS. Czekam na ciekawostki o sieciach od Web0 :)

webnull   9 #10 10.10.2011 16:23

@Druedain | 10.10.2011 7:53
Nie oczekiwałem aby trafił na główną - patrz stopka.

webnull   9 #11 10.10.2011 16:24

@Ardziej | 10.10.2011 15:10
Przyznam, że bardzo mało wiem o programowaniu więc chętnie przyjmuję krytykę. Bowiem w niej znajduje się zawsze lepsze rozwiązanie od podanego przeze mnie ;-)

webnull   9 #12 10.10.2011 16:31

@Ardziej | 10.10.2011 15:10
Od lipca mam jakoś tak mało czasu, ale raz na tydzień postaram się coś opublikować.

Mam nadzieję pokazać jak używać Scapy czy Ptrace w Pythonie.
Ptrace może nie jest związany z sieciami, ale ostatnio mnie zainteresował.

webnull   9 #13 10.10.2011 16:32

@Druedain | 10.10.2011 7:53
PS Obstawiam, iż ten wpis nie przekroczy liczby 20 komentarzy, więcej nie potrzeba.

Druedain   14 #14 10.10.2011 17:48

W zasadzie to te słowa kierowałem do redakcji. W końcu nie jest nigdzie napisane, że wolno umieszczać tylko wpisy zasługujące na wejście na główną. Ty sam twierdzić, że nie to było Twoim celem, więc tym bardziej warto by było poznać motywację redakcji.

Druedain   14 #15 10.10.2011 17:49

Okej, mimo wszystko nie wiem po co ten wpis umieściłeś, ale kwestie głównej kierowałem tylko do redakcji ;)

webnull   9 #16 10.10.2011 21:38

@Druedain | 10.10.2011 17:48
A od tak bo nie miałem czasu aby wymyślić nowy wpis tak więc przekształciłem i opublikowałem stary. Po prostu chciałem aby na moim blogu w dobreprogramy pojawił się w końcu jakiś wpis bo nic się nie pojawia u mnie od tygodni a nawet miesięcy...

Druedain   14 #17 11.10.2011 01:22

Liczy się jakość, a nie ilość. To nie jest pusty frazes, a ten wpis jest tego najlepszym przykładem i powiem Ci dlaczego. Do tej pory wrzucałeś tutaj różne rzeczy: niektóre wpisy były bardzo interesujące, były wpisy bardzo treściwe, ale idee, które chciałeś przekazać opierałeś na urojonych prawdach, co kończyło się tragicznie, były też parówki… Do tej pory jednak zawsze te wpisy trzymały pewien poziom i skojarzenia z Twoim tutejszym blogiem były jednoznaczne. Nie wiem z czego to wynika, ale źródeł popularności tego bloga doszukujesz się w ilości wpisów (która jak wiadomo nie jest mała). Żeby więc utrzymać ten poziom, w Twoim mniemaniu, cały czas powinny pojawiać się nowe wpisy. W ten o to sposób, kiedy okazało się, że zwyczajnie nie masz czasu na nowy sensowny wpis, postanowiłeś podtrzymać tę świecką tradycję publikując kolejny wpis MIMO WSZYSTKO. Pomijam teraz kwestię tego, że to jest odgrzewany kotlet, bo go na osworld umieściłeś, bo przede wszystkim problemem jest to, że te wpis jest szkicem jakiegoś algorytmu. Wpis jest dość miałki, a algorytm praktycznie prawie bezużyteczny.

Myślę, że nie będę jedyną osobą, która zapamięta ten wpis – fatalny wpis i to na blogu webnulla. Mam teraz wręcz wrażenie, że nie tylko wydaje się nieuzasadnione wrzucenie tego wpisu na główną, ale wręcz redakcja Ci zrobiła szkodę wyróżniając go tak samo jak poprzednie – co najmniej trochę lepsze – Twoje wpisy.

Na szczęście rzeczą ludzką jest błądzić, a rozumienie popełnianych błędów pozwala się rozwijać. Oczywiście to jest mój punkt widzenia i można uznać, że w wielu rzeczach się pomyliłem, jednak nie ja jeden dostrzegam pewien problem z tym wpisem, a – możesz mi wierzyć! – wiele podjętych przez Ciebie tematów również mógłbym podjąć i jestem pewny, że mógłbym je nawet lepiej opisać, ale nie pozwala mi na to poczucie przyzwoitości.

Abstrahując od przyczyn stworzenia tego wpisu, wciąż mam nadzieję na poznanie opinii redakcji…

eth0   4 #18 11.10.2011 18:23

@webnull

"A od tak bo nie miałem czasu aby wymyślić nowy wpis tak więc przekształciłem i opublikowałem stary."

Ja jak nie mam czasu na coś to tego nie robię:)

Pigmej   5 #19 11.10.2011 20:15

@eth0

Ale niestety niektórzy robią inaczej jak widać (to nie tylko do Ciebie webnull)

Algorytm tego typu to jest generalnie fajny 'przykład' braku myślenia w przód przy pisaniu czegokolwiek. Zakładam że w twoim serwisie nie ma po prostu nie dojdzie do opisanej przeze mnie sytuacji etc. Dlatego publikując wpisy warto pisać o założeniach poczatkowych pomyslu.

Skoro publikujesz wpis 'sortowanie tablic wedlug wielu kolumn metoda priorytetow' to odpowiedz brzmi: "Ten algorytm jest do bani" (ale lepszy niz twoj poprzedni algorytm) i wprowadza więcej problemów niż rozwiązuje.

Jeśli SQL to po prostu 'nawet podzapytanie zadziała' i posortujesz potem po róznych kolumnach
Jeśli NoSQL (jak na przykład CouchDB) to po prostu
"emit([1,2,3],null);" itp
Jeśli dajmy na to python to:

->> print l
[[1, 2, 3], [1, 3, 3], [1, 4, 3], [2, 2, 2], [2, 2, 3], [1, 1, 7], [1, 1, 6]]
->> print sorted(l)
[[1, 1, 6], [1, 1, 7], [1, 2, 3], [1, 3, 3], [1, 4, 3], [2, 2, 2], [2, 2, 3]]
->>

I koniec problemu...

Ardziej   5 #20 15.10.2011 20:52

webnull, stety niestety nie da rady być od wszystkiego :D
Albo, albo :)
Czekam!
Pozdrawiam

webnull   9 #21 16.10.2011 13:29

@Ardziej | 15.10.2011 20:52
Dzięki - znajdę dla Ciebie czas na tygodniu :-)

Ryan   15 #22 04.11.2011 09:44

Algorytm dobrze znany, przeważnie używa się go do kodowania wielu informacji na zbiorze bitów słowa lub dłuższej wartości. Opisany m.in. przez Humusa do sortowania wierzchołków w rendererze w celu zminimalizowania zmian stanów.

No i w notacji nie używałbym znaku plusa, jeśli "sklejasz" wartości, bo to może wprowadzać w błąd. ;)