Czy można napisać uogólnioną funkcję odwracania łańcucha, która działa dla wszystkich lokalizacji i typów ciągów?

16

Właśnie oglądałem prezentację Jona Skeeta (z Tony the Pony) z Dev-Days.

Chociaż „napisz funkcję odwrotną do łańcucha” to kodowanie wywiadu 101 - nie jestem pewien, czy tak naprawdę można napisać ogólną funkcję odwrotną do ciągu, z pewnością nie taką, która działa we wszystkich lokalizacjach i wszystkich typach ciągów.

Oprócz wykrycia, czy ciąg wejściowy to ascii, UTF8, UTF16 (stała i zmienna długość) itp.
Istnieje kod „zastosuj akcent do następnego znaku” (U + 0301), który Jon podkreślił. Są też ligatury, które mogą być wyświetlane lub zakodowane jako podwójne znaki.

Wydaje się, że „odwrócenie łańcucha” jest w rzeczywistości jednym z trudniejszych zadań informatycznych!

Martin Beckett
źródło
Nie, spróbuj rozwiązać problem, aby znaleźć coś o krok trudniejszego, ale prostszego do wyjaśnienia ludziom.
JB King
Będąc nietrywialnym, technicznym pytaniem, zaryzykuję stwierdzenie, że lepiej by to pasowało na StackOverflow (proszę jednak nie zamieszczać go tam ponownie, zostanie ono zautomatyzowane, jeśli wystarczająca liczba osób zagłosuje tutaj, aby je zamknąć).
Péter Török
1
Zależy od języka programowania. Na przykład w Ruby jest to tak proste, jak "stressed".reverse: p
Marcelo
Świetne pytanie filozoficzne. FWIW, Java StringBuilder dostaje Surogaci prawo, ale nie kombinatory
kdgregory
2
„Odwróć ten ciąg za pomocą Java” to dobre podchwytliwe pytanie. :)
Scott C Wilson

Odpowiedzi:

5

Tak. Jeśli otrzymamy ciąg, możemy definitywnie odwrócić każdy znak.

Problem, jak zauważa Jon, polega na tym, że odwrócenie ma sens i czy jest zgodne z językowymi i kulturowymi zasadami, znakami i kodowaniem. Woda staje się mroczna, im głębiej zejdziesz.

Jeśli wykonujesz jakiekolwiek operacje na łańcuchach w C #, używaj kultury Invariant podczas pisania i czytania, w ten sposób możesz bezpiecznie nimi manipulować. W przeciwnym razie przygotuj się na awarię tureckiego wsparcia.

ToUpper () wygląda tak niewinnie, ale jego epicka porażka czeka.

Jon Raynor
źródło
2
Drugie pytanie brzmi - do czego ktoś używa odwrotności łańcucha (oprócz wywiadu Q)? Potrzebowałem go tylko do niskopoziomowej manipulacji buforami portów I / O - i nawet wtedy prawie nigdy nie za pomocą łańcuchów
Martin Beckett
@Martin - Uzgodniony. Może program w języku angielskim do znalezienia palidromów? Nie sądzę, że użyłem tego innego niż rozwiązanie quizu.
Jon Raynor,
@Martin true. Myślę, że zrobiono to tylko ironicznie. :)
Scott C Wilson
2

Zasadniczo, gdy pytanie zostanie zadane, przyjmuje ono US-ASCII. Nie chodzi o to, aby sprawdzić znajomość Unicode (chociaż byłoby to interesujące), aby sprawdzić, czy rozumieją, jak działają wskaźniki. Zaskakująca liczba ludzi nie potrafi tego rodzaju arytmetyki wskaźników.

Scott C. Wilson
źródło
2
„Jak to by się nie powiodło z Unicode?” jest dobrym pytaniem uzupełniającym
Martin Beckett
Dobry, ale może nieco zaawansowany - w końcu „odwróć ten łańcuch na miejscu” to pytanie wstępne na rozmowę kwalifikacyjną. Prawdopodobnie nie zapytałbyś wytrawnego człowieka o coś tak prostego, chyba że byłby bardzo nieśmiały i próbowałbyś go rozgrzać.
Scott C Wilson
1

Jako pytanie do wywiadu zwykle pyta się go o techniczne częściowe wykonanie zamiany 8-bitowych elementów w miejscu, aby odwrócić ich kolejność (niezależnie od tego, jakie postacie mogą one faktycznie reprezentować).

Jednocześnie, szczególnie jeśli przeprowadzasz wywiad ze stosunkowo starszą osobą, możesz przynajmniej mieć nadzieję, że usłyszysz kilka pytań na temat specyfikacji i dokładnej formy danych wejściowych. Nawet jeśli przekierujesz je z powrotem do prostego przypadku po prostu zamiany 8-bitowych elementów, wiedząc, czy myślą one w szerszym ujęciu, niż to może być cenne.

Jeśli masz do czynienia z szerokim zakresem danych wejściowych, musisz pomyśleć o „stosie”, trochę jak o stosie sieciowym. Musisz zbudować oprogramowanie na kilku warstwach, z których każda stosuje dość specyficzny zestaw transformacji w określonej kolejności. Dzięki temu każda część transformacji jest na tyle prosta, że ​​można ją kontrolować i mieć uzasadnioną szansę na dostosowanie jej do swoich wymagań.

Przedstawię jedną z możliwości, którą uznałem za wykonalną. Jako pierwszy przyznam, że mogą być inni, którzy mają lepsze pomysły. Przynajmniej dla mnie wygląda to trochę jak brutalna inżynieria z niewielką prawdziwą elegancją.

Zwykle chcesz zacząć od konwersji dowolnej innej reprezentacji na UCS-4 (inaczej UTF-32). W tym celu zazwyczaj wolisz polegać na danych wejściowych od użytkownika niż próbować samodzielnie go zrozumieć. W niektórych przypadkach możesz być pewien, że określona sekwencja oktetów nie przestrzega reguł określonego schematu kodowania, ale rzadko (jeśli w ogóle) możesz mieć pewność, że przestrzega określonego schematu kodowania.

Następny krok jest opcjonalny. Można znormalizować dane wejściowe do jednej z czterech form normalizacji Unicode. W takim przypadku prawdopodobnie będziesz chciał zastosować transformację „NFKC”: rozkład zgodności, a następnie skład kanoniczny. Spowoduje to (tam, gdzie to możliwe) przekształcenie łączących form diakrytycznych (takich jak U + 301, o których wspomniał Jon) w pojedyncze punkty kodowe (np. „A” z „U + 301” zostanie przekonwertowane na „łaciński kapitał A z ostrym” , U + 00C1).

Następnie przechodzisz przez wszystkie znaki od początku do końca, dzieląc ciąg na rzeczywiste znaki - a jeśli (nadal) łączą znaki diakrytyczne, zachowując je ze znakami, które modyfikują. Wynikiem tego będzie zazwyczaj indeks rzeczywistych znaków w ciągu, takich jak pozycja i długość każdego z nich.

Możesz odwrócić kolejność tych kompletnych znaków, zwykle za pomocą indeksu utworzonego w poprzednim kroku.

Następnie (ponownie, opcjonalnie) stosuje się inny proces normalizacji Unicode, taki jak NFD (rozkład kanoniczny). Spowoduje to zamianę wspomnianego wcześniej „łacińskiego A z ostrym” z powrotem na dwa punkty kodowe - „łacińską wielką literę A” i „łączący ostry”. Jeśli wejście stało zawierać U + 00C1 na początek, jednak to również przekonwertować że do dwóch punktów kodowych, jak również.

Następnie kodujesz sekwencję punktów kodowych UCS-4 w pożądanym kodowaniu (UTF-8, UTF-16 itp.)

Zauważ, że kroki normalizacji Unicode mogą / zmienią liczbę punktów kodowych potrzebnych do przechowywania łańcucha, więc jeśli je uwzględnisz, nie będziesz już mógł planować dopasowania łańcucha wynikowego do oryginalnej pamięci. Oczywiście, wynikowe punkty kodowe mogą również nie odpowiadać bezpośrednio wejściowym punktom kodowym.

Jerry Coffin
źródło
Nie natknąłem się na U + 301, zanim Jon o tym nie wspomniał. Nie rozumiem, dlaczego jest potrzebny w Unicode z glifami dla wszystkich akcentowanych postaci - Wyobrażam sobie, że jest kompatybilny wstecz
Martin Beckett
@Martin: W rzeczywistości istnieje duża liczba kombinacji znaków diakrytycznych (cały zakres od U + 0300 do U + 036F, chociaż od U + 0363 do U + 036F są w najlepszym razie przestarzałe). Wstępnie skomponowane znaki są dostarczane dla niektórych z najczęstszych możliwości i łączenia znaków diakrytycznych z wszystkim innym potrzebnym.
Jerry Coffin
Zbyt dużo dodatkowego miejsca, normalizacja i konwersja. Wystarczy powtórzyć znaki i odwrócić kolejność składowych jednostek kodu w miejscu. Następnie odwróć kolejność wszystkich jednostek kodu na miejscu.
Deduplicator