[请教!] 求IP的冒泡排序的最优化算法....急~~(200分)

  • 主题发起人 主题发起人 淡淡的笑
  • 开始时间 开始时间

淡淡的笑

Unregistered / Unconfirmed
GUEST, unregistred user!
[:(]
有记录IP的LOG文件如下:
211.91.114.119
211.91.134.229
61.215.174.22
61.174.21.144
....
一共有10万多行,求冒泡排序算法..用普通的算法,,P4 1.4G上,竟然要用到60000多秒..
而我还有一大堆这样的文件要处理..70多M吧...这个10万行的LOG只不过才1.5M左右...
要求排序后的结果如下(以上例):
61.174.21.144
61.215.174.22
211.91.114.119
211.91.134.229
....
感谢~~~
 
我的算法部分代码
代码:
procedure TForm1.Button2Click(Sender: TObject);
var
  MyFile:textfile;
  MyStr:array of String;
  MyTmp:string;
  i,j,Y:integer;
  kkk,jjj:int64;
  flag:boolean;
begin
  if form1.OpenDialog1.Execute then
  begin
    AssignFile(MyFile,form1.OpenDialog1.FileName);
    Reset(MyFile);
    Y:=-1;
    While Not EOF(MyFile) do
    begin
      Readln(MyFile,MyTmp);
      Y:=Y+1;
    end;
    CloseFile(MyFile);
    setlength(MyStr,Y+2);
    AssignFile(MyFile,form1.OpenDialog1.FileName);
    Reset(MyFile);
    try
      i:=0;
      while not Eof(MyFile) do
      begin
        Readln(MyFile,MyStr[i]);
        Inc(i);
      end;
    finally
      CloseFile(MyFile);
    end;
    try
        For j:= Y do
wnto 0 do
        begin
            flag:=False;
            For i:= 0 to Y do
            begin
              if(strlen(pchar(MyStr[i+1]))<5) then
 MyStr[i+1]:='00000000000000000000000000000';
              label1.caption:=inttostr(j);
              application.ProcessMessages;
              kkk:=strtoint64(copy(MyStr[i],1,3)+'000000')+strtoint64(copy(MyStr[i],5,3)+'000')+strtoint64(copy(MyStr[i],9,3));
              jjj:=strtoint64(copy(MyStr[i+1],1,3)+'000000')+strtoint64(copy(MyStr[i+1],5,3)+'000')+strtoint64(copy(MyStr[i+1],9,3));
              if kkk<jjj then
              begin
                  mytmp:=MyStr[i];
                  MyStr[i]:=MyStr[i+1];
                  Mystr[i+1]:=Mytmp;
                  flag:=True;
              end;
            end;
        if Flag=False then
 break;
        end;
        copyfile(pchar(ExtractFileName(OpenDialog1.FileName)),pchar(ExtractFileName(form1.OpenDialog1.FileName)+'.bak'),False);
        AssignFile(MyFile,form1.OpenDialog1.FileName);
        Rewrite(MyFile);
        try
          For i:= 0 to Y do
          begin
            writeln(MyFile,MyStr[i]);
          end;
        finally
          CloseFile(MyFile);
        end;
        button2.caption:='完成!';
    finally
        MyStr:=nil;
    end;
  end;
end;
在转换int to str;str to int时可能浪费了部分效率,,求解! 谢谢
 
我有一個辦法,把ip的四個部分變成一個數據庫表的四個字段,
建一個四個字段的索引,搞定!
哦!對!最後倒出到文本文件!!!
 
to luyear: 能否具体点?? 比如这个索引,,比较难办..
order by ?????
 
不能从根本上解决问题
211.91.114.119 ->211.091.114.119
211.91.134.229 ->211.091.134.229
61.215.174.22 ->061.215.174.022
然后直接使用字符串比较就行了。
建议你导入到数据库里面去,用batchmov,然后建立索引,一下子就排序出来了。
 
Adnil说的很清楚了,直接把这个文件当作TXT的文件里面是字符类型的数据
直接导入数据库就可以了,接下去就很简单了。
 
虽然我们可以简单的做出通用QUICKSORT函数,但是为了让弟兄们
更简单,我们可以直接使用DELPHI的THREAD例子里的QUICKSORT
procedure QuickSort(var A: array of Integer;
iLo, iHi: Integer);
var
Lo, Hi, Mid, T: Integer;
begin
Lo := iLo;
Hi := iHi;
Mid := A[(Lo + Hi) div 2];
repeat
while A[Lo] < Mid do
Inc(Lo);
while A[Hi] > Mid do
Dec(Hi);
if Lo <= Hi then
begin
// VisualSwap(A[Lo], A[Hi], Lo, Hi);
T := A[Lo];
A[Lo] := A[Hi];
A[Hi] := T;
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if Hi > iLo then
QuickSort(A, iLo, Hi);
if Lo < iHi then
QuickSort(A, Lo, iHi);
// if Terminated then
Exit;
end;

现在的算法是,先将IP转换成整数.我们取名为IP2INT
例如一个IP地址为: 1.2.3.4
那么这个整数是
VAR I:INTEGER;
PBYTE(@I)^:=4;
PBYTE(@i+1)^:=3;
PBYTE(@i+2)^:=2;
PBYTE(@i+3)^:=1;
或者我们可以用I:=1*256*256*256+2*256*256+3*256+4;
现在我们只需要创建好一个整数数组,
我们可以建立
VAR STRLST:tsTRINGLIST;
ARR:ARRAY OF INTEGER;
begin

STRLST:=TSTRINGLIST.CREATE;
STRLST.LOADFROMFILE(FILENAME);
SETLENGTH(ARR,STRLST.COUNT);
FOR I:=0 TO STRLST.COUNT-1 do
begin
ARR:=IP2INT(STRLST.STRINGS);
end;
QUICKSORT(ARR,0,LENGTH(ARR)-1);
现在已经是排好序列的ARR了
我们只需要把整数再换回IP字符串
整数变回IP字符串就不用说了
用这样的方法,我想速度应该可以做到秒级
BTW:这个题目有问题,不是求冒泡算法,应该是求算法
 
[blue]同意Adnil的做法。先导入数据库,然后再做就很容易了。,[/blue]
 
以下为个人看法
1.用数据库来做的方法不是很好,会很慢的.
2.用内存文件可免于每次从磁盘读取文件
3.wenyue的说法应该是可行的.
4.个人认为最好是用整数来排序(字符串的处理就没这么快了),用inet_addr先把ip地址转成整数.再用hill等较优的算法来
排,冒泡怕是不行的,太慢.
5.建议c来实现
 
首先,将字符串形式的ip地址转换成整数形式再排序会快不少
其次,从需排序的数量来看,问题的关键在于外排序的策略
所以使用堆排序是比较合适的
具体算法可参看清华大学严蔚民老师的数据结构或是
由北大的张铭译的Shaffer的数据结构与算法分析
 
多人接受答案了。
 

Similar threads

S
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
I
回复
0
查看
473
import
I
后退
顶部