c++ - 基数排序 base 256 性能

Question

我正在尝试使用列表实现基数为 256 的基数排序。排序工作正常，但对大数组进行排序需要很长时间，此外复杂度应该是线性的，O(n)，但我没有得到那个结果，因为我在输出中对排序进行计时。这是我的代码:

插入函数:

//insert to the back of the list element pointed to by x
void insert(Item * ls, Item * x)
{
    x->prev = ls->prev;
    ls->prev->next=x;
    x->next=ls;
    ls->prev=x;
}

删除函数:

//delete link in list whose address is x
void delete_x(Item * x)
{
    x->prev->next = x->next;
    x->next->prev = x->prev;
    delete [] x;
}

Radix_Sort 函数:

void radix_sort_256(unsigned int *arr,unsigned int length)
//Radix sort implementation with base 256
{

    int num_of_digits=0,count=0,radix_num=0;
    unsigned int base=0,largest=0;

    Item List [256];             //Creating 256 Nodes ( Base 256 )
    for(int j=0; j<256;j++)      // Sentinel Init for each Node
    {
        List[j].key=0;
        List[j].next=&List[j];
        List[j].prev=&List[j];
    }

    for(unsigned int i=0; i<length ; i++)     //Finding the largest number in the array
    {
        if(arr[i]>largest)
            largest = arr[i];
    }

    while(largest != 0 )        //Finding the total number of digits in the bigest number( "largest" ) of the array.
    {
        num_of_digits++;
        largest = largest >> 8;
    }
    for(int i=0; i<num_of_digits; i++)
    {
        Item *node;
        for(unsigned int j=0; j<length; j++)
        {
            node = new Item;                      //Creating a new node(Total 256 nodes) and inserting numbers from the array to each node
            node->next = NULL;                    // with his own index.
            node->prev = NULL;
            node->key = arr[j];
            radix_num = ( arr[j] >> (8*i) ) & 0xFF;
            insert(&List[radix_num],node);
        }

        for(int m=0 ; m<256 ; m++)              //checking the list for keys // if key found inserting it to the array in the original order
        {
            while( List[m].next != &List[m] )
            {
                arr[count]=List[m].next->key;
                delete_x(List[m].next);             //deleting the Item after the insertion
                count++;
            }
        }
        count=0;
    }
}

主要内容:

void main()
{
    Random r;
    int start,end;
    srand((unsigned)time(NULL));

    // Seting up dinamic array in growing sizes,
    //  filling the arrayes with random
    for(unsigned int i=10000 ; i <= 1280000; i*=2)
    {
        // numbers from [0 to 2147483646] calling the radix
        //  sort function and timing the results
        unsigned int *arr = new unsigned int [i];
        for(int j=0 ; j<i ; j++)
        {
            arr[j] = r.Next()-1;
        }
        start = clock();
        radix_sort_256(arr,i);
        end = clock();
        cout<<i;
        cout<<"               "<<end-start;
        if(Sort_check(arr,i))
            cout<<"\t\tArray is sorted"<<endl;
        else
            cout<<"\t\tArray not sorted"<<endl;

        delete [] arr;
    }
}

任何人都可以看到，也许我正在做一些不必要的 Action ，这些 Action 需要花费大量时间来执行？

Answer 1

复杂性是一头难以掌握的野兽，因为它是多态的。

当我们谈到算法的复杂性时，我们通常会根据我们认为是瓶颈操作的内容对其进行简化和表达。

例如，在评估排序算法时，复杂度表示为比较次数；但是，如果您的内存是磁带¹ 而不是 RAM，真正的瓶颈是内存访问，因此快速排序 O(N log N) 最终比冒泡排序 O(N ** 2 ).

在这里，您的算法可能是最佳，它的实现似乎缺乏:例如，正在进行大量内存分配/取消分配。因此，很可能是您没有正确识别瓶颈操作，并且所有关于线性复杂度的讨论都没有实际意义，因为您没有衡量正确的事情。

¹ 因为磁带从一个单元格移动到另一个单元格所花费的时间与这些单元格之间的距离成正比，因此不断在内存中跳跃的快速排序算法最终会做很多来回操作而冒泡排序算法只运行磁带长度的 N 次(最大值)。