Apuntes DAM
Volver al inicio

Contador de palabras en paralelo con un pool de hilos

Ejercicio de JavaDifícilUnos 70 minutos

Reparte un texto en bloques, cuenta las palabras de cada bloque en un hilo distinto con ExecutorService y Callable, y une los resultados parciales: el informe tiene que ser idéntico con 1 hilo o con 8. Concurrencia sin estado compartido, Future y combinación de mapas.

  • ExecutorService
  • Callable y Future
  • Reparto de trabajo en bloques
  • HashMap.merge
  • Ordenar con Comparator
  • Evitar condiciones de carrera

Enunciado

Contar las palabras de un texto enorme (las actas de un ayuntamiento, los registros de un servidor) se puede repartir: cada hilo cuenta un trozo y al final se suman los recuentos. Es el esquema «divide y vencerás» que usan desde los procesadores de varios núcleos hasta MapReduce en los centros de datos.

El error típico es que todos los hilos escriban en el mismo HashMap: no está preparado para accesos simultáneos y se pierden recuentos (o se corrompe). La forma limpia es que cada hilo cuente en su propio mapa y devuelva el resultado; el hilo principal es el único que los combina.

La prueba de que el programa es correcto es que el resultado no dependa del número de hilos ni del orden en que terminen: con 1, 3 u 8 hilos el informe de palabras tiene que ser exactamente el mismo.

Qué tiene que hacer el programa

  1. La primera línea es el número de hilos, de 1 a 8 (si no, Número de hilos no válido: debe estar entre 1 y 8 y nada más). El resto es el texto; las líneas en blanco no cuentan. Si no queda ninguna línea, No hay texto que analizar.
  2. Se usan tantos hilos como se pidan, pero nunca más que líneas. Las líneas se reparten en bloques consecutivos lo más iguales posible: si no salen exactos, los primeros bloques tienen una línea más. Cada bloque lo cuenta un hilo de un ExecutorService.
  3. Una palabra es una secuencia de letras (de la a a la z, las vocales con tilde, la ü y la ñ), sin distinguir mayúsculas; cualquier otro carácter separa palabras.
  4. Escribe Hilos: H · Líneas: L y una línea por bloque, en orden, con dos espacios delante: Bloque [i-j]: N palabras (o [i] si el bloque tiene una sola línea; las líneas se numeran desde 1 sin contar las vacías).
  5. Después, Palabras: N · Distintas: D con el total de palabras y de palabras distintas, y Más frecuentes: seguido de las 5 palabras más repetidas (o las que haya) sin contar las palabras vacías de la tabla, cada una como el número en 4 caracteres alineado a la derecha, un espacio y la palabra. A igual número, por orden alfabético según compareTo.

Entrada

Línea 1: número de hilos (1 a 8). Resto: el texto.

Datos de referencia

Palabras vacías (no salen en «Más frecuentes»)
Palabras
de, la, que, el, en, y, a, los, se, del, las, un, por, con, no, una, su, para, es, al, lo, como

Ejemplos de ejecución

Tu programa debe escribir exactamente esta salida para estas entradas. Las pruebas del editor incluyen estos ejemplos y otros casos ocultos.

Un texto con tres hilos

Entrada

3
La programación concurrente permite que varios hilos trabajen a la vez.
Cada hilo cuenta las palabras de su bloque de líneas.
Si los hilos comparten un mapa sin protección, se pierden datos.
Por eso cada hilo usa un mapa propio y devuelve el resultado.
El hilo principal espera con get() y suma los mapas parciales.
Con un hilo o con ocho hilos, el resultado debe ser el mismo.
La concurrencia bien hecha no cambia el resultado: solo el tiempo.

Salida por consola

Hilos: 3 · Líneas: 7
  Bloque [1-3]: 32 palabras
  Bloque [4-5]: 23 palabras
  Bloque [6-7]: 24 palabras
Palabras: 79 · Distintas: 56
Más frecuentes:
   4 hilo
   3 hilos
   3 resultado
   2 cada
   2 mapa

Número de hilos no válido

Entrada

12
Un texto cualquiera

Salida por consola

Número de hilos no válido: debe estar entre 1 y 8

Guía paso a paso

Intenta resolverlo por tu cuenta y abre un paso solo cuando te atasques: cada uno te acerca a la solución sin dártela entera.

1. Contar un bloque

Empieza por la versión sin hilos: un método contar(List<String>) que devuelva un mapa palabra → veces. split("[^a-záéíóúüñ]+") parte por todo lo que no sea letra y merge(palabra, 1, Integer::sum) suma 1 o crea la entrada.

java
for (String palabra : linea.toLowerCase().split("[^a-záéíóúüñ]+"))
    if (!palabra.isEmpty()) cuenta.merge(palabra, 1, Integer::sum);
2. Repartir las líneas

Con L líneas y H hilos, cada bloque tiene L / H líneas y los primeros L % H bloques una más. subList(inicio, inicio + tamaño) te da el trozo sin copiar nada.

3. Lanzar las tareas

Crea el pool con Executors.newFixedThreadPool(h) y envía cada bloque con submit. Una lambda que devuelve un valor es un Callable, y submit te devuelve un Future con el que recogerás su resultado.

java
ExecutorService pool = Executors.newFixedThreadPool(hilos);
Future<Map<String, Integer>> f = pool.submit(() -> contar(bloque));
4. Unir los resultados

Recorre los Future en el orden en que los creaste y llama a get(), que espera a que ese hilo termine. Suma cada mapa parcial en el total con merge. Solo el hilo principal toca el mapa total: no hay nada compartido y no hace falta sincronizar. Cierra el pool con shutdown().

5. Las más frecuentes

Pasa las entradas del mapa (menos las palabras vacías) a una lista y ordénala con un comparador: primero por número descendente y, si empatan, por la palabra con compareTo.

Resuélvelo aquí

El editor trae el esqueleto del programa. Pulsa «Ejecutar» para comprobarlo con los ejemplos y con 3 casos ocultos que buscan los errores típicos.

☕JavaContador de palabras en paralelo con un pool de hilosDifícil

Ejemplo

Entrada (lo que se escribe por teclado)
3
La programación concurrente permite que varios hilos trabajen a la vez.
Cada hilo cuenta las palabras de su bloque de líneas.
Si los hilos comparten un mapa sin protección, se pierden datos.
Por eso cada hilo usa un mapa propio y devuelve el resultado.
El hilo principal espera con get() y suma los mapas parciales.
Con un hilo o con ocho hilos, el resultado debe ser el mismo.
La concurrencia bien hecha no cambia el resultado: solo el tiempo.
Salida esperada
Hilos: 3 · Líneas: 7
  Bloque [1-3]: 32 palabras
  Bloque [4-5]: 23 palabras
  Bloque [6-7]: 24 palabras
Palabras: 79 · Distintas: 56
Más frecuentes:
   4 hilo
   3 hilos
   3 resultado
   2 cada
   2 mapa
⏳
Test oculto #3
⏳
Test oculto #4
⏳
Test oculto #5
0/5 tests pasados · pulsa un test para ver su entrada y su salida esperada

Solución explicada

Ver la solución completa
java
1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5import java.util.Scanner;
6import java.util.Set;
7import java.util.concurrent.ExecutorService;
8import java.util.concurrent.Executors;
9import java.util.concurrent.Future;
10
11public class Main {
12    static final Set<String> VACIAS = Set.of("de", "la", "que", "el", "en", "y", "a", "los", "se", "del", "las", "un",
13            "por", "con", "no", "una", "su", "para", "es", "al", "lo", "como");
14
15    /** Lo que hace cada hilo: contar las palabras de su bloque en un mapa propio, sin compartir nada. */
16    static Map<String, Integer> contar(List<String> lineas) {
17        Map<String, Integer> cuenta = new HashMap<>();
18        for (String linea : lineas) {
19            for (String palabra : linea.toLowerCase().split("[^a-záéíóúüñ]+")) {
20                if (!palabra.isEmpty()) cuenta.merge(palabra, 1, Integer::sum);
21            }
22        }
23        return cuenta;
24    }
25
26    static int suma(Map<String, Integer> cuenta) {
27        int total = 0;
28        for (int n : cuenta.values()) total += n;
29        return total;
30    }
31
32    public static void main(String[] args) throws Exception {
33        Scanner sc = new Scanner(System.in);
34        String primera = sc.hasNextLine() ? sc.nextLine().trim() : "";
35        if (!primera.matches("[1-8]")) {
36            System.out.println("Número de hilos no válido: debe estar entre 1 y 8");
37            return;
38        }
39        List<String> lineas = new ArrayList<>();
40        while (sc.hasNextLine()) {
41            String linea = sc.nextLine();
42            if (!linea.isBlank()) lineas.add(linea);
43        }
44        if (lineas.isEmpty()) {
45            System.out.println("No hay texto que analizar");
46            return;
47        }
48
49        // Nunca más hilos que líneas; los bloques, lo más iguales posible
50        int hilos = Math.min(Integer.parseInt(primera), lineas.size());
51        ExecutorService pool = Executors.newFixedThreadPool(hilos);
52        List<Future<Map<String, Integer>>> resultados = new ArrayList<>();
53        List<String> bloques = new ArrayList<>();
54        int inicio = 0;
55        for (int i = 0; i < hilos; i++) {
56            int tamano = lineas.size() / hilos + (i < lineas.size() % hilos ? 1 : 0);
57            List<String> bloque = lineas.subList(inicio, inicio + tamano);
58            resultados.add(pool.submit(() -> contar(bloque)));
59            bloques.add(tamano == 1 ? "[" + (inicio + 1) + "]" : "[" + (inicio + 1) + "-" + (inicio + tamano) + "]");
60            inicio += tamano;
61        }
62
63        // Se unen los resultados en el hilo principal, en el orden de los bloques
64        Map<String, Integer> total = new HashMap<>();
65        List<String> parciales = new ArrayList<>();
66        for (int i = 0; i < hilos; i++) {
67            Map<String, Integer> parcial = resultados.get(i).get();   // get() espera a que termine ese hilo
68            parciales.add("  Bloque " + bloques.get(i) + ": " + suma(parcial) + " palabras");
69            parcial.forEach((palabra, n) -> total.merge(palabra, n, Integer::sum));
70        }
71        pool.shutdown();
72
73        System.out.println("Hilos: " + hilos + " · Líneas: " + lineas.size());
74        parciales.forEach(System.out::println);
75        System.out.println("Palabras: " + suma(total) + " · Distintas: " + total.size());
76
77        List<Map.Entry<String, Integer>> lista = new ArrayList<>();
78        for (Map.Entry<String, Integer> e : total.entrySet()) if (!VACIAS.contains(e.getKey())) lista.add(e);
79        lista.sort((a, b) -> !a.getValue().equals(b.getValue()) ? b.getValue() - a.getValue() : a.getKey().compareTo(b.getKey()));
80        System.out.println("Más frecuentes:");
81        for (int i = 0; i < Math.min(5, lista.size()); i++) {
82            System.out.printf("%4d %s%n", lista.get(i).getValue(), lista.get(i).getKey());
83        }
84    }
85}

Cada hilo trabaja sobre su propio bloque y su propio mapa, y devuelve el resultado en lugar de escribirlo en una variable compartida. Sin estado compartido no hay condiciones de carrera, así que no hacen falta synchronized, cerrojos ni ConcurrentHashMap.

Callable es la versión de Runnable que devuelve un valor, y Future.get() es el punto de encuentro: bloquea hasta que la tarea termina. Recorrer los Future en orden hace que los parciales se impriman siempre igual, aunque los hilos acaben en cualquier orden.

La suma de recuentos es asociativa y conmutativa: da igual cómo se reparta el texto y en qué orden se combinen los trozos, el total es el mismo. Esa propiedad es la que permite paralelizar este problema (y la que hay que comprobar antes de paralelizar cualquier otro).

El pool limita los hilos a los pedidos (y a las líneas que hay) y los reutiliza. Crear un Thread a mano por cada bloque funcionaría con 8 bloques, pero no con 10.000.

Para ir más allá

  • Mide con System.nanoTime() cuánto tarda con 1, 2, 4 y 8 hilos sobre un texto de varios megas y explica por qué no se divide el tiempo entre 8.
  • Haz una versión con hilos que escriben en un ConcurrentHashMap compartido y compárala con esta.
  • Resuelve el mismo problema con lineas.parallelStream() y Collectors.groupingByConcurrent.

Dónde se explica