寻求最快的算法!!!!

Question

寻求最快的算法!!!!
比较 数组A和数组B相同部分,谁能给我一个最快的算法，多谢了。

Answer 1

我现在这个算法好慢：
for I:=0 to 5000 do
begin
   for J:=0 to 5000 do
   if A[I]=B[J] then
   print '这两个是相同的'; 
end;它比较好好多次!好慢!,你们帮我改进一下

Answer 2

1、先用一遍循环去掉A数组中相同的部分，如：
   9845613432 将变成
   98456132
   也就是每种重复的元素只保留一个！！记住每个重复元素的下标。如：
   98456132
   ------------------
   01234569
       7 8
2、对新的A数组与数组B比较。
   如果B[x]=9，则输出一个'A[0]=B[x]'
   如果B[x]=5，则输出一个'A[3]=B[x]'
   如果B[x]=6, 则输出'A[4]=B[x]'和'A[7]=B[x]'
   如果B[x]=3, 则输出'A[6]=B[x]'和'A[8]=B[x]'
   ...试试吧，我也不知道有必要这么麻烦吗？

Answer 3

5000*5000 复杂度太高了,复杂度 O(n^2)笨的办法就是先将2个数组排序，然后比较
快速排序的复杂度还好像是 O(nlog2n)，最坏 O(n^2)两个都排序，然后再循环一遍比对。

Answer 4

5000*5000 复杂度太高了,复杂度 O(n^2)笨的办法就是先将2个数组排序，然后比较
快速排序的复杂度还好像是 O(nlog2n)，最坏 O(n^2)两个都排序，然后再循环一遍比对。

Answer 5

1 什么叫比较相同部分？看你的代码是求两个集合（数组）的交集。
2 重复元素如何处理？pazee(耙子)兄的方法最后一步可改为模拟归并排序，复杂度在O(n)，总算法复杂度 O(n*lgn)。

Answer 6

至于 pazee所说的都排好序，可是排序所用的时间也很长呀
A[0]=0,A[1]=1,A[2]=1,A[4]=1,A[3]=3,A[5]=4 .........B[0]=0,B[1]=0,B[2]=0,B[3]=0,B[5]=0,B[6]=3,B[4]=9 ........B数组和A数组相同部分就是[0,1,2,3,5,6]这就是我所要求的.
我的意思是从B中找出A中有相同值的数

Answer 7

>>
A[0]=0,A[1]=1,A[2]=1,A[4]=1,A[3]=3,A[5]=4 .........B[0]=0,B[1]=0,B[2]=0,B[3]=0,B[5]=0,B[6]=3,B[4]=9 ........B数组和A数组相同部分就是[0,1,2,3,5,6]这就是我所要求的.
我的意思是从B中找出A中有相同值的数
>>这叫什么交集,你是要求下标,那就不能排序了

Answer 8

jinjazz
是的我就是要求下标,不能排序那怎么办

Answer 9

你可以先把A排序,循环用二分查找在A中找B[i]算法复杂度还是在 O(n*lgn)。

Answer 10

program Project2;{$APPTYPE CONSOLE}uses
  SysUtils;
var a,b:Array[0..4999] of integer;
    i:integer;
{快速排序}
procedure QuickSort(var SortNum:array of integer;p,r:integer);
  procedure swap(var a,b:integer);  //交换
  var tmp:integer;
  begin
    tmp:=a;
    a:=b;
    b:=tmp;
  end;
  function partition(var SortNum:array of integer;p,r:integer):integer; //划分
  var i,j,x:integer;
  begin
    i:=p;j:=r+1;
    x:=SortNum[p];
    while true do
    begin
      repeat inc(i)
      until SortNum[i]>=x;
      repeat inc(j,-1)
      until SortNum[j]<=x;
      if i>=j then break;
      swap(SortNum[i],SortNum[j]);
    end;
    SortNum[p]:=SortNum[j];
    SortNum[j]:=x;
    result:=j;
  end;
var q:integer;
begin
  if p<r then
  begin
    q:=partition(SortNum,p,r);
    QuickSort(SortNum,p,q-1);
    QuickSort(SortNum,q+1,r);
  end;
end;
{二分查找}
function BinarySearch(SearchNum:array of integer;x,n:integer):integer;//序列,值,序列长度
var left,right,mid:integer;
begin
  result:=-1;
  left:=0;right:=n-1;
  while(left<=right)do
  begin
    mid:=(left+right) div 2;
    if x=SearchNum[mid] then
    begin
      result:=mid;
      exit;
    end;
    if x>SearchNum[mid] then left:=mid+1
                        else right:=mid-1
  end;
end;begin
  { TODO -oUser -cConsole Main : Insert code here }
Writeln('按回车键开始初始化');
Readln;
Writeln('正在初始化..');
for i:=0 to 4999 do
begin
  randomize;
  a[i]:=random(5000);
  randomize;
  b[i]:=random(5000);
end;
Writeln('初始化结束');
Writeln('按回车键开始查找');
Readln;
Writeln('正在排序...');
QuickSort(a,0,4999);
Writeln('正在查找...');
for i:=0 to 4999 do
begin
  if BinarySearch(b,b[i],5000)>0 then
  Writeln(a[i]);
end;
Writeln('按回车键退出');
Readln;
end.

Answer 11

和A中有没有重复元素是没有关系的对A排序时间花费O(n*Logn)
查找时间花费也是O(n*Logn)

Answer 12

O(n*Logn)????是什么呀？
是不是:0*(n*logn)?
logn,是不是以为10底数n为指数?

Answer 13

jinjazz
我看了你的理论，从理论上分析我认为它确实提高了一半的速度，如果原来是要30秒，现在按你的方法应只要15秒，归根还是二分法比每个元素都对比一次是快。
你数学一定学得不错

Answer 14

等中午我也测试一下看，GetTickCount前后用了多少时间

Answer 15

这样的问题在noi教学中属于基础问题，当你要看一个元素是否在一个集合中时，利用Hash散列表的效率最高。代码我已经写好了，复杂度：5000+5000。delphi5下通过:
program AB5000;
{$APPTYPE CONSOLE}const
  MaxVal = 30000;var
  a, b: array [0..5000] of Integer;
  d: array [0..MaxVal-1] of Byte;
  i: Integer;begin
  // 向数组a,b中填入随机数据。
  Randomize;
  for i:=0 to 5000 do
  begin
    a[i] := Random(MaxVal);
    b[i] := Random(MaxVAl);
  end;  // 清空Hash表
  FillChar(d, 30000*Sizeof(Byte), 0);
  // 构造数组a的Hash表
  for i:=0 to 5000 do
    Inc(d[a[i] mod MaxVal]);
  // 在数组a的Hash表中查找数组b的元素
  for i:=0 to 5000 do
    if d[b[i] mod MaxVal]<>0 then
      Write(b[i], ' ');
  Writeln;
  Readln;
end.

Answer 16

这不是我的理论-_-!!上面有点错误，应该这样调用
for i:=0 to 4999 do
begin
  if BinarySearch(a,b[i],5000)>0 then
  Writeln(i);
end;

Answer 17

QuickKeyBoard的办法很好。面对array of string就不是这么作的了。：）

Answer 18

在这里感谢jinjazz和kiboisme的称赞，我是一名noi教练，所以算法类的问题应该不是问题，但对于工业控件与团队开发，就需要努力学习了 :<然后我回答kiboisme提出的问题，如果是字符串数组的话，那么，改变一下Hash函数即可。我上面用的Hash函数是“求余数”，对于字符串，可以考虑使用执行连接格式(ELF)Hash函数，代码如下：
function ELFHash(var s: String): Integer;
var
  g, h, i: LongWord;
begin
  h := 0;
  for i:=1 to Length(s) do
  begin
    h := h shl 4 + Ord(s[i]);
    g := h and $f0000000;
    if g <> 0 then
     h := h xor (g shr 24);
    h := h and (not g);
  end;
  ELFHash := h mod M;
end;
这个Hash函数最早用于Unix系统的文件系统，对长短字符串都很有效，对不同的s，冲突的概率非常的小。其中的M是Hash表的大小。
不知这样的解释kiboisme是否满意。

Answer 19

@_@
开一天会，帖子居然顶这么高了：）
虽然还是不太明白mynameisking(isking)想做什么，不过QuickKeyBoard()的回答让人受益匪浅。
如果是要找数组下标或者考虑重复元素，可以用外Hash表（好像概念是这样叫吧@_@，在Hash表的每个表项链接一个队列/链表）的形式。

Answer 20

佩服，抄袭一下...问一句，字符串的话，哈希表大小如何确定？？该不会是f0000000吧
program AB5000;
{$APPTYPE CONSOLE}const
  MaxVal = 300000;const
  a: array [0..5] of string=('aba','bcd','afa','agwe','aaf','abweb');
  b: array [0..5] of string=('aba','bcd','dfe','agwe','aaf','abweb');
var
  d: array [0..MaxVal-1] of Byte;
  i,m: Integer;
function ELFHash(s: String): Integer;
var
  g, h, i: LongWord;
begin
  h := 0;
  for i:=1 to Length(s) do
  begin
    h := h shl 4 + Ord(s[i]);
    g := h and $f0000000;
    if g <> 0 then
     h := h xor (g shr 24);
    h := h and (not g);
  end;
  Result := h mod MaxVal;
end;
begin
  // 清空Hash表
  FillChar(d, MaxVal*Sizeof(Byte), 0);
  // 构造数组a的Hash表
  for i:=0 to 5 do
   inc(d[ELFHash(a[i])]);
  // 在数组a的Hash表中查找数组b的元素
  for i:=0 to 5 do
    if d[ELFHash(b[i])]<>0 then
      Write(b[i], ' ');
  Writeln;
  Readln;
end.

Answer 21

2 jinjazz(近身剪（N-P攻略）)
关于Hash表的大小确定，和元素的个数有关系。
没有记错的话似乎在n/2的时候比较好，而在n/3以后conflict会非常严重从而影响效率。

Answer 22

QuickKeyBoard，呵呵，看来对算法的研究不错，
一点个人意见：一个整数（那怕是int64)来唯一标识一个字符串，必然有冲突，int64：也最多只能标识别1 shl (Sizeof(Int64)*8-1这么多个字符串，一旦发生重复，必然导致错误。当然这个概率确实非常小。

Answer 23

to firetoucher(风焱) 
你还不明白呀？(:
在mynameisking(isking)中说到
“几乎跟找素数是相同的道理。
从B中找出能整除A中某一个数的数而且要求商一定是1”
这下你明白了吧

Answer 24

我正在慢慢看 QuickKeyBoard() 的Hash散列表问题，快不快还得看最后TEST结果

Answer 25

2 firetoucher:我把上面MaxVal = 300000 改为MaxVal = 30000 就出错了:(

Answer 26

to：mynameisking不用test了，空间换时间，hash肯定是最快的，查找一个元素只需要常量时间

Answer 27

已经test出结果了，果然 QuickKeyBoard() 的算法提高了2500倍的速度!
现在我要公布 QuickKeyBoard() 的原理为什么它的原理只循环2次个5000?原理如下：1、它做了一个全是0的很大数组
         2、然后A把以余数为下标保存下去
         3、然后B再以余数对比已经存在的(D数组为0的当然是不相同)
         4、所以速度飞快thanks to QuickKeyBoard()

Answer 28

to QuickKeyBoard()
请愿晾，我对你的算法改造一下：其实不用余数的，直接用值就可以了  FillChar(d, 30000*Sizeof(Byte), 0);
  for i:=0 to 5000 do
    Inc(d[a[i]]);
  for i:=0 to 5000 do
    if d[b[i]]<>0 then
      Write(b[i], ' ');

Answer 29

2 kiboisme(蓝色光芒) & jinjazz(近身剪（N-P攻略）)
hash函数发生冲突很正常，可以用外Hash表。在Unix中都是这样做的。看上面的回复回复人： firetoucher(风焱) ( ) 信誉：232  2004-12-22 11:33:00  得分: 0  
 
 
   @_@
开一天会，帖子居然顶这么高了：）
虽然还是不太明白mynameisking(isking)想做什么，不过QuickKeyBoard()的回答让人受益匪浅。
如果是要找数组下标或者考虑重复元素，可以用外Hash表（好像概念是这样叫吧@_@，在Hash表的每个表项链接一个队列/链表）的形式。  
 

Answer 30

2 mynameisking(isking) 
sigh，除非你a b的值范围确定并且不大于d(即hash表)，否则必须用mod

Answer 31

脸红一个，好像hash不是分“内”“外”,而是开散列和闭散列。
太久了，concept都混淆了,sorry 2 all。

Answer 32

to firetoucher
我们都会知道我们值的范围吧,无非就是整数范围内，大不了就在double范围内,(:改进是字符串：
a,b:array[0..4999]of string;
d:array[0..99999999999]of string;FillChar(d, 30000*Sizeof(Byte), 0);
  for i:=0 to 5000 do
    Inc(d[a[i]]);
  for i:=0 to 5000 do
    if d[b[i]]<>0 then
      Write(b[i], ' ');同样可用

Answer 33

这样的讨论应该作个标志，呵呵。To: mynameisking(isking)
>O(n*Logn)????是什么呀？
>是不是:0*(n*logn)?
>logn,是不是以为10底数n为指数?呵呵，这个不是说零乘于什么？这是数据结构里面用来评估表示算法效率的一种方法。
O(n*Logn)表示你的时间复杂度，你的数组大小为n，则耗费的时间是和n*Log(n)成大致正比的。
如果你的是O(n^2)，就说明数组为n大小的时候，耗费的时间和n的2次方成正比，这个算法肯定会比上面哪个O(n*Logn)的慢（在同等n下面比较），而且n越大，这是时间增正得越大！
时间复杂度的估算，是根据你的核心运算/操作的循环次数来计算的。
例如你这个：
for I:=0 to 5000 do
begin
   for J:=0 to 5000 do
   if A[I]=B[J] then
   print '这两个是相同的'; 
end;显然是5000*5000次比较，也就是n*n 或者n^2前面这个是英文的O，不是零，是一种记法。

Answer 34

求余的话，如果MaxV取得不够大，则Hash表里面有相重的，也就是大于2的元素，这是还得额外判断是否一样吧？如果不求余直接用数，则如果MavV取得不够，那么Hash表里面就没有位置放了。

Answer 35

另外，昨晚看了这样的一个帖子：
http://community.csdn.net/Expert/topic/3639/3639861.xml?temp=1.613796E-03今天看了几位在这里讨论Hash的问题，突然灵光一下，或许用hash也能解决这个问题，就是要到后来分析hash表的稀疏程度吧？用线性代数？都还给老师了，也许大家可以去看看，会有好的办法。

Answer 36

QuickKeyBoard()  的hash散列是不可挑踢的了,jinjazz的二分法也不错.
结帐了

Answer 37

http://blog.blogchina.com/article_75061.366777.html
十分值得一看

Answer 38

QuickKeyBoard的算法真是太巧妙了！并且为人那么谦虚，难得！

Answer 39

不用什么算法就能很快实现的。前提是这两数组是结构相同的。1。把两个数组存成文本文件一个叫A、一个叫B
2。调用win32的FC命令，或者从网上下载其它的文件比较命令
3。在程序里调用这个命令，通过管道命令把结果存成文件

Answer 40

我的改进？？
program AB5000;
{$APPTYPE CONSOLE}const
  MaxVal = 30000;//根据可用存储空间定
//如果为String
function ELFHash(var s: String): Integer;overload;
var
  g, h, i: LongWord;
begin
  h := 0;
  for i:=1 to Length(s) do
  begin
    h := h shl 4 + Ord(s[i]);
    g := h and $f0000000;
    if g <> 0 then
    h := h xor (g shr 24);
    h := h and (not g);
  end;
  ELFHash := h mod MaxVal;
end;
//如果为integer
function ELFHash(var i: integer): Integer;overload;
begin
  ELFHash := i mod MaxVal;
end;
type
  Thash = record
    num: integer;
    index: integer; //num = 1存放A[]的index, num > 1 存放 Tlist指针
  end;
var
//  a, b: array [0..5000] of Integer;
  a, b: array [0..5000] of string;
  d: array [0..MaxVal-1] of Thash;
  i,j,k: Integer;
  templist: Tlist;begin
  // 向数组a,b中填入随机数据。随机数据>MaxVal
{ }  // 清空Hash表
{  FillChar(d, 30000*Sizeof(Byte), 0);}
  // 构造数组a的Hash表
  for i:=0 to 5000 do
  begin
    j := ELFHash(a[i]);
    inc(d[j].num);
//以下是针对ELFHash函数造成的重复的处理
    case d[j].num of
      1: d[j].index := j;
      2: begin
        templist := tlist.create;
        templist.add(pointer(d[j].index));
        d[j].index := integer(templist);
      end;
      >2: Tlist(d[j].index).add(pointer(d[j].index));
    end;
  end;
  // 在数组a的Hash表中查找数组b的元素
  for i:=0 to 5000 do
  begin
    j := ELFHash(b[i]);
    case d[j].num of
    0:;//不相同
    1: if a[d[j].index] = b[i] then
      相同(b[i], i,a[d[j].index],d[j].index);
    >1:begin
      templist := tlist(d[j].index);
      for k:=0 to templist.count-1 do
        if a[integer(templist[k])] = b[i] then
  相同(b[i], i,a[integer(templist[k])],integer(templist[k]));
      end;  
    end;
  end;
  //释放Tlist
  for i := 0 to MaxVal -1 do
    if d[i].num > 1 then
      tlist(d[j].index).free;
end.