Do czego używasz odwracania łańcucha? [Zamknięte]

15

W PHP jest strrev(), w Railsach .reverse, ale większość języków nie ma funkcji odwracania łańcucha. Niektóre mają funkcje odwracania tablic, których można używać na znakach. Myślałem, że to musi być poważny niedopatrzenie, ale potem przyszło mi do głowy, do czego właściwie użyłbyś odwrotności łańcucha?

Mogę tylko myśleć, że widziałem to podczas pokazów i lekcji, aby zmienić „Hello World!” w „! dlroW olleH”.

Moje pytanie brzmi; Czy można cofnąć ciąg znaków, czy jest to całkowicie bezcelowe?

.

Uzupełnienie

Było znacznie więcej odpowiedzi, niż się spodziewałem i nie wszystkie były całkowicie akademickie. Odłożyłbym pieniądze, których nikt nie mógłby podać uzasadnionego przykładu. Nie sądziłem też, że nauczę się czegoś nowego, ale sugestia wyrażenia regularnego Marka Canlasa jest po prostu genialna i nie mogę się doczekać, aż się to sprawdzi. Dziękuje za wszystko.

mechanizm zegarowy
źródło
@clockworkgeek - jeśli poprosisz kandydata o odwrócenie łańcucha znaków w ich ulubionym języku, zdziwisz się, ilu nie wymyśliło podstawowej funkcji, o której wspomniałeś. Zatem ilu nie może wymyślić pętli, aby sami ją wdrożyć.
justkt
@ justkt - To jest zupełnie inne pytanie, które czeka, ale może być tematem TopCodera.
clockworkgeek
6
Aby wysłać wiadomość tekstową, którą można odczytać w lusterku wstecznym podczas jazdy, aby gliniarze tego nie zauważyli.
JeffO,
@ justkt - Gdybym musiał napisać iteracyjną pętlę, aby to zrobić, zaczynałbym na przeciwnych końcach zamieniając znaki, aż do osiągnięcia środka. Ale w jaki sposób zamieniasz dwie wartości? Oto po prostu najlepsza odpowiedź, jaką kiedykolwiek otrzymałem:a ^= b; b ^= a; a ^= b;
clockworkgeek
1
używam odwracania łańcuchów do odwracania łańcuchów;)
Muad'Dib

Odpowiedzi:

19

Sexegers

Czasami problemy z wyrażeniami regularnymi można łatwiej napisać, odwracając łańcuch wejściowy i rozwiązując problem w inny sposób.

Technika dzięki uprzejmości człowieka, który nauczył mnie Perla.

Sexeger na PerlMonks

Mark Canlas
źródło
Dziękuję Ci. Bardzo przydatna sztuczka pozwalająca znaleźć ostatnią rzecz. Zanotowano.
clockworkgeek
Robię to od lat. Pomaga w analizowaniu adresów e-mail.
sal
23

Cóż, to jest odpowiedź na język.

„Back in the day” Posiadałem pudełko uniksowe i miałem uporządkowany plik słownika angielskich słów, używany do sprawdzania pisowni.

Utworzyłem nowy plik, odwracając wszystkie słowa ze słownika, sortując je, a następnie odwracając. Rezultatem była lista słów posortowanych od prawej do lewej.

Więc jeśli szukałeś słowa, obok tego słowa byłyby słowa o podobnych zakończeniach. Łatwo było więc tworzyć małe wiersze!

Możesz naprawdę się zabawić, kiedy zobaczysz, co rymuje się z czym.

Mike Dunlavey
źródło
13

Jestem programistą / programistą / sysadminem od około 10 lat i nie pamiętam, aby kiedykolwiek potrzebowałem odwrócenia łańcucha w rzeczywistych sytuacjach.

Jedynym bezpośrednim przypadkiem użycia, o którym mogę myśleć, jest konwersja bazy liczbowej: naiwnie wykonana procedura zwraca ciąg odwrócony. Jednak przy odrobinie matematyki możesz z góry obliczyć potrzebną ilość miejsca, dzięki czemu możesz zacząć wypełniać bufor od końca.

zvrba
źródło
1
Możliwe, że odrobina matematyki jest droższa niż odwracanie łańcucha, więc po przeprowadzeniu testów porównawczych na swojej platformie (ARM, MIPS, x86) możesz użyć odwrotnego łańcucha. Może.
Zan Lynx,
Możesz wypełnić bufor od końca i użyć memmovedo początku po zakończeniu. Prawdopodobnie jest to tańsze niż obliczanie log (n) / log (base) do obliczenia niezbędnej liczby cyfr.
Patrick Schlüter
12
public bool IsPalindrome(string toCheck)
{
    return toCheck == toCheck.Reverse();
}
Scott Whitlock
źródło
1
Tak - faktycznie przeprowadzamy przesłuchanie podczas rozmowy kwalifikacyjnej, w ramach której kandydaci piszą sprawdzanie palindromu i większość z nich to robi. Jednakże, jak to lepiej gdy kandydaci iteracyjne od 0celu n/2i porównać znak na końcu przeciwnym.
Nicole,
@Reneesis: Możesz także: ustawić p początek łańcucha, q koniec łańcucha, while ( (*p == *q) && (p <= q) {p++; q--} return p > q;w C i innych językach wskaźnikowych.
Michael K
4
Przypuszczam, że chociaż „kontroler palindromu” nie jest szczególnie przydatny, „napisanie kontrolera palindromu” ma przynajmniej cel.
clockworkgeek
2
Podczas wywiadu poprosili mnie o odwrócenie ciągu znaków i powiedzieli: „Zapamiętaj to bez ciągu. Rverse (). Więc właśnie przekonwertowałem ciąg na tablicę znaków i zrobiłem Array.Reverse
Jack Marchetti
Jest to dość niszowe zastosowanie i ogólnie nie byłoby warte włączenia do języka / biblioteki!
Dan Diplo,
8

Wywiady

Odwracanie łańcucha (na miejscu lub nie) jest bardzo częstym pytaniem w wywiadach dla podstawowej wiedzy programistycznej. Trudno byłoby przeprowadzić wywiad z językiem pozbawionym tych wbudowanych funkcji. Kandydat musiałby coś wiedzieć. 1


1: To jest odpowiedź na język.

Josh K.
źródło
6

Widziałem sytuacje, w których aplikacja komputerowa rozmawiała z urządzeniami wbudowanymi i ciągle zmieniała endianność kolejności bajtów, a dane były przenoszone jako ciągi znaków. To tyle dla mnie.

Nie użyłbym ciągów dla tej aplikacji, ale tak właśnie było .....

Jaka jest nazwa?
źródło
+1 za tę odpowiedź. Jest to przynajmniej praktyczny przykład, chociaż ja też zrobiłbym to w inny sposób, być może wybierając prymitywne typy, które są inaczej endemiczne.
clockworkgeek
5
<span style="unicode-bidi: bidi-override; direction:rtl;">
    <?php echo strrev($emailaddress); ?>
</span>

Nie jest to najlepsze rozwiązanie do zaciemniania adresu e-mail, ponieważ po dodaniu go do schowka jest on nadal odwracany. A jeśli stanie się popularny, wkrótce zostanie wykryty przez roboty zbierające wiadomości e-mail.

Mimo to zostało zasugerowane .

Nicole
źródło
1
Najpopularniejszym zaciemnianiem w użyciu było tylko jedno zdanie w całym tym artykule ... Kodowanie jako obraz.
clockworkgeek
1
@clockworkgeek, może być popularny, ale IMHO jest najgorszym ze skutecznych rozwiązań - nie jest bardzo łatwy do wygenerowania, nie jest osadzony w HTML (szybkość, przechowywanie obrazów, obciążenie serwera), wygląda nie na miejscu, nie można go stylizować z CSS i tym samym słabym doświadczeniem użytkownika co odwracanie ciągów, konieczności zapamiętywania i przepisywania. I prawdopodobnie więcej problemów, o których nie myślę.
Nicole,
Co ciekawe, zastosowanie AT i DOT, najłatwiejszego do odkodowania dla kombajnu, okazuje się mieć niemal idealną skuteczność w zapobieganiu żniwom. Czasami uproszczenie nie jest wcale takim złym pomysłem.
Joeri Sebrechts,
5

ASCII nie jest najlepszym kodowaniem informacji genetycznej (typy podstawowe ACGT można spakować jako 2 bity). Spakuj je do szeregu długich liter, a otrzymasz 32 genetyczne „litery” na słowo. DNA można odwrócić, więc musisz sprawdzić, czy fragment DNA w obu kierunkach to odwrotne kopie sekwencji testowej. Możliwość odwrócenia upakowanego ciągu 2-bitowych ilości może być bardzo przydatna do różnego rodzaju analiz genetycznych.

Miałem jako punkt odniesienia dla agencji szpiegowskich, jak szybko można odwrócić bity na bardzo długo (właściwie bardzo długi szereg długich i długich). Oczywista metoda wymiany 2 bitów jednocześnie jest znacznie wolniejsza niż mniej oczywiste metody. Są one związane z niektórymi zgrabnymi algorytmami transpozycji macierzy na miejscu.

Tangurena: Operacja, o której mówisz, nazywa się liczbą ludności. Podobne wartości pożądane dla danych spakowanych bitowo to wiodąca i końcowa liczba zerowa. Istnieje wiele naprawdę fajnych rzeczy, które można zrobić z nieco spakowanymi danymi. Pojedyncza operacja na długim połączeniu jest równoległa do 64-kanałowej transmisji danych, więc jeśli wiesz, co robisz, możesz uzyskać niesamowitą wydajność w przypadku niektórych rodzajów obliczeń.

Omega Centauri
źródło
Ciekawy temat, jak odwróciłbyś nieco pole?
clockworkgeek
„po prostu jak odwróciłbyś pole bitowe?”
Omega Centauri,
2
Jednym z podejść jest wyszukiwanie tabeli. Możesz odwrócić bajt, używając tabeli. Więc możesz to zrobić na poszczególnych bajtach. Istnieją również sposoby na przeniesienie kilku bitów i raz ... Trochę sprytu i kompromisów (rozmiar tabeli w porównaniu do liczby operacji itp.) I możesz spróbować go dostroić.
Omega Centauri,
5

Wszystko, gdzie praca z odwróconym łańcuchem jest łatwiejsza.

Praca z liczbami całkowitymi jako ciągami jest znacznie łatwiejsza, jeśli ciągi są odwrócone. Zbudowałem kilka funkcji bibliotecznych do wykonywania obliczeń matematycznych z dużymi liczbami całkowitymi i użyłem odwrócenia łańcucha, aby uprościć funkcje arytmetyczne.

To prawda, że ​​użyłem go tylko do wykreślenia odpowiedzi na temat Project Euler, ale pierwotna przesłanka jest nadal aktualna.

Topór
źródło
+1. przy stosowaniu ciągów reprezentacji liczb odwrócona reprezentacja jest bardzo pomocna. i zwykle standardowa biblioteka będzie reprezentować liczby w normalnej kolejności.
back2dos,
3

Być może niedrogie wielojęzyczne wsparcie dla języków używających liter od prawej do lewej (takich jak arabski) zamiast od lewej do prawej. Oczywiście musisz uważać na znaki akcentujące modyfikujące właściwy znak ...

cyklop
źródło
2

Nie wiem, może ktoś ma palącą potrzebę sprawdzenia palindromu ...

Nie uważam tego za całkowicie bezużyteczne, ponieważ mogą zdarzyć się sytuacje, w których trzeba być w stanie odwrócić łańcuch.

Ciemna noc
źródło
Kolejne pytanie brzmi: kiedy kiedykolwiek musiałbyś sprawdzić palindrom w prawdziwym świecie? Znów widziałem tylko kogoś, kogo to obchodzi na lekcjach algorytmu.
clockworkgeek
jak ten na przykład: jimsabo.com/palindrome.html
Darknight
Myślę, że są prawdopodobnie inne zastosowania, ale są one specyficzne dla domeny. Na przykład, jeśli wyszukiwanie ciągów zostało zoptymalizowane pod kątem wyszukiwania do przodu i chcesz wykonać wiele wyszukiwań ostatniego wystąpienia, możesz najpierw je odwrócić. Byłaby to jednak optymalizacja i nie należy tego robić, chyba że można to udowodnić. Mógłbym wyobrazić sobie algorytm do generowania skrótu o wartości łańcucha, który chciałby użyć końca, ewentualnie odwróconego, gdyby zdarzyło się, że zapewni lepsze właściwości mieszania.
Scott Whitlock,
2

W przetwarzaniu i parsowaniu języka naturalnego czasem łatwiej jest wyszukać ciąg od końca do początku. Odwrócenie łańcucha byłoby przydatne do debugowania lub jako alternatywny sposób zapisania pętli (odwróć ciąg, a następnie zapętl indeks od 0 do n-1).

Również niektóre języki są pisane od prawej do lewej, więc można do tego użyć odwrócenia łańcucha, jeśli znajdujesz się w środowisku, które nie rozpoznaje natywnie języków LTR / RTL.

Ciąg (w niektórych językach) to tablica znaków, ale równie dobrze mogą to być wypłaty lub modyfikacje ekwipunku. W pętli poruszającej się po nich możesz wykonać pewne obliczenia, które powinny być takie same, niezależnie od kolejności ich przetwarzania. Idealnie cromulentny test jednostkowy polegałby na sprawdzeniu, czy obliczenia dotyczą tego samego w przód czy w tył. Może to być trywialnie oczywiste w przypadku dodawania, może nie w przypadku innych bardziej nieprzejrzystych operacji.

MatthewMartin
źródło
1

Dla kompilatorów?

To zabawne, ale większość symboli w języku zaczyna się od wspólnego wzorca. Nie mówię tu o notacji węgierskiej, ale jeśli pomyślisz o przestrzeni nazw / klasach, wtedy wiele symboli będzie miało wspólny przedrostek .

myproject::SomeClass::GetFoo
myproject::SomeClass::GetBar

Problem polega na tym, że podczas wyszukiwania binarnego najczęstsze prefiksy są najgorszą rzeczą, z jaką możesz się skończyć, ponieważ będziesz porównywał te prefiksy w kółko.

Z drugiej strony, jeśli spojrzysz na struny do tyłu, zobaczysz znacznie więcej entropii! A potem nagle wyszukiwanie binarne (za pomocą Trie) staje się znacznie potężniejsze!

Zawsze denerwowało mnie to, że zniekształcone nazwy C ++ (wg gcc) nie zostały odwrócone, aby pozostawić przestrzeń nazw OSTATNĄ :)

Matthieu M.
źródło
0

Od czasu do czasu przerzucam numery telefonów i określone ciągi wyszukiwania

Don
źródło
0

Jedyny raz, kiedy pamiętam, że użyłem odwrócenia łańcucha, była funkcja, którą widziałem wstecz, która używała go podczas analizowania nazw plików, aby upewnić się, że „.” znaleziona w nazwie pliku była w rzeczywistości ostatnią kropką oddzielającą nazwę pliku od rozszerzenia. tzn. parsując nazwę pliku, taką jak data.2010.12.08.dat, odwrócisz ciąg, znajdziesz pierwszą kropkę, odejmiesz tę pozycję od końca oryginalnego ciągu i weź podciąg. Nie twierdzę, że to optymalny sposób na zrobienie tego, ale tak właśnie się stało. Być może miało to miejsce w kreatorze zasilania, gdzie takie dziwne użycie funkcji było często stosowane w celu obejścia różnych nieoczywistych problemów.

Grandmaster B.
źródło
0

Jedyną prawdziwą aplikacją dla worlów, którą widziałem za pomocą strrev, było przechowywanie haseł użytkownika „nieczytelnych” w bazie danych ...

Ale pamiętam, że w C jest wzorzec do używania strrev, może wymyślę go później.


źródło