Diferencias

Muestra las diferencias entre dos versiones de la página.

--- otros:algoritmos [2008/09/15 12:58]
alfred
+++ otros:algoritmos [2020/05/09 09:25] (actual)
@@ Línea 27: / Línea 27: @@
 ===== Algoritmos de ordenación =====
@@ Línea 49: / Línea 50: @@
     }
 </code>
+==== MergeSort ====
+==== QuickSort ====
 ===== Algoritmos para entornos multi-proceso =====
@@ Línea 74: / Línea 81: @@
     itemsReady.signal()      consume(item)
 </code>
+En el caso en el que hayan varios productores y varios consumidores se debe proteger la colocación del elemento (producción), por ejemplo para que al añadir en el array no se deje ninguna celda libre o se sobreescriba una celda, y la recogida (consumición), para que dos consumidores no lean la misma celda.
+<code>
+producer:                consumer:
+  forever                  forever
+    produce(item)            itemsReady.wait()
+    mutexP.lock()            mutexC.lock()
+    place(item)              take(item)
+    mutexP.unlock()          mutexC.unlock()
+    itemsReady.signal()      consume(item)
+</code>
+Pero no siempre se tiene una cola infinita. Lo que se hace es añadir otro contador de signal\wait inicializado al número de elementos del array (''spacesLeft''), de esa forma podremos, antes de producir un elemento, comprobar si hay sitio libre en el array para hacerlo (para ahorrar recursos).
+<code>
+producer:                consumer:
+  forever                  forever
+    spacesLeft.wait()        itemsReady.wait()
+    produce(item)            mutexC.wait()
+    mutexP.wait()            take(item)
+    place(item)              mutexC.signal()
+    mutexP.signal()          consume(item)
+    itemsReady.signal()      spacesLeft.signal()
+</code>
+=== Código Python de ejemplo ===
+<code python>
+import threading
+import Queue
+class Producer(threading.Thread):
+    def __init__(self, in_queue, out_queue):
+        threading.Thread.__init__(self)
+        self.in_queue = in_queue
+        self.out_queue = out_queue
+    def run(self):
+        while True:
+            item = self.in_queue.get()
+            result = 'You should be doing work.'
+            self.out_queue.put(result)
+            self.in_queue.task_done()
+class Consumer(threading.Thread):
+    def __init__(self, out_queue):
+        threading.Thread.__init__(self)
+        self.out_queue = out_queue
+    def run(self):
+        while True:
+            item = self.out_queue.get()
+            result = 'This is your awesome output.'
+            self.out_queue.task_done()
+if __name__ == '__main__':
+    item_list = ['item1', 'item2', 'item3']
+    in_queue = Queue.Queue()
+    out_queue = Queue.Queue()
+    for i in xrange(len(item_list)):
+       t = Producer(in_queue, out_queue)
+       t.daemon = True
+       t.start()
+    for item in item_list:
+        in_queue.put(item)
+    for i in xrange(len(item_list)):
+        t = Consumer(out_queue)
+        t.daemon = True
+        t.start()
+    in_queue.join()
+    out_queue.join()
+</code>
+===== Algoritmos para detectar un bucle =====
+Si en una linked list queremos detectar si hay un bucle infinito podemos hacerlo de varias formas. La más sencilla es la de ir marcando los elementos que vamos comprobando, así al comprobar un elemento si tiene marca entonces significa que sí que existe un bucle. Otra forma sería ir guardando los elementos ya comprobados en una nueva lista luego, al comprobar un nuevo elemento si este existiese en la lista nueva es que, en efecto, hay un bucle. Pero hay otros algoritmos que simplifican esta operación y no gastan tantos 'recursos' (la segunda forma, por ejemplo, si la linked list fuese muy larga gastaría mucho). \\ \\
+[[http://en.wikipedia.org/wiki/Cycle_detection]]
+==== La liebre y la tortuga ====
+Consiste en tener dos punteros, uno que va pasando elemento por elemento (correspondería a la tortuga) y otro que a cada iteración salta dos elementos (correspondería a la liebre). Los dos inician en el primer elemento y lo que se comprueba es que no apunten al mismo, si así ocurriese significaría que existe un bucle.
+<code>
+turtle, rabbit = head, head
+steps_taken, step_limit = 0,2
+rabbit = head
+Forever:
+    if end==rabbit : return 'No loop' : else : rabbit = rabbit.next
+    steps_taken += 1
+    if rabbit==turtle : return 'Loop found'
+    if steps_taken==step_limit:
+        steps_taken = 0
+        step_limit *= 2
+        turtle = rabbit
+</code>
+[[http://www.penzba.co.uk/Writings/TheTeleportingTurtle.html]]
 ===== Otros algoritmos =====
@@ Línea 93: / Línea 190: @@
 </code>
+==== Potencia de 10 ====
+<code>
+i = 1;
+while((i * 10) < x)
+    i *= 10;
+</code>
 ==== Movimiento por array circular ====
   * C
@@ Línea 112: / Línea 214: @@
   - Ahora generaríamos otro número entre menor que la longitud del array-1, cogeríamos el valor del segundo array que está en esa posición y lo introduciríamos en el primer array. Luego, en el segundo, moveríamos a esa posición el último-1 valor.
 Qué conseguimos: Para diez valores no veríamos la diferencia, pero, por ejemplo para 3000? Además sólo es necesario un simple for, mientras que en los anteriores necesitaríamos un segundo bucle que generase números aleatorios hasta que no estén repetidos.
 ==== Intercambiar números ====
@@ Línea 133: / Línea 236: @@
 x = x - y    -> x = 8
 </code>
+==== Decir si dos de tres bools son ciertos ====
+<code>
+return a ? (b || c) : (b && c);
+</code>
+==== Marcar elementos ====
+El problema podría ser marcar elementos que se han procesado. Imaginemos que queremos procesar un gran número de elementos y lo hacemos en un entorno "multiproceso", en C, el algoritmo más rápido consistiría en mantener dos arrays de punteros de la misma logitud que el número de elementos que buscamos y un contador, cuando procesamos un elemento el puntero en la posición de su índice apuntará al puntero del segundo array que esté en la posición indicada por el contador y este al puntero que le apunta:
+{{ otros:algor:arrays.png |}}
+En la ilustración sólo el 4º elemento está procesado. La única desventaja es que se ha de sacrificar memoria a cambio de proceso.
+ \\ \\ Sacado de [[http://jaspervdj.be/posts/2010-07-11-the-dwarfs-and-the-fast-marking-algorithm.html]].

Programming

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página