многопоточный питон "максимальная глубина рекурсии"

Question

Я использую многопоточность Python для реализации быстрой сортировки. Быстрая сортировка реализована в функции. Это рекурсивная функция. Каждый поток вызывает Quicksort для сортировки имеющегося массива. Каждый поток имеет свой собственный массив, в котором хранятся числа, которые необходимо отсортировать. Если размер массива меньше (<10000). Это работает хорошо. Однако, если размер массива больше, он показывает «максимальное превышение глубины рекурсии». Итак, я использую функцию setrecursionlimit () для сброса глубины рекурсии до 1500. Но программа вылетает напрямую ... Ниже приведен код быстрой сортировки. Это хорошо работает, если не в многопоточной среде. Кажется, что несколько потоков является причиной проблемы глубины рекурсии. </p>

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

Похоже, ваш реальный вопрос: «Почему глубина рекурсии короче при использовании потоков»? Я постараюсь ответить на этот вопрос.

Во-первых, фон. Каждый уровень рекурсии хранится в области памяти, известной как стек. К сожалению, система должна заранее выделить место в стеке и не знает заранее, сколько места в стеке может понадобиться вашей программе. Вот почему слишком большая рекурсия вызывает ошибку «максимальной глубины рекурсии»: ваша программа использовала все это пространство стека.

Каждый поток нуждается в своем собственном стеке для хранения списка функций, которые в данный момент выполняются в этом потоке. В однопоточной программе система может предоставить большой кусок памяти в стек для этого одного потока. В многопоточной программе система должна быть немного более консервативной, и она дает только небольшой стек каждому потоку. В противном случае программа с большим количеством потоков может быстро использовать всю системную память только с использованием стека (большая часть которой не будет использоваться).

Все это выполняется операционной системой и / или библиотекой C, поверх которой работает Python (точнее, CPython). Python изо всех сил пытается помешать вам использовать весь стек C, потому что это вызовет серьезный сбой, а не просто исключение. Вы можете указать Python, как вести себя с функцией setrecursionlimit, но это не меняет фактического объема доступного стекового пространства.

В системе unix-ish с оболочкой bash вы можете изменить размер стека с помощью команды ulimit -s. Для получения дополнительной информации введите help ulimit в командной строке bash.

Answer 2

• Вы используете рекурсивную реализацию быстрой сортировки. Вы хотите реализовать быструю сортировку, используя вместо этого итерацию.

  Рекурсия не масштабируется в Python (по крайней мере, в CPython), поэтому при большем вводе она завершится неудачей.Вы можете увеличить предел рекурсии, но это позволит вам масштабировать только в большем диапазоне, но не сделает вашу реализацию по-настоящему масштабной.Это также связано с тем, что если у вас слишком много рекурсии, возможна ошибка сегмента.Этот подход работает (или, скорее, не работает) также и для многопоточного кода, вам просто нужно сделать это больше, потому что предел рекурсии для каждого потока будет ниже.В общем, это проигрышное предложение: вместо этого используйте итерацию.

• Вы используете потоки (или планируете), что обычно является плохим признаком.Нити сбивают с толку, опасны и трудны.Более того, потоки в Python не дают вам параллельного выполнения, если это то, что вы ожидали.Использование потоков для реализации быстрой сортировки, особенно в Python, вероятно, окажется не идеальным.(Если вам необходимо сделать это, вы должны хотя бы отступить и понять, что это может быть не лучшим подходом.)

Answer 3

Почему вы пишете свою собственную процедуру быстрой сортировки?Это домашнее задание?

Если нет, я бы предложил использовать встроенные механизмы сортировки;они довольно хороши для подавляющего большинства случаев и не страдают от проблемы глубины рекурсии.Если вы смотрите на очень большие наборы данных, я бы посоветовал взглянуть на различные контейнеры и алгоритмы, доступные от scipy и numpy.

Если это просто из любопытства реализации подпрограммы, как Марсело предлагает в комментарияхнам нужно будет увидеть код.

Answer 4

Вот итерационный код для быстрой сортировки

    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"

Answer 5

Проблема, с которой вы сталкиваетесь, заключается в том, что рекурсивная функция использует память, и при большом количестве элементов и, следовательно, большом количестве рекурсий у вас не хватает памяти. Это объясняет, почему повышение предела рекурсии приводит к сбою вашей программы - вы запрашиваете больше памяти, чем у вас.

Если вы действительно хотите реализовать быструю сортировку для большого количества элементов, вам нужно прочитать эту статью в Википедии об использовании памяти, особенно с использованием быстрой сортировки. В противном случае, как предположил Натан, в Python уже есть встроенная функция sorted(). Если это не домашняя работа или любопытство, я настоятельно рекомендую использовать это.