Попытка написать Quicksort в D, получить OutOfMemoryError

Question

В настоящее время пытается изучить язык программирования D.

Написал этот маленький quicksort algo, который возвращает OutOfMemoryError при работе с отправленным примером.

import std.stdio; 
import std.algorithm; 

int[] qs(int[] ary) 
{ 
    if(ary.length <= 1) 
    { 
     return ary; 
    } 

    int pivot_pos = 0; 
    int pivot  = ary[pivot_pos]; 

    for(int i = 0; i < ary.length; i++) 
    { 
     if(ary[i] < pivot) 
     { 
      ary = ary.remove(i) ~ ary; 
      pivot_pos++; 
     } 
     else 
     { 
      ary ~= ary.remove(i); 
      if(i < pivot_pos) 
       pivot_pos--; 
     } 
    } 

    return qs(ary[0..pivot_pos]) ~ qs(ary[(pivot_pos+1)..ary.length]); 
} 

int main() 
{ 

    int[] ary = [ 2, 1, 4, 1, 6, 78, 3, 5, 10, 129, 234, 3, 5 ]; 

    ary = qs(ary); 

    foreach(int element; ary) 
    { 
     printf("%d ", element); 
    } 

    return 0; 
} 

Любые подсказки, как решить это или что не так в алго? Любые советы, как узнать D и что мне нужно заботиться?

Answer 1

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

вы должны использовать своп:

auto tmp=ary; 
while(tmp.length) 
{ 
    if(tmp[0]==pivot)break;//assumes unique 
    if(tmp[0]<pivot) 
    { 
     tmp=tmp[1..$]; 
     pivot_pos++; 
    } 
    else 
    { 
     swap(tmp[0],tmp[$-1]); 
     tmp=tmp[0..$-1]; 
    } 
} 

или просто использовать std.algorithm.partition для него источник его можно найти here