pitón multiproceso “profundidad de recursión máximo excedido”

Question

Yo uso Python multiproceso para darse cuenta de la ordenación rápida. Ordenación rápida es poner en práctica en una función. Es una función recursiva. Cada subproceso llama a la ordenación rápida para ordenar la matriz que tiene. Cada hilo tiene su propia matriz que almacena las necesidades números para ser ordenados. Si el tamaño de la matriz es más pequeña (<10 000). Se ejecuta bien. Sin embargo, si el tamaño de la matriz es más grande, que muestra la "profundidad de recursión máximo exceda". Por lo tanto, yo uso la función setrecursionlimit () para restablecer el nivel de recursividad a 1500. Sin embargo, el programa de choque directamente ... La siguiente es la clasificación rápida de código. Funciona bien, si no en entorno multi-hilo. Parece múltiples hilos es la causa del problema de nivel de recursividad.

def partition (array, p, r):
    x = array[r]
    i = (p-1)
    j = p
    while (1):
        if array[j] <= x:
            i = (i+1)
            temp = array[j]
            array[j] = array[i]
            array[i] = temp
        j+=1
        if j == r:
            break
    temp = array[i+1]
    array[i+1] = array[r]
    array[r] = temp
    return i+1

def quicksort (array, p, r):
    if p < r:
        q = partition (array, p, r)
        quicksort (array, p, q-1)
        quicksort (array, q+1, r)

Answer 1

Parece que su verdadera pregunta es "¿Por qué es el nivel de recursividad más corto cuando se utiliza hilos"? Voy a tratar de responder a esta pregunta.

En primer lugar, fondo. Cada nivel de recursividad se almacena un área de memoria conocida como la pila. Desafortunadamente, el sistema tiene que asignar el espacio de pila de antemano y no se sabe de antemano cuánto espacio de pila puede ser que necesite su programa. Es por eso que mucha recursividad produce un error de "máximo nivel de recursividad":. Su programa ha utilizado todo ese espacio de pila

Cada hilo necesita su propia pila para almacenar la lista de las funciones que se están ejecutando actualmente en ese hilo. En un solo programa de roscado, el sistema puede permitirse el lujo de dar una gran parte de la memoria a la pila para que un hilo. En un programa multi-roscado, el sistema tiene que ser un poco más conservador y se da sólo una pequeña pila para cada hilo. De lo contrario, un programa con muchos hilos podría consumir rápidamente toda la memoria del sistema acaba con el espacio de pila (la mayoría de las cuales no se utiliza).

Todo esto se realiza por el sistema operativo y / o por la biblioteca C, la cual Python (más precisamente, CPython) se ejecuta en la parte superior de. Python se esfuerza para evitar que se utilice toda la pila C, ya que podría causar un choque duro en lugar de simplemente una excepción. Se puede decir Python cómo comportarse con la función setrecursionlimit, pero eso no cambia el real cantidad de espacio de pila disponible.

En un sistema UNIX-ish con una cáscara del golpe, que puede ser capaz de cambiar el tamaño de la pila con el comando ulimit -s. Tipo help ulimit a su pronta de Bash para más información.

Answer 2

• Está utilizando una aplicación recursiva de la clasificación rápida. que desea implementar la clasificación rápida usando iteración en su lugar.

  recursión no es escalable en Python (en CPython por lo menos), por lo que para la entrada más grande que fallará. Puede aumentar el límite de recursividad, pero esto sólo va a dejar que se cambia la escala en un rango más amplio, no hacer que su aplicación realmente escalar. También viene a costa de lo que permite la posibilidad de una violación de segmento si se tiene demasiado recursividad. Este enfoque funciona (o más bien no funciona muy bien), así para el código multiproceso, sólo hay que hacerlo más, porque el límite de recursión para cada hilo será más bajo. Con todo, es un caso perdido:. Uso iteración en lugar

• Está utilizando hilos (o planeando), que suele ser una mala señal. Los hilos se confuso y peligroso y difícil. Lo que es más, las discusiones en Python no le dan la ejecución en paralelo, si eso es lo que estabas esperando. El uso de hilos para una clasificación rápida aplicación, sobre todo en Python, probablemente resultar menos que ideal. (Si usted está obligado a hacerlo, debe hacer una copia al menos paso y entender que tal vez no sea el mejor enfoque.)

Answer 3

¿Por qué se desea escribir su propia rutina de ordenación rápida? Es esta tarea?

Si no es así, me gustaría sugerir el uso de la incorporada en la clasificación de mecanismos; que son bastante buenos para la gran mayoría de los casos y no sufren de un problema de nivel de recursividad. Si usted está buscando en los conjuntos de datos extremadamente grandes, sugeriría mirar los diversos contenedores y algoritmos disponibles de scipy y numpy.

Si es puramente por curiosidad de la implementación de la rutina, como Marcelo sugiere en los comentarios, tendremos que ver código.

Answer 4

El problema que tiene es un recursivo memoria el uso de funciones, y con un gran número de elementos y por lo tanto un gran número de recurrencias, se está ejecutando fuera de la memoria. Esto explica por qué el aumento del límite de recursividad se bloquea su programa -. Que está pidiendo más memoria que usted tiene

Si realmente desea implementar la clasificación rápida de un gran número de elementos, tendrá que leer este artículo en Wikipedia sobre el uso de memoria en concreto utilizando la clasificación rápida. De lo contrario, como se sugiere Nathan, Python ya se ha construido en función de sorted(). A menos que esta es la tarea o la curiosidad, yo sugeriría que usar.

Answer 5

Este es el código iterativo de QuickSort

    import time
    import random

    stack = []

    def partition(data,p,q):
        global stack
        pivot = p
        pivotvalue = data[q]
        for index in range(p,q+1):
            if data[index] < pivotvalue:
                temp = data[index]
                data[index] = data[pivot]
                data[pivot] = temp
                pivot = pivot + 1
        temp = data[q]
        data[q] = data[pivot]
        data[pivot] = temp
        return pivot

    def qSort(data,p,q):
        global stack
        push(stack,p,q)
        while isEmpty(stack) == False:
            q = pop(stack)
            p = pop(stack)
            pivot = partition(data,p,q)
            if pivot-1 > p:
                push(stack,p,pivot-1)
            if pivot+1 < q:
                push(stack,pivot+1,q)


    def push(stack,p,q):
        stack.append(p)
        stack.append(q)

    def pop(stack):
        global top
        if(len(stack)==0):
            return -1
        element = stack.pop()
        return element

    def isEmpty(stack):
        return len(stack) == 0

    if __name__ == '__main__':
        start_time = time.time()
        data = (range(1000000,0,-1))
        random.shuffle(data)
        #print data
        qSort(data,0,len(data)-1)
        #print data
        print time.time() - start_time, "seconds"