0votos

Los K números mas grandes en una secuencia infinita. en Haskell

por josejuan hace 2 años

Se crean dos hilos concurrentes, uno lee y el otro muestra estadísticas. Para mantener k-max valores se usa una tabla (árbol balanceado en este caso) sacando el menor elemento si el nuevo no está en la tabla.

En el LHC se producen miles de millones de colisiones por segundo y dos físicos han realizado una apuesta, ¿podrías ayudarles?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import Data.IntMap.Strict (IntMap) 
import qualified Data.IntMap.Strict as Map 
import Control.Concurrent 
import Control.Monad 
 
type KMax = MVar (IntMap Int) 
 
makeKMax :: Int → IO KMax 
makeKMax k = newMVar $ Map.fromList $ take k [(i, 0) | i ← [minBound, minBound + 1 …]] 
 
kmHit :: KMax → Int → IO () 
kmHit km x = modifyMVar_ km update 
  where update m = let (a, _) = Map.findMin m 
                   in  η $ case (x < a, Map.lookup x m) of 
                         (𝑇,   _) → m                               -- es menor 
                         (_, 𝐽 _) → Map.adjust (+1) x m             -- está 
                         (_, 𝑁  ) → Map.insert x 1 $ Map.delete a m -- empuja al menor 
 
kmStatus :: KMax → IO [(Int, Int)] 
kmStatus km = (filter ((0<).snd) ∘ Map.assocs) ↥ readMVar km 
 
-- Ya está. 
 
 
 
 
 
 
 
 
 
 
-- Para ejecutar el proceso concreto del experimento, lanzamos dos 
-- threads concurrentemente, mientras uno va leyendo los eventos, el otro 
-- cada cierto tiempo muestra la tabla con los k-max. 
-- 
 
-- El proceso que va cargando los eventos de entrada, aquí leemos de consola 
-- enteros separados por espacios 
events :: KMax → IO () 
events km = forever $ getLine ↪ ↱_(kmHit km) ∘ map read ∘ words 
 
 
 
-- Proceso que va reportando los resultados del experimento cada t segundos 
-- pero sólo si se producen nuevos eventos que cambian el estado de k-max 
report :: Int → KMax → [(Int, Int)] → IO () 
report t km cur = do 
  threadDelay (10⁶ × t) 
  nex ← kmStatus km 
  when (cur ≢ nex) $ do 
    putStrLn "Status ====================" 
    ↱_print nex 
  report t km nex 
 
 
main = do 
  km ← makeKMax 5 
  void $ forkIO $ events km 
  void $ forkIO $ report 5 km [] 
  forever $ threadDelay (10⁶ × 5) 
 
 
 
 
 
{- 
 
  Por ejemplo 
 
> main 
4 4 4 4 7 7 6 6 
Status ==================== 
(4,4) 
(6,2) 
(7,2) 
8 8 8 9 9 
Status ==================== 
(4,4) 
(6,2) 
(7,2) 
(8,3) 
(9,2) 
12 12 12 12 
Status ==================== 
(6,2) 
(7,2) 
(8,3) 
(9,2) 
(12,4) 
3 3 3 8 8 
Status ==================== 
(6,2) 
(7,2) 
(8,5) 
(9,2) 
(12,4) 
10 
Status ==================== 
(7,2) 
(8,5) 
(9,2) 
(10,1) 
(12,4) 
100 
Status ==================== 
(8,5) 
(9,2) 
(10,1) 
(12,4) 
(100,1) 
 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.