Re^15: [OT] The interesting problem of comparing (long) bit-strings.

$ for i in 99999996 99999997 99999998 99999999; do for j in 1999 2001 
+2002 2003 2004; do echo $i $j; ./bitstrstr test.dat $i $j 100; done; 
+done
99999996 1999
needle found at 99999996, expected at 99999996 in 11.7/100 = 0.117ms
99999996 2001
needle found at 99999996, expected at 99999996 in 11.7/100 = 0.117ms
99999996 2002
needle found at 99999996, expected at 99999996 in 11.6/100 = 0.116ms
99999996 2003
needle found at 99999996, expected at 99999996 in 12.1/100 = 0.121ms
99999996 2004
needle found at 99999996, expected at 99999996 in 12/100 = 0.12ms
99999997 1999
needle found at 99999997, expected at 99999997 in 11.5/100 = 0.115ms
99999997 2001
needle found at 99999997, expected at 99999997 in 13.2/100 = 0.132ms
99999997 2002
needle found at 99999997, expected at 99999997 in 11.5/100 = 0.115ms
99999997 2003
needle found at 99999997, expected at 99999997 in 11.8/100 = 0.118ms
99999997 2004
needle found at 99999997, expected at 99999997 in 11.6/100 = 0.116ms
99999998 1999
needle found at 99999998, expected at 99999998 in 911.9/100 = 9.119ms
99999998 2001
needle found at 99999998, expected at 99999998 in 12.2/100 = 0.122ms
99999998 2002
needle found at 99999998, expected at 99999998 in 13.2/100 = 0.132ms
99999998 2003
needle found at 99999998, expected at 99999998 in 11.7/100 = 0.117ms
99999998 2004
needle found at 99999998, expected at 99999998 in 12.6/100 = 0.126ms
99999999 1999
needle found at 99999999, expected at 99999999 in 12/100 = 0.12ms
99999999 2001
needle found at 99999999, expected at 99999999 in 912.1/100 = 9.121ms
99999999 2002
needle found at 99999999, expected at 99999999 in 12.5/100 = 0.125ms
99999999 2003
needle found at 99999999, expected at 99999999 in 12.6/100 = 0.126ms
99999999 2004
needle found at 99999999, expected at 99999999 in 12.2/100 = 0.122ms
[download]

Comment on Re^15: [OT] The interesting problem of comparing (long) bit-strings. Download Code

Replies are listed 'Best First'.
Re^16: [OT] The interesting problem of comparing (long) bit-strings. by BrowserUk (Patriarch) on Mar 31, 2015 at 13:44 UTC
You're pre-shifting the entire haystack and/or entire needle to align them before searching? (And not counting the time that takes?) With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked	[reply]
Re^17: [OT] The interesting problem of comparing (long) bit-strings. by salva (Canon) on Mar 31, 2015 at 13:51 UTC
Yes and no. My code is pre-aligning the needle to a byte boundary, but it never takes advantage of that... actually, it is aligning it on the wrong side!	[reply]
Re^18: [OT] The interesting problem of comparing (long) bit-strings. by BrowserUk (Patriarch) on Mar 31, 2015 at 14:10 UTC
My code is pre-aligning the needle to a byte boundary, That would, for my purposes, mean that the entire needle would need to be copied, and the time taken counted. The reason is hinted at in the 6 argument function signature() I posted in the OP: `U64 bsSearch( U64 hay, U8 oHay, U64 lHay, U64 ndl, U8 oNdl, U64 lNdl + );` [download] Both the haystack and needle will be subsections of -- potentially much larger -- bitstrings; and shifting them in-place is not on, because they are effectively just windows into the parent bitstrings -- think substr refs. (Though I guess you might* be able to rotate them in place -- rotate so that no bits are lost -- then rotate them back afterwards; but again, the time taken would have to be counted.). That's why I'm now recoding in OO-style; so that the function signature can become: `bvSearch( BV hay, BV ndl );` and I can hide the nasty offsets, cross-boundary manipulations and (in particular) end-of-bitstring sub-64-bit bits behind the curtains. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked	[reply] [d/l] [select]