CLANNAD_WAWA 2014-06-05 08:07 采纳率: 0%
浏览 1019

关于北大在线测试系统(POJ)第1002题

晚辈前不久迷上了POJ,目前已经实现了这题(第1002题),并且优化到了188ms,希望高手能告知进一步优化的方法,我希望能进入100ms以内,多谢前辈们指点!

目前我已经知道性能瓶颈是fgets()这个函数上,它大概花了和排序相同的时间
scanf(),gets()我都试过了,效率没有fgets()高
而fread()在读取stdin的时候又没办法及时地跳出来,所以没法使用
(比如说,用fread从一个只有1000字节的文件中读取10000个字节,那么在读到文件尾后会自动地跳出来。而在读stdin的时候,并不存在所谓的文件尾,它以为你还要不停地输入下去)
排序我这里用的是STL里的sort()函数,应该是非常高效的。

附上代码:

#include
#include
#include
#include

int main (int argc, char * argv[])
{
int n;
char TelTemp[50];
int TelTable[100000];
int i;
int j;

char symbol_table[100];

int Frequency = 1;  
int have_result = 0;

symbol_table['0'] = 0;
symbol_table['1'] = 1;
symbol_table['A'] = symbol_table['B'] = symbol_table['C'] = symbol_table['2'] = 2;
symbol_table['D'] = symbol_table['E'] = symbol_table['F'] = symbol_table['3'] = 3;
symbol_table['G'] = symbol_table['H'] = symbol_table['I'] = symbol_table['4'] = 4;
symbol_table['J'] = symbol_table['K'] = symbol_table['L'] = symbol_table['5'] = 5;
symbol_table['M'] = symbol_table['N'] = symbol_table['O'] = symbol_table['6'] = 6;
symbol_table['P'] = symbol_table['R'] = symbol_table['S'] = symbol_table['7'] = 7;
symbol_table['T'] = symbol_table['U'] = symbol_table['V'] = symbol_table['8'] = 8;
symbol_table['W'] = symbol_table['X'] = symbol_table['Y'] = symbol_table['9'] = 9;

scanf ("%d", &n);
getchar();

for (i = 0; i < n; ++i)
{       
    int times = 6;  
    TelTable[i] = 0;


    fgets (TelTemp, 50, stdin);

    for (j = 0; j < 50; ++j)
    {   
        if (TelTemp[j] != '-')
        {               
            TelTable[i] = TelTable[i] * 10 + symbol_table[TelTemp[j]];
            --times;
            if (times < 0)
            {
                break;
            }
        }       
    }
}

std::sort (TelTable, TelTable + n);


for (i = 0; i < n - 1; ++i)
{
    if (TelTable[i] == TelTable[i + 1])
    {
        ++Frequency;
    }
    else
    {
        if (Frequency >= 2)
        {
            printf ("%03ld-%04ld %d\n", TelTable[i] / 10000, TelTable[i] - TelTable[i] /10000 * 10000, Frequency);
            Frequency = 1;
            have_result = 1;
        }
    }
}
if (Frequency >= 2)
{
    printf ("%03ld-%04ld %d\n", TelTable[i] / 10000, TelTable[i] - TelTable[i] /10000 * 10000, Frequency);
    Frequency = 1;
    have_result = 1;
}
if (have_result == 0)
{
    printf ("No duplicates.");
}
return 0;

}

  • 写回答

1条回答 默认 最新

  • ChatGPTᴼᴾᴱᴺᴬᴵ 2023-03-16 13:12
    关注

    该回答引用ChatGPT

    你已经做得很好了,能够将程序优化到188ms已经非常不错了!不过,还有一些可能可以提高程序性能的方法。

    • 将读入的电话号码直接存储为整数
      目前,你的程序将电话号码读入一个字符数组中,然后通过 symbol_table 将其转换为整数。但是,这个过程需要逐个字符地遍历,所以会比较慢。一个更快的方法是直接将电话号码读入一个整数中。例如,对于电话号码 123-4567,可以将其转换为整数 1234567,这样做的话,就可以省去 symbol_table 的转换,同时也能减少遍历的时间。
    • 尝试使用快速的排序算法
      虽然STL的sort函数在大多数情况下是高效的,但是在一些情况下,它可能会变慢。这种情况通常是由于数据集太大而导致的。在这种情况下,可能需要使用快速的排序算法,例如快速排序或堆排序。这些算法的时间复杂度比STL的sort函数更低,并且能够更快地对数据进行排序。
    • 使用多线程
      如果你的计算机有多个CPU核心,那么可以考虑使用多线程来加速程序。例如,可以将电话号码分成几个块,然后在不同的线程中对它们进行排序。这样做可以利用多个CPU核心并行处理数据,从而更快地完成排序。

    希望这些建议能够帮助你进一步优化程序!

    评论

报告相同问题?

悬赏问题

  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常