Sortowanie dla ludzi - naturalna kolejność sortowania

Oryginalny post: Sorting for Humans : Natural Sort Order

Autor: Jeff Atwood

Domyślne funkcje sortowania w niemal każdym języku programowania są słabo dopasowane do ludzkich potrzeb. Co przez to rozumiem? Cóż, rozważ różnice pomiędzy sortowaniem nazw plików w Eksploratorze Windows, a sortowaniem tych nazw poprzez kod Array.Sort():

Sortowanie Eksploratora Array.Sort()
sortowanie alfabetyczne sortowanie ASCIIbetyczne

Niemała różnica.

Bez przesady mogę powiedzieć, że dokładnie ten problem był czułym punktem każdego projektu, nad którym pracowałem. Użytkownicy ciągle będą narzekać, że ich elementy nie sortują się poprawnie i będą zgłaszać bugi związane z tymi "błędami". Jako iż jesteśmy członkami klubu homo logicus, my programiści, wzdychamy ze znużenia, staramy się trzymać w ryzach wywracanie oczami z oczywistości podczas, gdy cierpliwie informujemy naszych użytkowników, że to nie jest błąd. Elementy sortowane w prawidłowej kolejności. W sensie, prawidłowiej kolejności według ASCII. Miejmy nadzieję, że jak odchodzimy, nie będziesz nas słyszał, jak mamroczemy pod nosem to, co aktualnie myślimy &mdash "Głupi użytkownicy! Nie rozumieją nawet, jak działa sortowanie!"

Zawsze czułem ukłucie żalu, gdy odrzucałem takie zgłoszenia. Szczerze, spójrz na te dwie listy — jaka osoba o zdrowym umyśle chciałaby kolejność według ASCII? Jest to zupełnie bezsensowny porządek dla każdego, kto nie ma zakodowanej tablicy ASCII w umyśle (a tak przy okazji, duże A, to 65). Niemal nigdy nie rozumiałem, że może być inny rodzaj sortowania nawet, gdy sortowanie naturalne, było tuż przed naszymi oczami pod postacią Mac Findera, czy listy plików w Eksploratorze Windows. Miałem nałożone językowe klapki na oczach. Jeśli wbudowana funkcja sort zwracała w porządku ASCII, to musiało to być poprawne. Zostawili to nam w spadku Bogowie Językowi. Czy może być inny sposób?

Kate Rhodes jest lekko oburzona naszą ogólną ignorancją problemu "ASCIIbetycznie kontra Alfabetycznie". Nie mogę powiedzieć, że ją obwiniam. Jestem tak samo winny, jak każdy inny. Okazuje się, że to nie użytkownicy byli głupi &mdash ja byłem.

Niech mnie, liczyłem na to, iż skoro sortowanie alfabetyczne było tak powszechną potrzebą (a sądząc po liczbie ludzi pytających, jak to zrobić, nie mylę się), to nie będę musiał do licha nic pisać. Ale nie zdawałem sobie sprawy z głupiego czynnika. Jezu Chryste. Jesteście programistami. Niemal wszyscy jesteście po studiach i nikt z Was nie wie, co do k***y znaczy "alfabetycznie". Powinno być Wam wstyd. Jeśli ktokolwiek z Was używa domyślnego algorytmu sortowania w swoim języku, który niemal na pewno jest ASCIIbetyczny (z konkretnych powodów), aby zaimplementować sortowanie alfabetyczne, niech uda się przed najbliższe lustro i uderzy kilkakrotnie w twarz przed tym, jak powróci do swojego biurka i naprawi testy jednostkowe, które nie wyłapały tego problemu.

Nie nazywa się to "sortowanie alfabetyczne"; bardziej znane jest jako sortowanie naturalne. Ale ma ona rację, co do jednej rzeczy: trudno jest znaleźć informacje na temat sortowania naturalnego i wielu programistów całkowicie ignoruje ten problem. Żaden z popularnych języków programowania (które znam) nie implementuje niczego innego, niż sortowanie ASCIIbetyczne. Jednakże, istnieje trochę miejsc, gdzie znajdziemy algorytmy sortowania naturalnego:

Nie pozwól na to, aby pythonowy dzięsięciolinijkowiec Neda Cię ogłupił. Zaimplementowanie sortowania naturalnego jest trudniejsze, niż się wydaje i nie chodzi tylko o fajne problemy związane z i18n, o których wspominałem powyżej. Ale implementacje w Pythonie są imponująco zwięzłe. Jeden z komentatorów Neda podesłał swoją wersję, która jest jeszcze krótsza:

    import re 

    def sort_nicely( l ): 
      """ Sort the given list in the way that humans expect. 
      """ 
      convert = lambda text: int(text) if text.isdigit() else text 
      alphanum_key = lambda key: [ convert(c) for c in re.split('([0-9]+)', key) ] 
      l.sort( key=alphanum_key ) 
  

Próbowałem dojść do jakiejś sprytnej, zwięzłej implementacji sortowania naturalnego w C# 3.0, ale bez powodzenia. Nie interesuje mnie żaden jednolinijkowiec, ale wydaje mi się, iż podstawowy algorytm sortowania naturalnego nie powinien wymagać więcej niż 40 linijek kodu tak, jak w przypadku większości języków programowania.

Jako programiści, postaramy się zachować w pamięci lekcję od Kate: ASCIIbetycznie to nie to samo, co alfabetycznie. Sortowanie ASCII jest na potrzeby komputerów i kompilatorów, to co jest w takim razie dla ludzi? Być może naturalne sortowanie, bardziej przyjazne ludziom, powinno być wbudowane w najpopularniejszych językach programowania.

Data publikacji oryginału: 12 grudnia, 2007

7 komentarze:

rafek pisze...

Dla chętnych i lubiących wyzwania polecam podzielenie się tym jak napisać sortowanie naturalne w Twoim ulubionym języku programowania?

Agares pisze...

Chociaż raz PHP wygrywa: http://pl.php.net/manual/en/function.natsort.php :PP

MDW pisze...

No bo kto tak numeruje pliki? Od zawsze robiło się to tak: z001.txt, z002.txt, z003.txt, z004.txt... Takie pliki zawsze będą posortowane dobrze. :) Oczywiście trzeba przewidzieć ile tych plików będzie. To znaczy tylko rząd wielkości: dziesiątki, setki, tysiące, dziesiątki tysięcy, setki tysięcy, miliony...

To dlatego na przykład kolejne backupy nazywam z datą w kolejności odwróconej, czyli: rok, miesiąc, dzień:

dev_20110312.7z
dev_20110313.7z
dev_20110314a.7z
dev_20110314b.7z
dev_20110315.7z
dev_20110316a.7z
dev_20110316b.7z
dev_20110316c.7z
dev_20110317.7z

i pewnie dzisiaj nazwę "dev_20110318.7z". :) W ten sposób też mam pliki zawsze posortowane chronologicznie niezależnie od tego jakiego używam file managera i czy jest to pod Windows, MacOSX, MorphOS, iOS...

Tomasz Kowalczyk pisze...

W sumie faktycznie rzadko się nad tym zastanawiamy - trzeba będzie częściej pytać swoich userów o to, czy oprogramowanie działa dobrze w ich sensie. ;]

Anonimowy pisze...

nie rozumiem dlaczego te sortowanie nazywa się ASCIIbetyczne, czy to nie jest po prostu porządek leksykograficzny?

rafek pisze...

@Anonimowy - gra słów.

Anonimowy pisze...

gdyby ktoś nie zauważył to kod funkcji sort_nicely jest oczywiście z błędem... ;)

Prześlij komentarz

Related Posts with Thumbnails