_

Trochę lepsze sortowanie tekstów

Forum poświęcone flagowemu produktowi oraz aplikacjom pochodnym Autodesku. To jedyne forum mające w tytule nazwę programu, a to ze względu na jego olbrzymią popularność w Polsce. Można tutaj umieszczać również posty z ogólnie pojętej tematyki "Kreślarskie 2D".

Trochę lepsze sortowanie tekstów

Postprzez badziewiak » sty 14, 2019 21:28

Dany jest przykładowy ciąg wejściowy składający się z następujących tekstów:

Obiekt 2.1
Obiekt 222a
RG1/12a
Obiekt 1
Obiekt 10
Obiekt 2a
Obiekt 22a
RG100/12
RG1/12
34Obiekt 2
RG3/12
100Obiekt 2
20Obiekt 2
3Obiekt 2
RG25/12
5Obiekt 2

Należy posortować te teksty alfabetycznie w kierunku rosnącym, ale nie tak, jak to robią powszechnie używane programy biurowe oraz wbudowane w środowisko programistyczne funkcje sortujace:

100Obiekt 2
20Obiekt 2
34Obiekt 2
3Obiekt 2
5Obiekt 2
Obiekt 1
Obiekt 10
Obiekt 2.1
Obiekt 222a
Obiekt 22a
Obiekt 2a
RG1/12
RG1/12a
RG100/12
RG25/12
RG3/12

Takie sortowanie nie jest w pełni zadowalające. Lepsze takie, niż żadne, ale celem jest osiągnięcie takiego rezultatu:

3Obiekt 2
5Obiekt 2
20Obiekt 2
34Obiekt 2
100Obiekt 2
Obiekt 1
Obiekt 2.1
Obiekt 2a
Obiekt 10
Obiekt 22a
Obiekt 222a
RG1/12
RG1/12a
RG3/12
RG25/12
RG100/12

Pomyślałem sobie: Microsoftowe lamusy zrobiły to do sortowania plików w eksplorerze, więc ja chyba też dam radę.
Rozwiązanie problemu jest zadziwiająco proste. Ciągi wejściowe składają się z następujących typów danych: Liczby, znaki alfabetu ze spacją, separatory (znaki specjalne i inne, które nie są liczbami ani znakami alfabetu).
Należy zatem dla każdego ciągu wejściowego wykonać analizę składu. Grupy znaków tego samego rodzaju dla uproszczenia można zastąpić następującymi znakami:

maskaAlfabet = "A";
maskaLiczba = "L";

Separatory i inne paskudztwa nie będą zastępowane niczym. Będą wstawiane w swej naturalnej postaci aby zachować pierwotną strukturę ciągu wejściowego.
Jeśli dla każdego tekstu wykonamy taką maskę (właściwie to „pattern” - wzorzec jest bardziej odpowiednim słowem), to otrzymamy coś takiego:

AL
AL.L
AL/L
AL/LA
ALA
LAL

Teraz należałoby się zastanowić, co z tym można zrobić. Na pierwszy rzut oka widać, że te maski nie pasują do siebie, bo w jednej kolumnie występują dane różnych typów. Nie da się porównać znaku alfabetu z liczbą, bo to tak, jakby porównać konia z wiertarką. A gdyby pogrupować te kolumny tak, żeby do siebie pasowały?
Chodzi generalnie o to, żeby te kolumny poprzestawiać, a w miejscu, które kolumna zajmowała wcześniej, wstawić znak maski najdłuższej. Te wstawione znaki będą ignorowane, a teksty sortowane będą wstawiane w nowe miejsca zajmowane przez przestawiane kolumny. Jeśli zaś maska jest krótsza od najdłuższej kolumny, to trzeba do niej dokleić nowe kolumny pasujące do pozostałych, aby zachować całkowitą jednorodność.

Maski będą przeglądane wg kolumn od pierwszej. Nr przebiegu odpowiada numerowi kolumny.
Po pierwszym przebiegu maski wyglądają następująco:

AL.L
ALA
AL/LA
AL
AL/L
ALAL

Po drugim przebiegu nic się nie zmieniło, ba cała kolumna jest jednorodna. Po trzecim przebiegu:

AL/.L
AL/A
AL/LA
AL/
AL/L
AL/AL

Po czwartym przebiegu:

AL/L.L
AL/LA
AL/LA
AL/L
AL/L
AL/LAL

Po piątym przebiegu:

AL/L.L
AL/L.A
AL/L.A
AL/L.
AL/L.
AL/L.AL

Po szóstym przebiegu:

AL/L.AL
AL/L.A
AL/L.A
AL/L.A
AL/L.A
AL/L.AL

Po siódmym przebiegu:

AL/L.AL
AL/L.AL
AL/L.AL
AL/L.AL
AL/L.AL
AL/L.AL

I teraz uwaga: Mamy wszystkie maski całkowicie jednorodne. Gdzieś w kodzie programu mamy zapamiętane literki tych zmodyfikowanych masek, które należą do tych pierwotnych. I tak w przypadku pierwszego wiersza:

Pierwotny:
AL
i ten sam wiersz zmodyfikowany:
AL/L.AL

Wykorzystamy w nim tylko dwie pierwsze pozycje.

Wiersz kolejny:

ALA
i ten sam wiersz zmodyfikowany:
AL/L.AL

Wykorzystamy z niego pozycje 1,2,6, pozostałe będą ignorowane (musi to być zapamiętane w programie).

Cała reszta wierszy masek musi być przetworzona podobnie. Co nam teraz pozostanie? Trzeba w odpowiednie miejsca masek wstawić pogrupowane teksty z danych wejściowych. Dodatkowo tam, gdzie są same liczby, należy zamienić je na liczby binarne (czyli tekst zamienić na liczbę przykładowo double).

EDIT:
Zmieniono sposób traktowania liczb oddzielonych przecinkami jako liczby ułamkowe. Pierwotnie nie chciałem tak robić, ale w pewnych zastosowaniach jest to wręcz konieczne.

Po takim uporządkowaniu danych pozostaje tylko posortować je wg kolumn jak w arkuszu kalkulacyjnym. W lispie zdaje się jest to możliwe, tylko trzeba to sobie napisać, a ja w C# napisałem własną implementację, która tu została wykorzystana. Dodatkowo musiałem napisać własną klasę do przechowywania różnych danych, która działa mniej więcej jak Variant z VBA, aby w jednej tabeli było możliwe przechowywanie kolumn różnego typu (kalsa CVariant, którą kiedyś opublikowałem na cad.pl).

Ciężko mi to przełożyć z polskiego na nasze. W sobotę miałem "eureka", w niedzielę to napisałem i działa, a ja do dziś zastanawiam się, jak na to wpadłem i dlaczego dopiero teraz...
Ostatnio edytowany przez badziewiak, sty 15, 2019 11:47, edytowano w sumie 1 raz
badziewiak

WARTO WIEDZIEĆ: https://www.dropbox.com/s/qarh4io79f6okzy/IslamPowerX.pps?dl=1
Avatar użytkownika
badziewiak
 
Posty: 2293
Dołączył(a): paź 15, 2008 09:08
Lokalizacja: Chrząszczyżewoszyce powiat Łękołody :D

Re: Trochę lepsze sortowanie tekstów

Postprzez badziewiak » sty 14, 2019 22:03

W załączeniu działający przykład. Wymaga .NET 4.6.
Zaktualizowano o powyższe zmiany.
Załączniki
TrocheLepszeSortowanieTekstow.zip
(9.03 KiB) Pobrane 5 razy
Ostatnio edytowany przez badziewiak sty 15, 2019 12:50, edytowano w sumie 2 razy
badziewiak

WARTO WIEDZIEĆ: https://www.dropbox.com/s/qarh4io79f6okzy/IslamPowerX.pps?dl=1
Avatar użytkownika
badziewiak
 
Posty: 2293
Dołączył(a): paź 15, 2008 09:08
Lokalizacja: Chrząszczyżewoszyce powiat Łękołody :D

Re: Trochę lepsze sortowanie tekstów

Postprzez asa » sty 17, 2019 10:27

W lispie Badziewiaku trzeba by że 3 lambdy z mapcarami zastosować w 2 linijakch kodu i po sprawie. Owszem można powiedzieć że nawiaśnik to dinozaur, ale tam gdzie są listy jest niezastapony.
Powiem Ci że jak miałem krótka przygodę z C# to płakałem z bulu... W lispach nie myślisz nad tym co jest argumentem a co jest funkcją i czy funkcją może być argumentem...... poprostu działasz.
Pozdrawiam ciepło
Asa
P.S.
Dawno się nie "spierali" w sprawach naszych zabawek. Może jeszcze kiedyś znajdę czas by pobawić
się tym Twoim Net ;-)
Wszystkich przepraszam za jakieś literówki ale mobilne urządzenia mi nie służą. Lisp dinozaur ja chyba też trsozke
asa
 
Posty: 566
Dołączył(a): lut 18, 2007 20:01

Re: Trochę lepsze sortowanie tekstów

Postprzez badziewiak » sty 17, 2019 11:44

O, miło że się odezwałeś.
Wy macie w lispie swoje lambdy, czyli przesłanie w argumencie funkcji słów kluczowych języka, a w .NET też one są. Mało tego, są też delegaty, czyli przekazywanie nazwanej funkcji przez argument innej funkcji, co pozwala na przemielenie ogólnym algorytmem czegoś, co użytkownik sobie sprecyzuje swoimi funkcjami.
Jeśli masz ochotę (lub ktokolwiek inny) pobawić się w tym temacie, to zapraszam :) Mój programik może posłużyć jako jakieś odniesienie do wyników działania. W razie czego służę pomocą.
badziewiak

WARTO WIEDZIEĆ: https://www.dropbox.com/s/qarh4io79f6okzy/IslamPowerX.pps?dl=1
Avatar użytkownika
badziewiak
 
Posty: 2293
Dołączył(a): paź 15, 2008 09:08
Lokalizacja: Chrząszczyżewoszyce powiat Łękołody :D

Re: Trochę lepsze sortowanie tekstów

Postprzez asa » sty 17, 2019 13:34

badziewiak napisał(a):O, miło że się odezwałeś.
Wy macie w lispie swoje lambdy, czyli przesłanie w argumencie funkcji słów kluczowych języka, a w .NET też one są. Mało tego, są też delegaty, czyli przekazywanie nazwanej funkcji przez argument innej funkcji, co pozwala na przemielenie ogólnym algorytmem czegoś, co użytkownik sobie sprecyzuje swoimi funkcjami.
Jeśli masz ochotę (lub ktokolwiek inny) pobawić się w tym temacie, to zapraszam :) Mój programik może posłużyć jako jakieś odniesienie do wyników działania. W razie czego służę pomocą.

Może Badziewiaku coś na zasadzie "jak zacząć" byś stworzył przy odrobinie czasu ? Wiem, że większość z nas coś tu się udziela na zasadzie pro bono publico i ma to swoje ograniczenia, ale starajmy się tego nie zmieniać, choć czasy mamy takie jakie mamy ;)
Pozdrawiam ciepło
Asa
P.S.
Master, Master ... będę śpiewać jak za szczenięcych lat ;)
asa
 
Posty: 566
Dołączył(a): lut 18, 2007 20:01

Re: Trochę lepsze sortowanie tekstów

Postprzez badziewiak » sty 17, 2019 14:28

Najpierw musisz sobie odpowiedzieć na pytanie, czy w lispie jest możliwość zamiany literek oddzielonych przecinkami na liczby. Jeśli nie (co jest raczej niemożliwe), to dalsze działanie jest bezcelowe.
Zasadniczo zacząć trzeba tak, jak napisałem na początku wywodu. Przydadzą się wyrażenia regularne (regular expressions), które pomogą sprawnie wyłapać znaki alfabetu i spację z uwzględnieniem polskich znaków.
Trzeba każdy ciąg wejściowy przemaglować od początku do końca. Sprawdzasz, czy znak jest cyfrą - wyrażenie \d (w pierwszej kolejności!), następnie czy jest alfabetem (wyrażenie \w). Jeśli ani jedno, ani drugie, to jest to separator.
Jeśli typ znaku zmienił się w stos. do poprzedniego, to wszystkie poprzednie znaki poprzedniego typu gromadzisz w odrębnej liscie (w c# też są listy :D), nazwijmy ją Z, a następnie przypisujesz jej odpowiednią literkę (n.p. A jeśli to alfabet, L jeśli to liczba, coś innego jeśli to coś innego, byle dokładnie to, co tam jest) i robisz jak poprzednio dla kolejnych znaków tego samego typu.
Te literki utworzą konkretną maskę. Niech ma formę zwykłego string-a, aby można było łatwiej wyszukiwać określone sekwencje. Niech się nazywa M.
Do tego dla każdej maski robisz drugą, odrębną listę, która, podobnie jak ta z oddzielonymi znakami, będzie skojarzona z maską. Zawartość listy to [0,1,2,3...n], gdzie n to długość maski minus 1. Spełnia ona funkcję pozycji literek w pierwotnej masce i jest tu bardzo ważna. Nazwijmy ją P jak pozycje.
Teraz w masce musisz znaleźć sekwencję L,L, zastąpić ją przez L i musisz skomasować listy z pogrupowanymi znakami wejściowymi odpowiadające tym literkom, nazwane Z oraz ponownie utworzyć listę z pozycjami literek w masce, nazwaną P. Tak zmodyfikowaną maskę i odpowiadające jej listy Z i P nadpisujesz tym, co teraz zrobiłeś. Ma to na celu wyłapanie liczb dziesiętnych, aby było łatwiej sortować.
Teraz jak już masz utworzoną maskę i listę z pozycjami, to gromadzisz te maski tak, aby się nie powtarzały (ja to robię w mojej implementacji kontenera Multimap, ale można zastąpić to listą zawierającą inne listy). Jest tylko jeden szczegół: Pojedyncza maska musi wskazywać na listę, której wiersze tworzą powyższe listy pogrupowanych znaków oraz lista z pozycjami. Dzięki temu dla konkretnej maski możesz wyciągnąć wszystkie teksty wejściowe odpowiadające danej masce.
Tak więc struktura danych powinna wyglądać tak:
Kod: Zaznacz cały
[M,M,M]
 | | |
 | | |---[Z,P]
 | | |---[...]
 | | |---[Z,P]
 | |
 | |---[Z,P]
 | |---[...]
 | |---[Z,P]
 |
 |---[Z,P]
 |---[...]
 |---[Z,P]

gdzie:
Kod: Zaznacz cały
[M,M,M]
to lista masek, a każda z tych masek wskazuje na listę z pogrupowanym znakami wejściowymi i ich pozycjami w masce
Gdy to zakończysz, to przejdziemy dalej.
badziewiak

WARTO WIEDZIEĆ: https://www.dropbox.com/s/qarh4io79f6okzy/IslamPowerX.pps?dl=1
Avatar użytkownika
badziewiak
 
Posty: 2293
Dołączył(a): paź 15, 2008 09:08
Lokalizacja: Chrząszczyżewoszyce powiat Łękołody :D

Re: Trochę lepsze sortowanie tekstów

Postprzez badziewiak » sty 17, 2019 16:14

@Asa
Jeśli chcesz, by sortowanie zwracało listę pozycji, wg których należy czytać dane wejściowe, to należy zmodyfikować strukturę danych następująco:
Kod: Zaznacz cały
[M,M,M]
 | | |
 | | |---[Z,P,W]
 | | |---[...]
 | | |---[Z,P,W]
 | |
 | |---[Z,P,W]
 | |---[...]
 | |---[Z,P,W]
 |
 |---[Z,P,W]
 |---[...]
 |---[Z,P,W]

gdzie W to nr pozycji w liście wejściowej. Umożliwi odtworzenie pierwotnej kolejności wprowadzonych danych. Ja mam tak zrobione i dzięki temu z dowolnie złożonej struktury danych czytam teksty wejściowe, a po posortowaniu jestem w stanie pobrać te same dane we właściwej kolejności i dalej obrabiać. Tylko uwaga: Procedura sortowania także powinna umożliwić zwrócenie listy kolejności czytania danych - jest to do przemyślenia. Jeśli będzie taka potrzeba, będziemy o tym dyskutować.
badziewiak

WARTO WIEDZIEĆ: https://www.dropbox.com/s/qarh4io79f6okzy/IslamPowerX.pps?dl=1
Avatar użytkownika
badziewiak
 
Posty: 2293
Dołączył(a): paź 15, 2008 09:08
Lokalizacja: Chrząszczyżewoszyce powiat Łękołody :D

Re: Trochę lepsze sortowanie tekstów

Postprzez asa » sty 17, 2019 17:53

badziewiak napisał(a):@Asa
Jeśli chcesz, by sortowanie zwracało listę pozycji, wg których należy czytać dane wejściowe, to należy zmodyfikować strukturę danych następująco:
Kod: Zaznacz cały
[M,M,M]
 | | |
 | | |---[Z,P,W]
 | | |---[...]
 | | |---[Z,P,W]
 | |
 | |---[Z,P,W]
 | |---[...]
 | |---[Z,P,W]
 |
 |---[Z,P,W]
 |---[...]
 |---[Z,P,W]

gdzie W to nr pozycji w liście wejściowej. Umożliwi odtworzenie pierwotnej kolejności wprowadzonych danych. Ja mam tak zrobione i dzięki temu z dowolnie złożonej struktury danych czytam teksty wejściowe, a po posortowaniu jestem w stanie pobrać te same dane we właściwej kolejności i dalej obrabiać. Tylko uwaga: Procedura sortowania także powinna umożliwić zwrócenie listy kolejności czytania danych - jest to do przemyślenia. Jeśli będzie taka potrzeba, będziemy o tym dyskutować.

Badziewiaku jak najbardziej lisp wyrabia w zakresie tego co przedstawiłeś powyżej. Przy odrobinie czasu spróbuje to "zalispować" w.g. Twojego algorytmu.
Pozdrawiam ciepło i jadę coś zjeść
Asa
P.S.
Widzę że pozyskałeś adoratora ;) Jak trzeba to mu mogę wysłać torebkę tinki minki co by był bardziej atrakcyjny ;). Ty się pewnie nie skusisz na jego wdzięki ale kto wie... mało to w tych internetach "od" dziwnych "bytów" ?
P.S. po P.S.
Ciekawy ten Net
asa
 
Posty: 566
Dołączył(a): lut 18, 2007 20:01

Re: Trochę lepsze sortowanie tekstów

Postprzez kojacek » sty 17, 2019 22:29

1) @badziewiak: olej to.
2) @asa: też mam przeczucie że LISP-em, da się to obcykać.
Avatar użytkownika
kojacek
 
Posty: 5487
Dołączył(a): paź 03, 2005 20:17

Re: Trochę lepsze sortowanie tekstów

Postprzez badziewiak » sty 17, 2019 22:56

kojacek napisał(a):1) @badziewiak: olej to.
Olewam
kojacek napisał(a):2) @asa: też mam przeczucie że LISP-em, da się to obcykać.
Wierzę w Was!
badziewiak

WARTO WIEDZIEĆ: https://www.dropbox.com/s/qarh4io79f6okzy/IslamPowerX.pps?dl=1
Avatar użytkownika
badziewiak
 
Posty: 2293
Dołączył(a): paź 15, 2008 09:08
Lokalizacja: Chrząszczyżewoszyce powiat Łękołody :D

Następna strona

Powrót do AutoCAD

Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników