string - sobre - Implementación eficiente de cadenas en Haskell

multiplos en haskell

Question

Actualmente me estoy enseñando a mí mismo Haskell, y me pregunto cuáles son las mejores prácticas al trabajar con cadenas en Haskell.

La implementación de cadena predeterminada en Haskell es una lista de Char. Esto es ineficiente para la entrada-salida de archivos, de acuerdo con Real World Haskell , ya que cada personaje se asigna por separado (supongo que esto significa que una cadena es básicamente una lista enlazada en Haskell, pero no estoy seguro).

Pero si la implementación de cadena predeterminada es ineficaz para el archivo de E / S, ¿también es ineficaz para trabajar con cadenas en la memoria? ¿Por qué o por qué no? C usa una matriz de caracteres para representar una Cadena, y asumí que esta sería la forma predeterminada de hacer las cosas en la mayoría de los idiomas.

Según lo veo, la implementación de la lista de String ocupará más memoria, ya que cada personaje requerirá sobrecarga, y también más tiempo para iterar, ya que se requerirá una desreferenciación del puntero para llegar al siguiente carácter. Pero hasta ahora me ha gustado jugar con Haskell, así que quiero creer que la implementación predeterminada es eficiente.

Answer 1

La respuesta es un poco más compleja que solo "usar cadenas de bytes perezosas".

• Las cadenas de bytes solo almacenan 8 bits por valor, mientras que String contiene caracteres Unicode reales. Por lo tanto, si desea trabajar con Unicode, debe convertir desde y hacia UTF-8 o UTF-16 todo el tiempo, lo cual es más costoso que el simple uso de cadenas. No cometa el error de asumir que su programa solo necesitará ASCII. A menos que sea solo un código descartable, un día alguien tendrá que poner un símbolo de Euro (U + 20AC) o caracteres acentuados, y su agradable implementación de la cadena de bytes se romperá irremediablemente.
• Las cadenas de bytes hacen que algunas cosas, como anteponer al comienzo de una cadena, sean más caras.

Dicho esto, si necesita rendimiento y puede representar sus datos puramente en cadenas de bytes, hágalo.

Answer 2

Las mejores prácticas para trabajar con cadenas de manera performante en Haskell son básicamente: Usar Data.ByteString / Data.ByteString.Lazy.

http://hackage.haskell.org/packages/archive/bytestring/latest/doc/html/

En cuanto a la eficacia de la implementación de cadenas por defecto va en Haskell, no lo es. Cada Char representa un punto de código Unicode, lo que significa que necesita al menos 21bits por Char .

Como una String es simplemente [Char] , es una lista vinculada de Char , significa que String s tiene una localidad de referencia pobre, y de nuevo significa que las String son bastante grandes en la memoria, como mínimo es N * (21bits + Mbits) donde N es la longitud de la cadena y M es el tamaño de un puntero (32, 64, lo que tiene) y a diferencia de muchos otros lugares donde Haskell utiliza listas donde otros idiomas pueden usar estructuras diferentes (estoy pensando específicamente en el flujo de control aquí), es mucho menos probable que String s pueda ser optimizado para bucles, etc. por el compilador.

Y mientras que un Char corresponde a un punto de código, el informe de Haskell 98 no especifica nada sobre la codificación utilizada al hacer el archivo IO, ni siquiera un valor predeterminado, y mucho menos una forma de cambiarlo. En la práctica, GHC proporciona extensiones para hacer, por ejemplo, IO binario, pero de todos modos está saliendo de la reserva en ese punto.

Incluso con operaciones como anteponer al frente de la cadena, es poco probable que una String ByteString una ByteString de ByteString en la práctica.

Answer 3

Además de String / ByteString, ahora existe la biblioteca de texto que combina lo mejor de ambos mundos: funciona con Unicode mientras está basado en ByteString internamente, por lo que obtiene cadenas rápidas y correctas.

Answer 4

La respuesta básica dada, use ByteString, es correcta. Dicho eso, todas las tres respuestas anteriores tienen imprecisiones.

Con respecto a UTF-8: si esto será un problema o no, depende completamente del tipo de procesamiento que haga con sus cadenas. Si simplemente los trata como trozos únicos de datos (que incluyen operaciones tales como concatenación, aunque no se dividen), o haciendo ciertas operaciones basadas en bytes limitados (por ejemplo, encontrar la longitud de la cadena en bytes, en lugar de la longitud en personajes), no tendrás ningún problema. Si está utilizando I18N, hay suficientes otros problemas que simplemente usar String lugar de ByteString comenzará a solucionar solo algunos de los problemas que encontrará.

El antepender bytes individuales al frente de ByteString es probablemente más costoso que hacer lo mismo con una Cadena. Sin embargo, si está haciendo mucho de esto, probablemente sea posible encontrar formas de lidiar con su problema particular que sean más baratas.

Pero el resultado final sería, para el afiche de la pregunta original: sí, las cuerdas son ineficientes en Haskell, aunque bastante prácticas. Si le preocupa la eficiencia, use ByteStrings y visualícelos como matrices de Char8 o Word8, según su finalidad (ASCII / ISO-8859-1 frente a Unicode de algún tipo, o solo datos binarios arbitrarios). En general, usa Lazy ByteStrings (donde anteponer el inicio de una cadena es realmente una operación muy rápida) a menos que sepas por qué quieres las que no son flojas (que generalmente se envuelve en una apreciación de los aspectos de rendimiento de la evaluación perezosa).

Por lo que vale, estoy construyendo un sistema de comercio automatizado completamente en Haskell, y una de las cosas que tenemos que hacer es analizar muy rápidamente un feed de datos de mercado que recibimos a través de una conexión de red. Puedo manejar la lectura y el análisis de 300 mensajes por segundo con una cantidad insignificante de CPU; en lo que respecta al manejo de estos datos, Haskell compilado por GHC se desempeña lo suficientemente cerca de C que no está cerca de ingresar a mi lista de problemas notables.