我有未排序的整数对，它们表示一些时间间隔（第一个数总是小于第二个数）。问题是为每个时间间隔分配一个整数，即所谓的通道号（0..x），以便不发生冲突的间隔共享同一个通道应使用最少数量的通道。
例如，这些间隔将使用2个通道：
50 100//1
10点70分
80 200/零
我已经用计数排序实现了它，按照第一列对输入进行排序，然后使用线性搜索来查找一对一对的链。我还首先将input*const*数组复制到新数组中，最后将值赋给input数组中的正确位置。
是的，这是我从大学得到的一个作业，它已经实现了，但是有谁能告诉我如何使代码更快使用哪种算法，使排序、链接对将尽可能快输入数组的长度可达1000万个元素。
代码如下：
#include <cstdlib>
#include <cstdio>
#include <iostream>
using namespace std;
struct TPhone
{
unsigned int m_TimeFrom;
unsigned int m_TimeTo;
unsigned int m_Channel;
};
class TElement
{
public:
TPhone m_data;
int index;
TElement(TPhone * const data, int index_)
{
m_data.m_TimeFrom=data->m_TimeFrom;
m_data.m_TimeTo=data->m_TimeTo;
m_data.m_Channel=-1;
index=index_;
}
TElement()
{
}
};
int FindNext(TElement** sorted_general_array, int general_array_size, int index_from)
{
for (int i=index_from+1; i<general_array_size; i++ )
{
if (sorted_general_array[i]->m_data.m_TimeFrom > sorted_general_array[index_from]->m_data.m_TimeTo)
{
if (sorted_general_array[i]->m_data.m_Channel==(unsigned int)-1)
{
return i;
}
}
}
return -1;
}
int AssignChannels(TElement **sorted_general_array, int general_array_size)
{
int current_channel=-1;
for (int i=0; i<general_array_size; i++)
{
if (sorted_general_array[i]->m_data.m_Channel==(unsigned int)-1)
{
current_channel++;
sorted_general_array[i]->m_data.m_Channel=current_channel;
//cout << sorted_general_array[i]->m_data.m_TimeFrom << " " << sorted_general_array[i]->m_data.m_TimeTo << " " << sorted_general_array[i]->m_data.m_Channel << endl;
int next_greater=i;
while (1)
{
next_greater=FindNext(sorted_general_array,general_array_size,next_greater);
if (next_greater!=-1)
{
sorted_general_array[next_greater]->m_data.m_Channel=current_channel;
//cout << sorted_general_array[next_greater]->m_data.m_TimeFrom << " " << sorted_general_array[next_greater]->m_data.m_TimeTo << " " << sorted_general_array[next_greater]->m_data.m_Channel << endl;
}
else
{
break;
}
}
}
}
return current_channel;
}
int AllocChannels ( TPhone * const * req, int reqNr )
{
//initialize
int count_array_size=1700000;
int * count_array;
count_array=new int [count_array_size];
for (int i=0; i<count_array_size; i++)
{
count_array[i]=0;
}
//
int general_array_size=reqNr;
TElement ** general_array;
general_array=new TElement *[general_array_size];
for (int i=0; i<general_array_size; i++)
{
general_array[i]= new TElement(req[i],i);
}
//--------------------------------------------------
//counting sort
//count number of each element
for (int i=0; i<general_array_size; i++)
{
count_array[general_array[i]->m_data.m_TimeFrom]++;
}
//modify array to find postiions
for (int i=0; i<count_array_size-1; i++)
{
count_array[i+1]=count_array[i+1]+count_array[i];
}
//make output array, and fill in the sorted data
TElement ** sorted_general_array;
sorted_general_array=new TElement *[general_array_size];
for (int i=0; i <general_array_size; i++)
{
int insert_position=count_array[general_array[i]->m_data.m_TimeFrom]-1;
sorted_general_array[insert_position]=new TElement;
//cout << "inserting " << general_array[i]->m_data.m_TimeFrom << " to " << insert_position << endl;
sorted_general_array[insert_position]->m_data.m_TimeFrom=general_array[i]->m_data.m_TimeFrom;
sorted_general_array[insert_position]->m_data.m_TimeTo=general_array[i]->m_data.m_TimeTo;
sorted_general_array[insert_position]->m_data.m_Channel=general_array[i]->m_data.m_Channel;
sorted_general_array[insert_position]->index=general_array[i]->index;
count_array[general_array[i]->m_data.m_TimeFrom]--;
delete general_array[i];
}
//free memory which is no longer needed
delete [] general_array;
delete [] count_array;
//--------------------------------------------------
int channels_number=AssignChannels(sorted_general_array,general_array_size);
if (channels_number==-1)
{
channels_number=0;
}
else
{
channels_number++;
}
//output
for (int i=0; i<general_array_size; i++)
{
req[sorted_general_array[i]->index]->m_Channel=sorted_general_array[i]->m_data.m_Channel;
}
//free memory and return
for (int i=0; i<general_array_size; i++)
{
delete sorted_general_array[i];
}
delete [] sorted_general_array;
return channels_number;
}
int main ( int argc, char * argv [] )
{
TPhone ** ptr;
int cnt, chnl;
if ( ! (cin >> cnt) ) return 1;
ptr = new TPhone * [ cnt ];
for ( int i = 0; i < cnt; i ++ )
{
TPhone * n = new TPhone;
if ( ! (cin >> n -> m_TimeFrom >> n -> m_TimeTo) ) return 1;
ptr[i] = n;
}
chnl = AllocChannels ( ptr, cnt );
cout << chnl << endl;
for ( int i = 0; i < cnt; i ++ )
{
cout << ptr[i] -> m_Channel << endl;
delete ptr[i];
}
delete [] ptr;
return 0;
}
最佳答案
如果你希望你的算法快速，你应该尽可能减少搜索此外，您不需要知道哪些间隔是“链接在一起”来为每个间隔确定正确的通道（即，不使用超过绝对必要的通道）以下是我将用于最大性能的步骤/技巧：
像这样定义interval类，添加两个内联函数定义（我为TimeDescriptor使用一个struct只是样式问题，而不是这段代码完全是样式问题）：
typedef struct TimeDescriptor {
unsigned time;
bool isEnd;
} TimeDescriptor;
class TimeInterval {
public:
TimeDescriptor start, end;
unsigned channel;
TimeInterval(unsigned startTime, unsigned endTime) {
start = (TimeDescriptor){ startTime, false };
end = (TimeDescriptor){ endTime, true };
}
}
inline TimeInterval* getInterval(TimeDescriptor* me) {
return (me->isEnd) ? (TimeInterval*)(me - 1) : (TimeInterval*)me;
}
inline TimeDescriptor* getOther(TimeDescriptor* me) {
return (me->isEnd) ? (me - 1) : (me + 1);
}
创建指向所有时间描述符的指针数组，每个时间间隔两个（一个用于开始，另一个用于结束）。
按时间对时间描述符指针数组排序确保使用
isEnd标志作为辅助排序键我不知道间隔冲突是如何定义的，也就是说，两个间隔（20，30）和（30，40）是否冲突，如果它们冲突，用相同的值对开始时间之后的结束时间排序，如果它们不冲突，用相同的值对开始时间之前的结束时间排序。无论如何，我建议您只使用标准的quicksort实现对数组进行排序。
为未使用的通道号创建堆栈这个堆栈的重要之处是：它必须允许您在恒定时间内获取/推送通道号，理想情况下，更新内存中的数字不超过两个；它必须是无底的，即它必须允许您弹出任意数量的值，生成一个整数的升序序列。
实现这样一个堆栈的最简单方法可能是编写一个小类，该类使用
std::vector<unsigned>来存储空闲通道，并跟踪使用过的最大通道数当一个pop请求不能从内部存储器中得到服务时，通过将最大的通道号递增一个来产生一个新的通道号。浏览已排序的时间描述符数组每次遇到开始时间时，获取一个通道号，并将其存储在相应的时间间隔中（使用
getInterval()）每次遇到结束时间时，将其通道号推回到空闲通道阵列上。当您通过时，您的空闲信道堆栈将告诉您同时使用的最大信道数，并且每个时间间隔将包含正确的使用信道号。您甚至可以通过简单地按通道号对timeinterval数组进行排序来高效地计算共享通道的所有间隔链…
关于c++ - 整数的快速排序算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19757146/