Algoritmos

• C

  int BinarySearch (int dato,int length){
     int inicio,final,medio;
     inicio = 0;
     final = length-1;
     while (inicio <= final) {
         medio = (inicio+final)/2;
         if (dato == array[medio])
             return medio;
         else {
           if(dato > array[medio])
             inicio = medio+1;
           else
             final = medio-1;
         }
     }
     return -1;
 }

• Java

    public static void sort(double[  ] nums) {
        for(int i = 0; i < nums.length; i++) {
            // Nos quedamos con el mínimo, el actual. 
            int min = i;  
	    // Buscamos el más pequeño a partir de la posición actual
            for(int j = i; j < nums.length; j++) {
                if (nums[j] < nums[min]) 
                	min = j;
            }
	    // Cambiamos el actual por el más pequeño y vamos al siguiente
            double tmp = nums[i];
            nums[i] = nums[min];
            nums[min] = tmp;
        }
    }

Resuelve el problema en el que un thread (productor) prepara datos para que sean procesados por otro thread (consumidor). Dicho problema consiste en que, como no podemos controlar cuando se ejecuta ni uno ni otro, hay que impedir que el consumidor consuma más rápido de lo que el productor produce.

Se utilizará las siguientes instrucciones signal y wait, y mutex.lock y mutex.unlock.

• La instrucción signal incrementa un contador y no bloquea el thread en el momento de su llamada, en cambio wait comprueba si el contador está a 0, si lo está bloquea el thread en el que ha sido llamado hasta que el contador cambie; si no es 0 decrementa el contador y sigue la ejecución.
• Los mutex corresponden a operaciones de exclusión mutua. Cuando un thread llama al lock de un mutex si este está bloqueado el thread se bloqueará y el seguirá, también, bloqueado; si no estaba bloqueado el thread no se bloqueará pero sí el mutex, de esa forma cuando vuelva a llamarse de nuevo por otro thread este sí se bloqueará. Cuando se llama al unlock de un mutex no hay posibilidad de bloquear un thread y lo que hace es desbloquear el mutex.

Las instrucciones produce corresponden a la lectura del elemento, place a la colocación del elemento en el array (o lugar intermedio entre el productor y consumidor, la memoria compartida por los dos), take corresponde a la recogida del elemento del array y consume al proceso del dato.

La solución más sencilla nos viene cuando el array es infinito y utilizando el signal\wait: mientras existen elementos en el array el consumidor irá consumiendo, si no se esperará (itemsReady se ha de inicializar a 0):

producer:                consumer:
  forever                  forever
    produce(item)            itemsReady.wait()
    place(item)              take(item)
    itemsReady.signal()      consume(item)

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.

producer:                consumer:
  forever                  forever
    produce(item)            itemsReady.wait()
    mutexP.lock()            mutexC.lock()
    place(item)              take(item)
    mutexP.unlock()          mutexC.unlock()
    itemsReady.signal()      consume(item)

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).

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()

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()

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

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.

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

http://www.penzba.co.uk/Writings/TheTeleportingTurtle.html

• ActionScript

function desordenaArray (v) {
	var len = v.length;
	var vTmp = new Array ();
	var j;
	for (i = 0; i < len; i++) {
		j = Math.round(Math.random()*((len-i-1)));   // random que de un numero entre el 0 y (len - i - 1)
		vTmp[i] = v[j];
		v[j] = v[len-i-1];
	}
	return vTmp;
}

i = 1;
while((i * 10) < x)
    i *= 10;

• C

	pos = (pos + 1) % length;
	array[pos] = elem;

Para un ejercicio en el que se nos pedía rellenar un array de 10 posiciones con números aleatorios se nos dió dos posibles soluciones:

• Crear el array, e ir llenando el array generando un número aleatorio y comprobar que no exista antes de meterlo.
• Crear un segundo array con 10 posiciones en las que hay un número distinto de -1, generar un número aleatorio que corresponda a la posición de este segundo array, si en esa no existe un -1 introduciríamos ese número en el array y cambiaríamos el valor del 2º por -1.

Luego se nos mostró otra tercera forma de implementarlo:

1. Crear un segundo array en el que los valores sean los mismos que la posición en la que están.
2. Generar un número aleatorio.
3. Ir a la posición donde está ese número y coger el valor y meterlo en el primer array.
4. Cambiar el último número del array por la posición que nos ha dicho.
5. 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.

Este algoritmo intercambia el valor de dos integers:

procedure AddSwap (var X, Y: integer);
begin
  if X <> Y then begin
    X := X + Y;
    Y := X - Y;
    X := X - Y
  end
end

Ejemplo:

x = 5
y = 8
x = x + y    -> x = 13
y = x - y    -> y = 5
x = x - y    -> x = 8

return a ? (b || c) : (b && c);

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: 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.