functional programming - resolucion - ¿Cómo se implementan las tablas hash en un lenguaje funcional?

tablas hash aplicaciones

Question

¿Hay alguna forma de implementar tablas hash de manera eficiente en un lenguaje puramente funcional? Parece que cualquier cambio en la tabla hash requeriría crear una copia de la tabla hash original. Debo estar perdiendo algo. Las tablas hash son estructuras de datos bastante importantes, y un lenguaje de programación estaría limitado sin ellas.

Answer 1

¿Hay alguna forma de implementar tablas hash de manera eficiente en un lenguaje puramente funcional?

Las tablas hash son una implementación concreta de la estructura de datos abstracta del "diccionario" o "matriz asociativa". Así que creo que realmente quieres preguntar sobre la eficacia de los diccionarios puramente funcionales en comparación con las tablas hash imperativas.

Parece que cualquier cambio en la tabla hash requeriría crear una copia de la tabla hash original.

Sí, las tablas hash son inherentemente imprescindibles y no hay un equivalente puramente funcional directo. Tal vez el tipo de diccionario puramente funcional más similar sea el hash trie pero son significativamente más lentos que las tablas hash debido a las asignaciones e indirecciones.

Debo estar perdiendo algo. Las tablas hash son estructuras de datos bastante importantes, y un lenguaje de programación estaría limitado sin ellas.

Los diccionarios son una estructura de datos muy importante (aunque vale la pena señalar que eran raros en la corriente principal hasta que Perl los hizo populares en la década de 1990, por lo que las personas codificaron cosas durante décadas sin el beneficio de los diccionarios). Estoy de acuerdo en que las tablas hash también son importantes porque a menudo son, con mucho, los diccionarios más eficientes.

Hay muchos diccionarios puramente funcionales:

• Árboles equilibrados (rojo-negro, AVL, peso equilibrado, árboles de dedos, etc.), por ejemplo, Map en OCaml y F # y Data.Map en Haskell.

• Hash trie , por ejemplo, PersistentHashMap HashMap en Clojure.

Pero estos diccionarios puramente funcionales son mucho más lentos que una tabla hash decente (por ejemplo, el Dictionary .NET).

Tenga cuidado con los bancos de pruebas de Haskell que comparan tablas hash con diccionarios puramente funcionales que afirman que los diccionarios puramente funcionales tienen un rendimiento competitivo. La conclusión correcta es que las tablas hashell de Haskell son tan ineficientes que son casi tan lentas como los diccionarios puramente funcionales. Si se compara con .NET, por ejemplo, ¡encuentra que un Dictionary .NET puede ser 26 veces más rápido que la tabla hash de Haskell !

Creo que para concluir realmente lo que está tratando de concluir sobre el desempeño de Haskell, necesitaría probar más operaciones, usar un tipo de clave no ridículo (funciona como clave, ¿qué?), No usar -N8 sin razón, y comparar a un tercer idioma que también encuadra sus tipos paramétricos, como Java (ya que Java tiene un rendimiento aceptable en la mayoría de los casos), para ver si es un problema común de boxeo o alguna falla más grave del tiempo de ejecución de GHC. Estos benchmarks están en esta línea (y ~ 2x tan rápido como la implementación actual de la tabla hash).

Este es exactamente el tipo de información errónea a la que me refería. No preste atención a las tablas hashell de Haskell en este contexto, solo mire el rendimiento de las tablas hash más rápidas (es decir, no Haskell) y los diccionarios puramente funcionales más rápidos.

Answer 2

Las tablas hash pueden implementarse con algo como la mónada ST en Haskell, que básicamente envuelve las acciones de IO en una interfaz puramente funcional. Para ello, obliga a que las acciones de IO se realicen de forma secuencial, por lo que mantiene la transparencia referencial: no se puede acceder a la "versión" anterior de la tabla hash.

Ver: hackage.haskell.org/package/hashtables

Answer 3

Todas las respuestas existentes tienen buenos puntos para compartir, y pensé que solo agregaría un dato más a la ecuación: comparar el desempeño de unas pocas estructuras de datos asociativos diferentes.

La prueba consiste en insertar de forma secuencial y luego buscar y agregar los elementos de la matriz. Esta prueba no es increíblemente rigurosa, y no debe tomarse como tal, solo es una indicación de qué esperar.

Primero en Java usando HashMap la implementación del Map no sincronizado:

import java.util.Map;
import java.util.HashMap;

class HashTest {
    public static void main (String[] args)
    {
        Map <Integer, Integer> map = new HashMap<Integer, Integer> ();
        int n = Integer.parseInt (args [0]);
        for (int i = 0; i < n; i++)
            {
                map.put (i, i);
            }

        int sum = 0;
        for (int i = 0; i < n; i++)
            {
                sum += map.get (i);
            }


        System.out.println ("" + sum);
    }
}

Luego, una implementación de Haskell utilizando el trabajo reciente de tablas hash realizado por Gregory Collins (está en el paquete de hashtables ). Esto puede ser puro (a través de la mónada ST ) o impuro a través de IO , estoy usando la versión IO aquí:

{-# LANGUAGE ScopedTypeVariables, BangPatterns #-}
module Main where

import Control.Monad
import qualified Data.HashTable.IO as HashTable
import System.Environment

main :: IO ()
main = do
  n <- read `fmap` head `fmap` getArgs
  ht :: HashTable.BasicHashTable Int Int <- HashTable.new
  mapM_ (/v -> HashTable.insert ht v v) [0 .. n - 1]
  x <- foldM (/ !s i -> HashTable.lookup ht i >>=
               maybe undefined (return . (s +)))
       (0 :: Int) [0 .. n - 1]
  print x

Por último, uno que utiliza la implementación HashMap inmutable de hackage (del paquete hashmap ):

module Main where

import Data.List (foldl'')
import qualified Data.HashMap as HashMap
import System.Environment

main :: IO ()
main = do
  n <- read `fmap` head `fmap` getArgs
  let
    hashmap = 
        foldl'' (/ht v -> HashMap.insert v v ht) 
           HashMap.empty [0 :: Int .. n - 1]
  let x = foldl'' (/ s i -> hashmap HashMap.! i + s) 0 [0 .. n - 1]
  print x

Al examinar el rendimiento para n = 10,000,000, encuentro que el tiempo total de ejecución es el siguiente:

• HashMap de Java - 24.387s
• Haskell HashTable - 7.705s, 41% de tiempo en GC (
• Haskell HashMap - 9.368s, 62% de tiempo en GC

Al reducirlo a n = 1,000,000, obtenemos:

• HashMap de Java - 0.700s
• Haskell HashTable - 0.723s
• Haskell HashMap - 0.789s

Esto es interesante por dos razones:

1. El rendimiento es generalmente bastante cercano (excepto cuando Java diverge por encima de las entradas de 1M)
2. Una gran cantidad de tiempo se gasta en la colección! (matando a Java en el caso de n = 10,0000,000).

Esto parece indicar que en lenguajes como Haskell y Java que han encajonado las claves del mapa, se ve un gran éxito de este boxeo. Los idiomas que no necesitan, o pueden desempaquetar las claves y los valores probablemente verán un par de veces más rendimiento.

Claramente, estas implementaciones no son las más rápidas, pero diría que usar Java como línea de base, al menos son aceptables / utilizables para muchos propósitos (aunque quizás alguien más familiarizado con la sabiduría de Java podría decir si HashMap se considera razonable).

Me gustaría señalar que el Haskell HashMap ocupa mucho espacio en comparación con el HashTable.

Los programas de Haskell se compilaron con GHC -O2 -threaded y -O2 -threaded , y se ejecutaron con solo el indicador +RTS -s para las estadísticas de GC en tiempo de ejecución. Java fue compilado con OpenJDK 1.7.