¿Para qué utilizas la inversión de cuerda? [cerrado]

15

En PHP es strrev(), en Rails .reverse, pero la mayoría de los lenguajes no tienen ninguna función inversa de cadena. Algunos tienen funciones inversas de matriz que se pueden usar en los caracteres. Estaba pensando que esto debe ser un gran descuido, pero luego se me ocurrió, ¿para qué usarías realmente la secuencia inversa?

La única vez que puedo pensar que lo he visto es en demostraciones y lecciones para convertir "Hello World!" en "! dlroW olleH".

Mi pregunta es; ¿Hay algún uso para invertir una cadena o es completamente inútil?

.

Apéndice

Hubo muchas más respuestas que había previsto y no todas fueron completamente académicas. Hubiera puesto dinero para que nadie pudiera dar un ejemplo legítimo. Tampoco pensé que aprendería algo nuevo, pero la sugerencia de expresiones regulares de Mark Canlas es genial y espero con ansias la oportunidad de que se pruebe. Gracias a todos.

Clockworkgeek
fuente
@clockworkgeek: si le pide a un candidato que invierta la cadena en su idioma favorito, se sorprenderá de cuántos no tienen la función básica que mencionó. Entonces, ¿cuántos no pueden crear un bucle para implementarlo ellos mismos?
justkt
@justkt: esa es otra pregunta que espera suceder, pero podría ser un tema para TopCoder.
clockworkgeek
66
Para enviar un mensaje de texto que pueda leerse en el espejo retrovisor mientras conduce, para que la policía no se dé cuenta.
JeffO
@justkt: si tuviera que escribir un bucle iterativo para hacerlo, comenzaría en los extremos opuestos intercambiando caracteres hasta llegar al medio. Pero entonces, ¿cómo intercambias dos valores? Esta es simplemente la mejor respuesta que he recibido:a ^= b; b ^= a; a ^= b;
clockworkgeek
1
Yo uso la inversión de cadena para invertir las cadenas;)
Muad'Dib

Respuestas:

19

Sexegers

A veces, los problemas que involucran expresiones regulares se pueden escribir más fácilmente invirtiendo la cadena de entrada y abordando el problema de una manera diferente.

Técnica cortesía del hombre que me enseñó Perl.

Sexeger en PerlMonks

Mark Canlas
fuente
Gracias. Un truco muy útil para encontrar lo último de algo. Debidamente anotado.
clockworkgeek
He estado haciendo esto por años. Ayuda a analizar las direcciones de correo electrónico.
sal
23

Bueno, esta es una respuesta irónica.

"En el pasado" poseía una caja de Unix, y tenía un archivo de diccionario ordenado de palabras en inglés, utilizado para la corrección ortográfica.

Hice un nuevo archivo invirtiendo todas las palabras en el diccionario, clasificándolas y luego invirtiéndolas nuevamente. El resultado fue una lista de palabras ordenadas de derecha a izquierda.

Entonces, si buscó una palabra, al lado de esa palabra habría palabras con terminaciones similares. ¡Así que fue fácil hacer pequeños poemas!

Realmente puedes divertirte cuando ves qué rima con qué.

Mike Dunlavey
fuente
13

He sido codificador / desarrollador / administrador de sistemas durante ~ 10 años y no recuerdo haber necesitado nunca la inversión de cadenas en situaciones de la vida real.

El único caso de uso inmediato que se me ocurre es la conversión de base numérica: realizada ingenuamente, el procedimiento devuelve una cadena invertida. Sin embargo, con un poco de matemática, puede calcular por adelantado la cantidad de espacio necesario, por lo que puede comenzar a llenar el búfer desde el final.

zvrba
fuente
1
Es posible que la matemática sea más costosa que invertir la cadena, por lo que después de la evaluación comparativa en su plataforma (ARM, MIPS, x86) podría usar una cadena inversa. Tal vez.
Zan Lynx
Puede llenar el búfer desde el final y usar memmovea al inicio cuando haya terminado. Probablemente sea más barato que calcular log (n) / log (base) para calcular la cantidad de dígitos necesarios.
Patrick Schlüter
12
public bool IsPalindrome(string toCheck)
{
    return toCheck == toCheck.Reverse();
}
Scott Whitlock
fuente
1
Sí, en realidad tenemos una entrevista de selección donde los candidatos escriben un corrector de palíndromo y la mayoría lo hace. Sin embargo, me gusta más cuando los candidatos de iterar 0a n/2y comparar el carácter en el extremo opuesto.
Nicole
@Renesis: También puede hacer: establecer p inicio de cadena, q final de cadena, while ( (*p == *q) && (p <= q) {p++; q--} return p > q;en C y otros lenguajes de puntero.
Michael K
44
Supongo que si bien un "verificador de palíndromo" no es especialmente útil, "escribir un verificador de palíndromo" al menos tiene un propósito.
clockworkgeek
2
En una entrevista, me pidieron que invirtiera una cadena y me dijeron "recuerda esto sin cadena. Invertir (). Así que simplemente convertí la cadena en una matriz de caracteres e hice Array
Jack Marchetti
¡Ese es un uso bastante especial y no vale la pena incluirlo en un idioma / biblioteca!
Dan Diplo
8

Entrevistas!

Invertir una cadena (en el lugar o no) es una pregunta de entrevista muy común para el conocimiento básico de programación. Sería difícil entrevistar un lenguaje que carezca de estas funciones integradas. El candidato realmente tendría que saber algo. 1


1: Esta es una respuesta irónica.

Josh K
fuente
6

He visto situaciones en las que una aplicación de escritorio hablaba con dispositivos integrados y cambiaba constantemente la resistencia de orden de bytes, y los datos se movían como cadenas. Eso es todo para mí.

No hubiera usado cadenas para esa aplicación, pero así era .....

whatsisname
fuente
+1 por esta respuesta. Es al menos un ejemplo práctico, aunque yo también lo habría hecho de otra manera, quizás eligiendo tipos primitivos que son enddian de manera diferente.
clockworkgeek
5
<span style="unicode-bidi: bidi-override; direction:rtl;">
    <?php echo strrev($emailaddress); ?>
</span>

No es la mejor solución para ofuscar una dirección de correo electrónico, ya que cuando la agrega al portapapeles todavía se invierte. Y, si se hizo popular, pronto sería detectado por bots de raspado de correo electrónico.

Aún así, ha sido sugerido .

Nicole
fuente
1
Y la ofuscación más popular en uso solo recibió una sola oración en todo ese artículo ... Codificación como imagen.
clockworkgeek
1
@clockworkgeek, puede ser popular, pero en mi humilde opinión, es la peor de las soluciones efectivas : no es muy fácil de generar, no está incrustado en HTML (velocidad, almacenamiento de imágenes, carga del servidor), parece fuera de lugar, no se puede diseñar con CSS, y la misma experiencia de usuario deficiente que la inversión de cadenas, de tener que recordarlo y volver a escribirlo. Y probablemente más problemas en los que no estoy pensando.
Nicole
Sin embargo, curiosamente, el uso de AT y DOT, el más fácil de decodificar para una cosechadora, resulta tener una efectividad casi perfecta para evitar la cosecha. A veces, mantenerlo simple no es una mala idea.
Joeri Sebrechts
5

ASCII no es la mejor codificación para la información genética (puede empaquetar los tipos base ACGT como 2 bits). Empaquételos en una variedad de longlongs y obtendrá 32 "letras" genéticas por palabra. El ADN se puede cambiar, por lo que debe verificar un fragmento de ADN contra ambos hacia adelante son copias inversas de una secuencia de prueba. Por lo tanto, ser capaz de revertir una cadena empaquetada de cantidades de 2 bits puede ser muy útil para varios tipos de análisis genéticos.

Tuve como elemento en un punto de referencia para las agencias de espionaje, qué tan rápido puede revertir los bits durante mucho tiempo (en realidad, una gran variedad de long-longs). El método obvio de intercambio de 2 bits a la vez es mucho más lento que los métodos menos obvios. Estos están relacionados con algunos de los algoritmos limpios para la transposición de matriz en el lugar.

Tangurena: La operación a la que te refieres se llama conteo de población. Deseables similares para datos empaquetados en bits son el recuento cero inicial y final. Hay muchas cosas realmente buenas que uno puede hacer con datos empaquetados en bits. Una sola operación en una larga duración es un paralelo de datos de 64 vías, por lo que si sabe lo que está haciendo, puede obtener un rendimiento increíble para ciertos tipos de cómputos.

Omega Centauri
fuente
Tema interesante, ¿cómo revertirías un campo de bits?
clockworkgeek
"¿Cómo revertirías un campo de bits?"
Omega Centauri
2
Un enfoque es la búsqueda en la tabla. Puede invertir un bit en un byte utilizando una tabla. Entonces podrías hacer eso en los bytes individuales. También hay formas de mover varios bits y una vez ... Un poco de inteligencia y compensaciones (tamaño de la tabla versus número de operaciones, etc.) y puede intentar ajustarlo.
Omega Centauri
5

Cualquier cosa donde trabajar con la cadena invertida es más fácil.

Trabajar con enteros como cadenas es mucho más fácil si las cadenas se invierten. Construí algunas funciones de biblioteca para hacer matemáticas con enteros grandes y usé la inversión de cadenas para simplificar las funciones aritméticas.

Por supuesto, solo lo he usado para obtener respuestas sobre el Proyecto Euler, pero aún así, la premisa original se mantiene.

Hacha
fuente
+1. cuando se utilizan representaciones de números en cadena, la representación inversa es muy útil. y generalmente la biblioteca estándar representará números en el orden normal.
back2dos
3

Tal vez soporte multilingüe de bajo costo, para idiomas que usan letras de derecha a izquierda (como el árabe), en lugar de izquierda a derecha. Por supuesto, debe tener cuidado con los caracteres de acento que modifican el carácter correcto ...

Cíclope
fuente
2

No sé, tal vez alguien tenga una necesidad ardiente de comprobar si hay palindrome ...

No creo que sea completamente inútil, ya que puede haber situaciones en las que uno deba poder invertir una cadena.

Noche oscura
fuente
La siguiente pregunta sería, ¿cuándo alguna vez has necesitado comprobar un palíndromo en el mundo real? De nuevo, solo he visto a alguien preocuparse por las lecciones de algoritmos.
clockworkgeek
como este, por ejemplo: jimsabo.com/palindrome.html
Darknight
Creo que probablemente hay otros usos, pero es específico del dominio. Por ejemplo, si las búsquedas de cadenas se optimizaron para la búsqueda hacia adelante y desea realizar varias búsquedas para la última aparición, es posible que desee revertirla primero. Sin embargo, esto sería una optimización y no debe hacerse a menos que haya un caso comprobable para ello. Podría imaginar un algoritmo para generar un hash de un valor de cadena que quisiera usar el final de la cola, posiblemente invertido, si proporcionara mejores características de hash.
Scott Whitlock
2

En el procesamiento y análisis del lenguaje natural, a veces es más fácil buscar una cadena desde el final hasta el principio. Una cadena inversa sería útil para la depuración, o como una forma alternativa de escribir el ciclo (invierta la cadena y luego repita desde el índice 0 a n-1).

Además, algunos idiomas se escriben de derecha a izquierda, por lo que se podría usar un inversor de cadena para eso si estuviera en un entorno que no reconociera de forma nativa los idiomas LTR / RTL.

Una cadena (en algunos idiomas) es un conjunto de caracteres, pero también podría ser cheques de pago o modificaciones de inventario. En un bucle que se mueve a través de estos, es posible que realice algunos cálculos que deberían ser los mismos independientemente del orden en que los procese. Una prueba de unidad perfectamente cromulenta sería verificar si los cálculos se aplican de la misma manera hacia adelante o hacia atrás. Esto puede ser trivialmente obvio para la adición, tal vez no para otras operaciones más opacas.

MatthewMartin
fuente
1

¿Para compiladores?

Es divertido, pero la mayoría de los símbolos en un idioma comenzarán con un patrón común. No estoy hablando de notación húngara aquí, pero si piensas en espacios de nombres / clases, muchos símbolos compartirán un prefijo común .

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

El problema es que, al hacer una búsqueda binaria, los prefijos comunes son lo peor con lo que puedes terminar, porque terminarás comparando esos prefijos una y otra vez.

Por otro lado, si observa las cuerdas hacia atrás, ¡verá mucha más entropía! ¡Y de repente una búsqueda binaria (sobre un Trie) se vuelve mucho más poderosa!

Siempre me molestó que los nombres destrozados de C ++ (por gcc) no se invirtieran para poner el espacio de nombres ÚLTIMO :)

Matthieu M.
fuente
0

Volteo los números de teléfono y ciertas cadenas de búsqueda de vez en cuando

Don
fuente
0

La única vez que recuerdo haber visto la inversión de cadenas en uso fue una función que vi hace mucho tiempo que la usaba al analizar los nombres de archivo, para asegurar que el '.' se encontró en el nombre del archivo, de hecho, fue el último punto que separó el nombre del archivo de la extensión. es decir, analizando un nombre de archivo como data.2010.12.08.dat, invertirías la cadena, encontrarías el primer punto, restarías esa posición del final de la cadena original y tomarías la subcadena. No digo que esa sea la forma óptima de hacerlo, pero eso es lo que hizo. Puede haber sido en Powerbuilder, donde tales usos extraños de funciones eran comunes para solucionar varios problemas no obvios.

Gran maestro B
fuente
0

La única aplicación de Worls real que vi usando Strrev fue almacenar las contraseñas de los usuarios 'ilegibles' en la base de datos ...

Pero puedo recordar que hay un patrón en C para usar el strrev, tal vez se me ocurra más tarde.


fuente