Comparing strings from the back?

S

Steve Howell

It's exactly right. You can obtain this result analytically from
Johannes' formula above. Just replace 256 with 10 to get that the
expected number of comparisons is

(10/9)*(1 - 10**(-N))

The math here is simple, but of course the average running time is
also driven by usage patterns.

Let's say you have two independently produced strings with N number of
random bits. The average amount of bit comparisons that it takes to
determine that the strings are different is between 1 and 2 checks for
any value of N, for the same reason that the average number of times
you need to flip a coin before either coming up heads or exhausting
your N tries is always less than 2, and pretty darn close to 2 for
even relatively small values of N.

def compute_checks_for_different_strings(n):
x = 1
p = 0.5
for i in range(0, n):
x += p * i
p = p * 0.5
print n, x

for n in [10, 100, 1000, 10000]:
compute_checks_for_different_strings(n)

10 1.9892578125
100 2.0
1000 2.0
10000 2.0


Now let's say your string comparison function is used to verify 100-
bit passwords, and 99% of the time the password is from a legit user
who types it correctly. Except for the 1% of a time when somebody fat
fingers the copy/paste of their password, every strcmp call is gonna
have to compare 100 pairs of characters, or N pairs. If the usage
pattern says that 99% of the time you're simply verifying that two
strings are equal, then the number of bits is the main driving factor
for running time.
 
A

alex23

If you're unsure if it was racist, you should err on the side of
caution.

If your comments are mistakable as racism, maybe *you* should be more
cautious and *not make them*.
 
C

Chris Angelico

If your comments are mistakable as racism, maybe *you* should be more
cautious and *not make them*.

That applies to the most obvious examples (for instance, there's a
line in a 19th century opera that uses a six-letter word starting with
'n' to refer to a dark-skinned person - for obvious reasons, that line
is usually changed in modern performances, even though it was
descriptive and not offensive when the opera was written - like
referring to a Caucasian). However, there are many things which could
be misinterpreted as racist, and I would hate to see people leaned
hard on to make their speech entirely politically correct. Use common
sense, on both sides. Don't be offensive, and don't be offended.

ChrisA
 
A

alex23

I would hate to see people leaned
hard on to make their speech entirely politically correct. Use common
sense, on both sides. Don't be offensive, and don't be offended.

While I would like to agree, this would require there to be no power
disparities between the parties involved, which isn't always the case.
I hate the term "politically correct", it always seems to be used in
an eye-rolling, "what a load of nonsense" way, probably because I
believe there's at least some validity in the Sapir/Whorf hypothesis
that language dictates thought.

If Ramit's name was Barbie and e was told to "get back to your dream
home" or some other guff, it would be quite rightly viewed as sexist,
whether intentional or not. Such behaviour has been called out on this
list in the past, and I'm genuinely surprised to see so little
reaction to this.
 
E

Ethan Furman

Neil said:
Ethan Furman:

I can't work out who you are plonking. While more than one of the
posters on this thread seem worthy of a good plonk, by not including
sufficient context, you've left me feeling puzzled. Is there a guideline
for this in basic netiquette?

You're right, my apologies. Dwight Hutto is the one I plonked. His
signal to noise ratio seems incredibly low.

alex23 can definitely be abrasive, but his ratio is high.

(Now I'm wondering what that says about me as far as who I agree with
and why... I'll have to think about that.)

~Ethan~
 
D

Dwight Hutto

You're right, my apologies. Dwight Hutto is the one I plonked. His signal
to noise ratio seems incredibly low.

Is this just because of the lack of context, or because of the content
of my response to the OP following the question?

And with all the netiquette talk being passed around, why isn't this a
new thread instead of hijacking the OP's original question, and
engaging in bickering about netiquette that goes
on all the time?

And it seems redundant to argue this topic other than to comment, and
let it pass, unless there's seems to be a legitimate reason why
someone 'disobeyed' posting policy.
 
D

Dwight Hutto

You're right, my apologies. Dwight Hutto is the one I plonked.
You can call me David. I go by my middle name.

And it seem to me I made some valid points about a few simple trimming
of postings, that didn't seem necessary in the context of a small
quick conversation.
 
C

Chris Angelico

You can call me David. I go by my middle name.

You're most often going to be addressed by the name that's given in
your post headers. In this case "David" has been reduced to an
initial, and is visible only in your email address, whereas "Dwight"
is right there in your real-name.

ChrisA
 
D

Dwight Hutto

You're most often going to be addressed by the name that's given in
your post headers. In this case "David" has been reduced to an
initial, and is visible only in your email address, whereas "Dwight"
My sig says David, but it was just to let him know he can call me by
my used name.
 
S

Steven D'Aprano

You can call me David. I go by my middle name.

If you want to be known as David, why do you give your name as Dwight? In
your email client or newsreader, set your name as David and attributions
will be to David, and people will know to call you David.

Otherwise, people will continue to call you Dwight.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
474,038
Messages
2,570,374
Members
47,020
Latest member
anuradha

Latest Threads

Top