Simulación clásica de "100 puertas" en Clojure -- mparative-review campo con clojure campo con simulation camp codereview Relacionados El problema

Classic “100 doors” simulation in Clojure


1
vote

problema

Español

Leí esta pregunta sobre el " 100 puertas "rompecabezas , y pensé que haría un buen Ejercicio rápido.

Terminé con dos implementaciones. El primero es más sencillo y usa un vector para almacenar el estado booleano de cada puerta.

Esto es bastante lento, y que tiene un vector de true y false

Me gustaría comentarios generales en cualquier cosa que esté aquí. La necesidad de oneth-range es desafortunado (como es su nombre), y cualquier sugerencia para evitar su uso sería agradable. Sé que esto probablemente puede resolverse completamente utilizando matemáticas simples, pero me gustaría sugerencias sobre el algoritmo "Manual".

  ; Example of set-version usage and time (let [n 5000]   (time     (find-open-doors-for n n))) "Elapsed time: 939.315276 msecs" => (1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225 1296 1369 1444 1521 1600 1681 1764 1849 1936 2025 2116 2209 2304 2401 2500 2601 2704 2809 2916 3025 3136 3249 3364 3481 3600 3721 3844 3969 4096 4225 4356 4489 4624 4761 4900)   

  (ns irrelevant.hundred-doors-vec)  (defn- new-doors [n-doors]   (vec (repeat n-doors false)))  (defn- multiple-of? [n mutliple]   (zero? (rem n mutliple)))  (defn- oneth-range   "Returns a range without 0. Max is inclusive."   ([] (rest (range)))   ([max] (rest (range (inc max)))))  (defn- toggle-doors   "Toggles the state of every nth door."   [doors every-n]   (mapv #(if (multiple-of? % every-n)            (not %2)            %2)         (oneth-range), doors))  (defn- toggle-doors-for [doors max-n]   (reduce toggle-doors doors (oneth-range max-n)))  (defn find-open-doors-for   "Simulates the opening and closing of n-doors many doors, up to a maximum skip distance of n."   [n-doors n]   (let [doors (new-doors n-doors)         toggled (toggle-doors-for doors n)]      (->> toggled          (map vector (oneth-range))          (filter second)          (map first))))   

  (ns irrelevant.hundred-doors-set)  (defrecord Doors [open n-doors])  (defn- new-doors [n-doors]   (->Doors #{} n-doors))  (defn- multiple-of? [n multiple]   (zero? (rem n multiple)))  (defn- oneth-range   "Returns a range without 0. Max is inclusive."   ([] (rest (range)))   ([max] (rest (range (inc max)))))  (defn- toggle-doors   "Toggles the state of every nth door."   [doors every-n]   (update doors :open     (fn [open]       (reduce (fn [acc-set n]                 (cond                   (not (multiple-of? n every-n)) acc-set                   (open n) (disj acc-set n)                   :else (conj acc-set n)))               open               (oneth-range (:n-doors doors))))))  (defn- toggle-doors-for [doors max-n]   (reduce toggle-doors doors (oneth-range max-n)))  (defn find-open-doors-for   "Simulates the opening and closing of n-doors many doors, up to a maximum skip distance of n."   [n-doors n]   (let [doors (new-doors n-doors)         toggled (toggle-doors-for doors n)]      (-> toggled         (:open)         (sort))))   

Original en ingles

I read this question about the "100 Doors" puzzle, and thought that it would make for a good quick exercise.

I ended up with two implementations. The first is more straightforward and uses a vector to store the boolean state of each door.

This is quite slow though, and having a vector of true and falses seems off, so I decided to instead try making it use a set of open doors, and just toggle membership of the set. This is much faster, although the logic is a bit more complex.

I'd like just general feedback on anything that's here. The need for oneth-range is unfortunate (as is its name), and any suggestions to avoid its use would be nice. I know this can probably be solved entirely using simple math, but I'd like suggestions on the "manual" algorithm.

; Example of set-version usage and time (let [n 5000]   (time     (find-open-doors-for n n))) "Elapsed time: 939.315276 msecs" => (1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225 1296 1369 1444 1521 1600 1681 1764 1849 1936 2025 2116 2209 2304 2401 2500 2601 2704 2809 2916 3025 3136 3249 3364 3481 3600 3721 3844 3969 4096 4225 4356 4489 4624 4761 4900) 

(ns irrelevant.hundred-doors-vec)  (defn- new-doors [n-doors]   (vec (repeat n-doors false)))  (defn- multiple-of? [n mutliple]   (zero? (rem n mutliple)))  (defn- oneth-range   "Returns a range without 0. Max is inclusive."   ([] (rest (range)))   ([max] (rest (range (inc max)))))  (defn- toggle-doors   "Toggles the state of every nth door."   [doors every-n]   (mapv #(if (multiple-of? % every-n)            (not %2)            %2)         (oneth-range), doors))  (defn- toggle-doors-for [doors max-n]   (reduce toggle-doors doors (oneth-range max-n)))  (defn find-open-doors-for   "Simulates the opening and closing of n-doors many doors, up to a maximum skip distance of n."   [n-doors n]   (let [doors (new-doors n-doors)         toggled (toggle-doors-for doors n)]      (->> toggled          (map vector (oneth-range))          (filter second)          (map first)))) 

(ns irrelevant.hundred-doors-set)  (defrecord Doors [open n-doors])  (defn- new-doors [n-doors]   (->Doors #{} n-doors))  (defn- multiple-of? [n multiple]   (zero? (rem n multiple)))  (defn- oneth-range   "Returns a range without 0. Max is inclusive."   ([] (rest (range)))   ([max] (rest (range (inc max)))))  (defn- toggle-doors   "Toggles the state of every nth door."   [doors every-n]   (update doors :open     (fn [open]       (reduce (fn [acc-set n]                 (cond                   (not (multiple-of? n every-n)) acc-set                   (open n) (disj acc-set n)                   :else (conj acc-set n)))               open               (oneth-range (:n-doors doors))))))  (defn- toggle-doors-for [doors max-n]   (reduce toggle-doors doors (oneth-range max-n)))  (defn find-open-doors-for   "Simulates the opening and closing of n-doors many doors, up to a maximum skip distance of n."   [n-doors n]   (let [doors (new-doors n-doors)         toggled (toggle-doors-for doors n)]      (-> toggled         (:open)         (sort)))) 
        

Lista de respuestas

1
 
vote
vote
La mejor respuesta
 

Mi filosofía es "un problema fundamentalmente mutable requiere una solución fundamentalmente mutable":

  redirect0  

con resultado:

  redirect1  

Acabo de notar que desea las primeras puertas abiertas n:

  redirect2  

con resultado:

  redirect3  
 

My philosophy is "A fundamentally mutable problem requires a fundamentally mutable solution":

(def N 100) (def bound (inc N))  (defn calc-doors []   (verify (pos? N))   (let [bound (inc N)         doors (long-array bound 0) ]     (doseq [step (range 1 bound)             idx (range 0 bound step)]       (aset-long doors idx         (inc (aget doors idx))) )      (vec doors)))  (dotest   (let [doors (time (calc-doors))]     (dotimes [i bound]       (println (format "%5d %5d" i (nth doors i)))))) 

with result:

----------------------------------    Clojure 1.9.0    Java 10.0.1 ----------------------------------  Testing tst.demo.core "Elapsed time: 0.498 msecs"      0   100     1     1     2     2     3     2     4     3     5     2     6     4     7     2     8     4     9     3    10     4    11     2    12     6    13     2    14     4    15     4    16     5    17     2    18     6    19     2    20     6    21     4    22     4    23     2    24     8    25     3    26     4    27     4    28     6    29     2    30     8 

Just noticed that you want the first N open doors:

(defn door-open?   "Returns true if `door-idx` is open"   [door-idx]   (assert (pos? door-idx))   (let [hits (atom 0)]     (doseq [step (range 1 (inc door-idx))]       (when (zero? (rem door-idx step))         (swap! hits inc)))     (odd? @hits)))  (defn first-n-open-doors   "Return a vector of the first N open doors"   [doors-wanted]   (assert (pos? doors-wanted))   (loop [idx       1          open-idxs []]     (let [next-idx       (inc idx)           next-open-idxs (if (door-open? idx)                            (conj open-idxs idx)                            open-idxs)]       (if (= doors-wanted (count next-open-idxs))         next-open-idxs         (recur next-idx next-open-idxs))))) 

with result:

(first-n-open-doors 100) => [1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225 1296 1369 1444 1521 1600 1681 1764 1849 1936 2025 2116 2209 2304 2401 2500 2601 2704 2809 2916 3025 3136 3249 3364 3481 3600 3721 3844 3969 4096 4225 4356 4489 4624 4761 4900 5041 5184 5329 5476 5625 5776 5929 6084 6241 6400 6561 6724 6889 7056 7225 7396 7569 7744 7921 8100 8281 8464 8649 8836 9025 9216 9409 9604 9801 10000] "Elapsed time: 1279.926319 msecs" 
 
 
       
       
1
 
vote

sus implementaciones

Su toggle-doors Las funciones son más lentas de lo que necesitan. Veamos el primero:

  (defn- toggle-doors   "Toggles the state of every nth door."   [doors every-n]   (mapv #(if (multiple-of? % every-n)            (not %2)            %2)         (oneth-range), doors))   

Esto llama a cada uno de los doors , volteando su estado solo si su número se divide por every-n . Por lo tanto, la función toggle-doors-for4 hace max-n * max-n Puerta de las puertas en todos.

Una mejor manera de toggle-doors es para llamar solo en las puertas que necesitan alternar:

  (defn toggle-doors [doors every-n]   (reduce (fn [ds i] (assoc ds i (not (ds i))))           doors           (range (dec every-n) (count doors) every-n)))   

(He cambiado defn- a defn para poder ejercer la función de la conflaz.)

Esto golpea sobre (defn- toggle-doors "Toggles the state of every nth door." [doors every-n] (mapv #(if (multiple-of? % every-n) (not %2) %2) (oneth-range), doors)) 0 de las puertas. Por lo que el número o los golpes en (defn- toggle-doors "Toggles the state of every nth door." [doors every-n] (mapv #(if (multiple-of? % every-n) (not %2) %2) (oneth-range), doors)) 1 ahora es aproximadamente

  (defn- toggle-doors   "Toggles the state of every nth door."   [doors every-n]   (mapv #(if (multiple-of? % every-n)            (not %2)            %2)         (oneth-range), doors)) 2  

... que, según este , es sobre < / p>

  (defn- toggle-doors   "Toggles the state of every nth door."   [doors every-n]   (mapv #(if (multiple-of? % every-n)            (not %2)            %2)         (oneth-range), doors)) 3  

Esto es como la mejora de burbujas a clasificación rápida. Sobre esta base, para un (defn- toggle-doors "Toggles the state of every nth door." [doors every-n] (mapv #(if (multiple-of? % every-n) (not %2) %2) (oneth-range), doors)) 4 de 100,

  • Tu versión hace 10,000 golpes;
  • El mío hace alrededor de 460 (482, de hecho).

así que el mío es aproximadamente 20 veces más rápido que el suyo.

Mi enfoque preferido

Estamos buscando las puertas que reciben un número impar de veces por un evento abierto / cerrado. Podemos encontrar estos de la siguiente manera:

  (defn- toggle-doors   "Toggles the state of every nth door."   [doors every-n]   (mapv #(if (multiple-of? % every-n)            (not %2)            %2)         (oneth-range), doors)) 5  

Tomando cada línea a su vez ...

  • (defn- toggle-doors "Toggles the state of every nth door." [doors every-n] (mapv #(if (multiple-of? % every-n) (not %2) %2) (oneth-range), doors)) 6 es el rango de intervalos para los pases a través de las puertas;
  • (defn- toggle-doors "Toggles the state of every nth door." [doors every-n] (mapv #(if (multiple-of? % every-n) (not %2) %2) (oneth-range), doors)) 7 devuelve la secuencia de puertas golpeadas por el paso con el paso dado;
  • (defn- toggle-doors "Toggles the state of every nth door." [doors every-n] (mapv #(if (multiple-of? % every-n) (not %2) %2) (oneth-range), doors)) 8 es toda la secuencia de hits de puerta;
  • (defn- toggle-doors "Toggles the state of every nth door." [doors every-n] (mapv #(if (multiple-of? % every-n) (not %2) %2) (oneth-range), doors)) 9 Maps Cada puerta al número de hits que recibe;
  • doors0 Filtra las entradas del mapa para la rareza del número de visitas.

La respuesta son las teclas de las entradas doors1 , ordenadas para mostrar.

Puede abreviar esta cascada de cálculos usando el doors2 roscado Macro:

  doors3  

A pesar de las apariencias, esto no es tan diferente de su solución.

  • convierte la secuencia de golpes de puerta en una estructura de datos explícita.
  • un golpe, en lugar de voltear el estado de una puerta, incrementa su conteo de hits.

 

Your implementations

Your toggle-doors functions are slower than they need be. Let's look at the first one:

(defn- toggle-doors   "Toggles the state of every nth door."   [doors every-n]   (mapv #(if (multiple-of? % every-n)            (not %2)            %2)         (oneth-range), doors)) 

This knocks on every one of the doors, flipping its state only if its number divides by every-n. So the toggle-doors-for function does max-n * max-n door knocks in all.

A better way to toggle-doors is to knock only on the doors that need toggling:

(defn toggle-doors [doors every-n]   (reduce (fn [ds i] (assoc ds i (not (ds i))))           doors           (range (dec every-n) (count doors) every-n))) 

(I've changed defn- to defn to be able to exercise the function from the REPL.)

This knocks on about 1 / every-n of the doors. So the number or knocks in toggle-doors-for is now roughly

max-n * (1 / 1 + 1 / 2 + ... 1 / max-n) 

... which, according to this, is about

max-n * ln (max-n) 

This is like the improvement from bubble-sort to quick-sort. On this basis, for a max-n of 100,

  • your version does 10,000 knocks;
  • mine does about 460 (482, in fact).

So mine is roughly 20 times as fast as yours.

My preferred approach

We are looking for the doors that are hit an odd number of times by an open/close event. We can find these as follows:

(defn hundred-doors []   (let [steps (range 1 101)         hits (fn [step] (range step 101 step))         changes (mapcat hits steps)         change-counts (frequencies changes)         opens (filter (comp odd? val) change-counts)]         (sort (map key opens))))     (hundred-doors)        => (1 4 9 16 25 36 49 64 81 100) 

Taking each line in turn ...

  • steps is the range of intervals for the passes through the doors;
  • hits returns the sequence of doors hit by the pass with the given step;
  • changes is the whole sequence of door hits;
  • change-counts maps each door to the number of hits it gets;
  • opens filters the map entries for oddness of number of hits.

The answer is the keys of the opens entries, sorted for display.

You can abbreviate this cascade of computations using the ->> threading macro:

(defn hundred-doors []   (->> (range 1 101)         (mapcat (fn [step] (range step 101 step)))         (frequencies)         (filter (comp odd? val))         (map key)         (sort))) 

Despite appearances, this is not so different from your solution.

  • It turns the sequence of door hits into an explicit data structure.
  • A hit, instead of flipping the state of a door, increments its hit-count.
 
 

Relacionados problema

4  Tarea de lotería virtual  ( Virtual lotto task ) 
Tuve la tarea de escribir un simulador de lotería. Mi programa funciona de la siguiente manera: Para comenzar, el usuario puede escribir en 6 números. Lu...

1  Simulación de la placa de galton  ( Galton board simulation ) 
Este programa está escrito para Windows 7 en MINGW utilizando GCC. Estoy buscando recomendaciones para mejorar la portabilidad del programa. /* galtonboa...

1  Medidas repetidas de optimización simuladora  ( Repeated measures simulator optimisation ) 
Estoy aprendiendo a programar en R y para hacer eso y crear algo útil en el proceso, he decidido reescribir este applet Java para la simulación de medidas r...

5  Monte Carlo Moneda Simulación Flip  ( Monte carlo coin flip simulation ) 
He estado aprendiendo sobre las simulaciones de Monte Carlo en la introducción de MIT a la clase de programación, y estoy tratando de implementar una que calc...

5  Vectorización para simulación de temperatura  ( Vectorization for temperature simulation ) 
Soy nuevo en Matlab y me gustaría saber consejos para reducir el tiempo de procesamiento de dicho programa. El esquema del código real es muy similar al códig...

8  Los individuos reproducen y mutan  ( Individuals reproduce and mutate ) 
¿Cómo puedo mejorar el rendimiento (en términos de tiempo de cómputo) de este código? # Settings const nbloci = 100 # length of the genome const ...

1  Cuenta las precipitaciones acumuladas en una cadena de montaña 2D  ( Count the accumulated rainfall in a 2d mountain range ) 
desafío: cuenta cuánta lluvia se recogerá en los valles entre los picos de una cordillera en un mundo 2D. La gama de montaña se define por una única ...

8  UEFA Champions League Draw Simulator  ( Uefa champions league draw simulator ) 
Soy nuevo en Python y he escrito un simulador de sorteo de la UEFA Champions League. Recibe aportes para 32 equipos de 14 países, y luego los distribuye al az...

2  Simulación física de agregados limitados por difusión  ( Physical simulation of diffusion limited aggregates ) 
El siguiente código genera agregados limitados de difusión en un Lattice cuadrado bidimensional. Algunos del Código se han omitido (por ejemplo, Soporte par...

0  Consigue los lados del vecino de un cubo de rúbidos  ( Get neighbour sides of a rubics cube ) 
Estoy escribiendo 2x2x2 Rubics Cube Simulator. En mi código, tengo un concepto de cara, que es un lado individual del cubo, y el estado, que es agregado de lo...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos