Probabilistic search - psearch.tar.gz

Wed Apr 5 00:44:09 PDT 2006

"sundaresh" <sundaresh_member at pathlink.com> wrote in message 
news:e0vqej$12o5$1 at digitaldaemon.com...
>I believe that I have replied to this already. My first suspisions was with
> comparisons, but there is nothing wrong with it. Comparisons is updated 
> prior
> to call to the base case psearch, so why should it be updated again during 
> the
> base case, since in the base case, no recursive call to psearch is being 
> made.

That's just it. You don't count how many comparisons it takes to find a 
match, just
how deep it has to go. And with an original size of 512, that always leads 
to
log2(512).

Since you only count the depth of the search, not the amount of comparisons, 
you'll
find it's almost always 9 - it may be shorter, depending on which item was 
randomly picked to be searched for.

> Doing so might actually result in 256 or so as you claim, but that would 
> be
> introducing a bug and not eliminating it.

Frankly, you are so wrong in this. Now you only count the depth, not how 
many items it searches. And it's the items that matter, not the depth. It's 
the amount of comparisons that tells what time the algorithm has - and in 
the case of this, it's most definitely O(N).

> Sorry, these arguments have only served to convince me even further of the
> correctness and workability of this algorithm.

*sigh* A fool, then.

Many have shown you where you've gone wrong, but you seem to be "I'm right 
and I know it, you'd just introduce a bug in it"... If you refuse to listen, 
go ahead.

Mathematically, it is possible to prove that no search of unordered data can 
be done in time less than O(N) - you always have to in the worst case test 
*all* occurences.

I'm attaching an altered version of psearch with this message, so you can 
test it yourself. It's a zip archive with MS-DOS line endings (since that's 
the system I happen to be on). I strongly recommend after unzipping and 
compiling that you invoke it by directing standard output to a file - it's 
going to display so much data on the amount of comparisons it took to find 
something, as well as how it found it. Then you'll see it's not
O(log N) but O(N). 

begin 666 psearch.zip
M4$L#! H``````!=5A30````````````````(````<'-E87)C:"]02P,$% `"
M``@`%E6%-$XL)B*]`0``P at 0``!$```!P<V5A<F-H+W!S96%R8V at N8\5336_;
M, P]V[^"2Q%4CI7LZ[8L'89>B]YZ*U H$1T+<.1 4M9V0_][*4IVC6$8NNTP
M`P9D\I%\[XD^,W;7G31^]D&;?M5>E&>32&>V,50:&V#7'X[*&=];O^; 03W<
M:3R&=EV6WWJC87'TJ-RN%>EKJSQ*B$AOON?3O=&AE9 `V.$!;4 at 9L4@#L,KE
M`ZJJX$=9^*""V3&29\(&WM'<PC0B=H?-!MXSL(@0A_[4!<+DGB)QR0.K-<$F
M<NHZ!HZ.*ALQNQP3,/^HX1/,]:V=R=R3:QV&D[/#E"]P?7-U1< XA-)/98&=
MQY%,J[J&RLV^#;$XJ6KZD]510!'3Q)15O(4/W#]B*::V7CAEM2 /YBEE&A!U
MG2RX>+F"BE+%^$6E^6)>9'T=C)MK":H)Z. at TO50)]WCN$/:]L7L at P0R74TB5
M& CFE]P>^W-L14XQJ&!]Q&-8B>@-U.P%+(8U8,W+;%".C4LQK .WHZ%O@'OF
ML7^F"QIE.M2P?<SRF*V$#L.YA^ >Z=2$U4QR:TC/S\)_+4J^ACZM!+_C7HST
M>>YO79/_PY](:VI/NMV_\><?+GUP;;D<MSG_>?GOH>Q3^0Q02P,$% `"``@`
M]XIZ-.O.;/,A`0``T (``!4```!P<V5A<F-H+W!S96%R8V at N8RYB86NEDDM.
MQ# 01-?V*1HAI'SY+1D"%QBQXP!.W,&6,DYD.R"!YN[8;6?$@L4(%I&2[G+5
M2R67V at S3*O'1>3GI_EH]<:Z-AV$^+,)J-QNWX_Q]UA*JQ:&P at RK24R\<-A"U
M3G_FNP\MO6H@"7#"`QJ?-D65'+',QS=56<(79\X+KP=22ER\@@YN0R[38Q'=
MH>O at CH3,HE^MR7Q8)(H<5<(SO+SN]_ `<;[C[, at 93@[I9#178AH;L/I-^;!E
M"6&<5R-C&HOK$$V1-W ?):0-,]&[P at HCBP!\E58_. at J"NB;RN C4="P1,_(/
MBJV_R 8UL4"U=4:9;0;,LU.#6W?1/+I?`'EF_U\#FG.L0CUTG3KZN]5Y5/]X
M[8VU;4\]YW\A?[^P/?)O4$L#!!0``@`(`!=5A31!QOL!U@```$<!```1````
M<'-E87)C:"]P<V5A<F-H+FA-C<N.PC ,1??Y"DO=T*B"_; !C49BB08T6Q0:
MM[&4.%$>P^/K22E([.Q[CGT;&ECC`/O#S_;W>W?:B::NQ/B1B)6$HZ$$RHX^
M4C8."EM,4Q!1Z1OT/MPBC2:C[J"*Q) -0BAG2SUH[Q3Q4H"$;<G&1_B"0V&M
M(B8#?\AE]$'9B6,U;<7IC3=3L.R]FZA<"8'7C)%K0ZZM+JA(R7-:?^9.74\:
M0S9K(?X]:9 AH8J]6<S;627LGF:B^VNZD,ZF at UE BPXYSV0AYQYL7^=OJVWK
M_P99TR >4$L#!!0``@`(`.B*>C1R_)2\S@```#$!```5````<'-E87)C:"]P
M<V5A<F-H+F at N8F%K38W!:L,P#(;O?@I!+HT)[7V[K(Q!CV4MNPXW5F*!+1O+
M7M<]_9REA=VD__NDOZ.)+4YP/+WMWU\/GP?5M948_R5JI^'L2,#X.68J+D!E
MC[($&8V]P1C3+=/L"MH!FD@,Q2&D>O$T at HW!$&\5:-C7XF*&)SA5MB:C./A 
MKG-,QB\<F^D;E@=^68+M&,-"]4XI_"Z8N364UAJ2R221Y5FIKT at 6=!(T>72;
M=;L8P>'/%?JY3U>RQ0VP"N at Q()>5;/3Z$?O[^</J^_:_0[8TJ5]02P,$% `"
M``@`F(IZ-%'^F>R@!0``JPP``!,```!P<V5A<F-H+W!S96%R8V at N='AT?5?!
MCMLV$#TOOV(*Y+ .!#?(M:<T0-$`05*@R0=0%&412Y$*2=EQO[YO.)2MW:0]
M96V3PYDW[[V9J"])#ZZX&+3WUXY<*#;A;\I6)S.Y<"+M3S&Y,LV9)GVVU%L;
MR.AB^>M_[$ Z4YEBMJ27Q3NC>V^I1*4#Q338A!/9%HHC66]G&THF'8:?7<'W
MM(;_N'14ZLMD:8ZYD(GS',,],QICVF?\,HSC#"UY%W"F'>SH,CDS\6]:9?MM
MQ2.."S><^%@OZ)3TM0;G3X/-CB.VC([T9>++RY*BED A%CK;="4[CLXX/J0^
M!\X'P"5]0L0^K at 4X^OT#%^>]8 L,>N09XQ/>69?Z].C"P%7])(5..8G3/N,R
MGY0"<8RO(RT7[H\=Z1V-.J/+[1 at 5-ULN^"5JBH% -K$O&L -U%]Q)B(2X+!F
M"@Z8 at 0C>XS?CT<T!1>1IBXNWXP*JZ&%(-F<DUJD>Q1=&;;;H_\#)U2OC&@R3
M$ 7BRL"E48[[TO(>(!>R3452FJT.&?DK/OPL6+<5/KH$TBQ>&WNDWP$A8.SX
MEV1K^SV>TI1GE$(1C9JL'AB1:,RZZ&"NZG'D%HW:E)@.('R.QFE.X +Z244;
M#X[T*1;^.A=]:QR8/B1]Z;5YPLN<I;K3E2_3V541L#*6N*P>/$W6Q#5EV]5O
MD:!-+JZ<;]5H<8+',U8C'H3R6>J67DVXW>W4(:U^(8]D?0WH`>B*YGU;G7FR
M29Y.4 =HEU7<<[FC&'#<Q]/;QPPC.+ L%YU<CFC(GKFXLQ$6HF/4^1(_BW^I
MUT#G;:?X)8ZSJ;4P((^5M(?ZPUZQOK$CK'./&O?FTII>KQ_5>[&*>[G"^8V_
M?-SX=8"MN:"AW': DZE>N$0&!A'NKL$%X 6%'UA&2,>>P?,YXON\+MRE5(FZ
MCXBN_(F+#JS\0/;[XOGT)J<E0A^]\ZY<^>+_.-FNT V.&0[26]6$N+0"&'\0
MLM<<-A=GMCS$M>[Z8_C9:Z+ EJQ&_X2V&M2H_J+$IW!Z<&>HIV*#!EPB at 1J:
MS<N?FZ;"3EBA_7Q+I%P[B:O#E4[@6U!WZ_(QG.K#<>>-WM4>D745J6;,_+*\
MR?7LLZY<-I!-);.J\P7Y(J9ED_[A?J7+FH+$,5-TIKJA8"M&O76DD9K-Q&65
MP)$X\P3$70N(\7H"$\#-5F/S_+P:`P,<5[^W7, C0M!UA*%!CZ*$0Q6=JBB.
M4;BVZY>(;)N8SUG[7-H"X/,1^E=E&NZNV69!@^5VL_.FAFX;S$S]W,#(;EX@
M>!-!-%-HT$63@ "@`:,6S>%N$90ZZNNP$Y]"-6@@6V#K\,P'-4%&/(Q*M91A
M38PC"&-D9AS5UVQOB=Z&[:R?:N]X#K Z!5&#9.&Z[>%G8.^ [C@\:%P%I at 8F
MJ![.N(8,`-$?J"]>&I<8^^H#\'Y94>[T(L:C(BL. at 20W]0&-]PAEO[-3<X"]
M-_ZFU#FZ at 5ZWTX_RB;M?%[!F=OS7Q0T%GB,';A[*OSR^EHCVT*YOIPX'I1[^
ME at T@[X2$[*J[WGR22<[AJS" 2>0ZJU(P5249YONV[:B']B &! 20;$EKH#?L
M$!KM*$P_P\C(S/CEC8R?B\M6M'6;\;@*P67UH-NC:9/\Y at 6(Z>I8&N.*6!+Q
MT]>/'_<Q/]Q,P=1DV:<>SL"X:F,_B^I^Q;.(M]878\,5.^?[QM6V3*QI9]ZV
M1AOJ<BQS.<42RW6Q5;G at 6MN+VL#AK8&]O/GL;<%DN%1_DU8]?\5 at WTNL:ROQ
MSS at E2.#2%MGP#I<U'U3(Z92T+,"EF=!&*_Y\-(=M7 KIV:W>B90M77CYC*L?
M>*E"#Q at TA^]=4:_(&'I]-+1E%JJ&T7+D\XJ.O^HC;[)=CXY0FQV\EO-IWDBV
M[?BVHM<:ZI*VK#WJ)OB&YG$HS<9.5-?G^K\+[6'H`UO-<DWN-(&71_4O4$L#
M!!0``@`(`!=5A30C!NGWS $``#@$```.````<'-E87)C:"]T97-T+F.-4U%K
MVS 0?G9^Q=6E(,6B<\H*8TD&&<M#(.W#ZL%H4X(3*XO EHVEA+&1_UY)Y\I*
MZ4,--KI/=Y^^[W2^%');'@H^4;H0]?7^V^ R0$JQ.8.TJ+@%/!(WBN?M=G^]
MCPU8\)V0''XL'K+UW>PWD%&:4@]G/Q>S)>(WZ><OM"_(9M^7\_7#XG$.Y'9T
M0P=":M#YIN1/_=;SN"]8W&==NA+_>+TCIH :0ELGMG75Y"TGQUH4,.0EK[C4
M*8.S>$3A_R"*6JX/K82A)8 A?4V&B^E;;#0>G/" *A>28+D-"Z$T`]V*O&30
MU(J!.E3K3 at 0&!6_TWLB/HEW=$EL`4TC'KA0FOE\() ER1Y%J<UD0VW-R_VNY
MI)"X!#IVNY;*'(=,=C$)^NB0GBF*L)L&?#8%CK>C.;EOTQHK.Q*O)(KZ"E>%
M63M7*VW*5MJ9B%DH(3!J6+U3)\EK=!RH$I>3?A(Z*!2*EO*-(JB2PE7HJ\O"
M4X6JI<VN\K]O3S9$.)G$.6<!!_/CPW#(3%_=O;U.#O44OBNF&[I_X_/[#L2P
M7HMG";N43,/L, /U)X&9]^]G=OP#F(MW9&-+J5P<!P,'G_I&,\<"'W]"T0&/
M,W4R?\(+4$L#!!0``@`(`%9,>C0>&@Y;H@$``'(#```2````<'-E87)C:"]T
M97-T+F,N8F%K;5)=:\(P%'UN?\5=99!H<:UL,%8==,R'@O-A=C V1:J-,]"F
MI8D^;/C?EX_:UK&'EN3DGI-S3VZ/LFUV2,F8BY06P_VCW>L@&=U<0(+F1 $-
MXI2<)-5V/]P[$DS)CC("S]$B7K^$[X!\S\,-'+]&X<S@(^_V'K>$.'R:3=>+
MZ&,*Z,X?89LR`2+99.2S/5H%+2&:QW4YI]^DV"%)P%)0\>BVR,ND(NA8T!3Z
M)",Y8<)SX6+O8_BQ+:LBXE QZ"L!Z.-S,5Q-_F)^8)_,!7E"&3)TM4TI%RZ(
MBB:9"V7!7>"'7'JUK%U1(74*$_ "70?C)AP## 9&R+)XE; 4J8#1_&TVPS#0
M!3C0ITI*:ALEM1AW0M-(JV19)CH)KB1!Z]8R)_TO*^E[AYPE,Z8>X#J5:]W"
M4DC:4J2D%'O'[5J07>GK&S^ZWC at RRW'[Q#74-67L)QN.C",,U]T>ZBKS>)07
MC+>W2;(9,Z0[<SL\MYD%UTR,S$T_PGD,<"/1="V[%>9S+A^N<WE#4VT/)MVC
M_Z,,CU^@4]-Q.GH*X*9-1 N>Y S]`E!+`0(4``H``````!=5A30`````````
M```````(````````````$ ````````!P<V5A<F-H+U!+`0(4`!0``@`(`!95
MA31.+"8BO0$``,($```1``````````$`( ```"8```!P<V5A<F-H+W!S96%R
M8V at N8U!+`0(4`!0``@`(`/>*>C3KSFSS(0$``- "```5``````````$`( ``
M`!("``!P<V5A<F-H+W!S96%R8V at N8RYB86M02P$"% `4``(`" `7584T0<;[
M`=8```!'`0``$0`````````!`" ```!F`P``<'-E87)C:"]P<V5A<F-H+FA0
M2P$"% `4``(`" #HBGHT<OR4O,X````Q`0``%0`````````!`" ```!K! ``
M<'-E87)C:"]P<V5A<F-H+F at N8F%K4$L!`A0`% `"``@`F(IZ-%'^F>R@!0``
MJPP``!,``````````0`@````; 4``'!S96%R8V at O<'-E87)C:"YT>'102P$"
M% `4``(`" `7584T(P;I]\P!```X! ``#@`````````!`" ````]"P``<'-E
M87)C:"]T97-T+F-02P$"% `4``(`" !63'HT'AH.6Z(!``!R`P``$@``````
M```!`" ````U#0``<'-E87)C:"]T97-T+F,N8F%K4$L%!@`````(``@`]P$`
'``</````````
`
end