home *** CD-ROM | disk | FTP | other *** search
/ Gold Fish 3 / goldfish_volume_3.bin / files / dev / e / amigae / src / class / hash / hashtest.e < prev   
Text File  |  1992-09-02  |  2KB  |  59 lines
  1. /* test hashing functions
  2.  
  3. identifiers are generated in amounts of 10,100,1000, which are
  4. then hashed with tables of size 1, 211, 941, 3911 and 16267.
  5. Displayed are the average number of StrCmp()'s needed to find
  6. any of these identifiers.
  7.  
  8. */
  9.  
  10. MODULE 'class/hash'
  11.  
  12. RAISE "MEM" IF String()=NIL
  13.  
  14. PROC main()
  15.   DEF heavy:PTR TO LONG,a,b,l,num:PTR TO LONG,t=NIL:PTR TO hashtable,
  16.       c,ll,n,h,link:PTR TO hashlink,rs[10]:STRING
  17.   heavy:=[1,HASH_NORMAL,HASH_MEDIUM,HASH_HEAVY,HASH_HEAVIER]
  18.   num:=[10,100,1000]
  19.   l:=genidents(1000)
  20.   WriteF('numidents:')
  21.   FOR b:=0 TO 2 DO WriteF('\t\d\t',num[b])
  22.   WriteF('\ntablesize:\n')
  23.   FOR a:=0 TO 4
  24.     WriteF('[\d]\t\t',heavy[a])
  25.     FOR b:=0 TO 2
  26.       NEW t.hashtable(heavy[a])
  27.       ll:=l
  28.       FOR c:=1 TO num[b]
  29.         n,h:=t.find(ll,EstrLen(ll))
  30.         t.add(NEW link,h,ll,EstrLen(ll))
  31.         ll:=Next(ll)
  32.       ENDFOR
  33.       WriteF('\s[8]\t',RealF(rs,t.calc_hash_spread(),4))
  34.       END t
  35.     ENDFOR
  36.     WriteF('\n')
  37.   ENDFOR
  38. ENDPROC
  39.  
  40. -> generate some random identifiers
  41.  
  42. PROC genidents(n)
  43.   DEF l=NIL,a,s[100]:STRING,x:PTR TO LONG,len,prt,b,y
  44.   x:=['bla','burp','e_','pom','ti','dom','aap','noot','mies']
  45.   len:=ListLen(x)
  46.   FOR a:=1 TO n
  47.     StrCopy(s,'')
  48.     StrAdd(s,(y:=Rnd(26)+"A") BUT {y}+3,1)
  49.     StrAdd(s,(y:=Rnd(26)+"a") BUT {y}+3,1)
  50.     StrAdd(s,(y:=Rnd(26)+"A") BUT {y}+3,1)
  51.     prt:=Rnd(3)+1
  52.     FOR b:=1 TO prt DO StrAdd(s,x[Rnd(len)])
  53.     StrAdd(s,(y:=Rnd(26)+"A") BUT {y}+3,1)
  54.     StrAdd(s,(y:=Rnd(26)+"a") BUT {y}+3,1)
  55.     StrAdd(s,(y:=Rnd(26)+"A") BUT {y}+3,1)
  56.     l:=Link(StrCopy(String(EstrLen(s)),s),l)
  57.   ENDFOR
  58. ENDPROC l
  59.