^ speedy solution for The Hamming Distance by veky - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

^ solution in Speedy category for The Hamming Distance by veky

checkio=lambda n,m:bin(n^m).count("1")

Feb. 26, 2014

Comments:

Cjkjvfnby on March 6, 2014, 7:20 p.m.
Congratulation you have fastest solution here (1 from 8)

Lasica on April 22, 2014, 8:40 a.m.
I dunno how fast .count() is, but isn't mine a little faster? :(

veky on April 22, 2014, 10:21 a.m.
Your big problem is that you're writing C. More precisely, you write code that would be fast if it was written in C. But it isn't. My code, on the other hand, is written in C directly. Read "an optimization anecdote" by GvR.

Lasica on April 22, 2014, 10:50 a.m.
Whenever I google it, I get the link: <a href="https://www.python.org/doc/essays/list2str.html">https://www.python.org/doc/essays/list2str.html</a> But it seems to be outdated. Can you hint the source or way to increase my google-fu?

veky on April 22, 2014, 10:53 a.m.
<a href="https://www.python.org/doc/essays/list2str/">https://www.python.org/doc/essays/list2str/</a> I hate nonURLs too. :-)

Cjkjvfnby on April 22, 2014, 9:44 a.m.
Just timeit.

Lasica on April 22, 2014, 10:44 a.m.
Checked with result: mine: 3.125577583006816 veky's: 2.2694583480188157 Can anyone explain why this lambda is faster? I think that in C++ mine solution would be faster as I count only as many times as there are set bits, not as many as there are number digits. Is it some python magic or it's the lenght of code to interprete that makes this difference? It's also the first time I use timeit, so maybe I did something wrong. Although it's not really a big deal, I am curious of how should I use python effectively in comparison to for example C++ (which was my "native" lang. :P). Also I am not sure of the timeit.timeit result. Did it really last 3/2 seconds? Why did it take so long for such a simple problem? I've saved the following code in a.py and run in console: python a.py Code: <pre class='brush: python'>ccheckio = lambda n,m:bin(n^m).count("1") def checkio(n, m): # n ^ m == n xor m, it xors bits: 1^1==0, 1^0==1, 0^1==1, 0^0==0 v = n^m # count the number of bits set in v which is xor of numbers c = 0 # c is counter of the total bits set in v while v: v &= v - 1; # clear the least significant bit set c += 1 return c if __name__ == '__main__': import timeit print("1: ", timeit.timeit("checkio(117, 17)", setup="from __main__ import checkio")) checkio = ccheckio print("2: ", timeit.timeit("checkio(117, 17)", setup="from __main__ import checkio")) </pre>

Cjkjvfnby on April 22, 2014, 12:07 p.m.
you use default number=1000000 in timeit.

Lasica on April 22, 2014, 1:43 p.m.
Oh, thanks, that explains 3 seconds

veky on April 22, 2014, 11:06 a.m.
<blockquote> Although it's not really a big deal, I am curious of how should I use python effectively in comparison to for example C++ (which was my "native" lang. :P). </blockquote> Sorry I'll say this, but first try to unlearn almost everything you know about C++. Python is on the other side of the looking glass, where things are superficially similar, but mostly completely different. Just one example that trips many newbies: C++ has value semantics, mostly inherited from C (where it made kinda sense). Great pains await anyone trying to understand exactly how complicated types are passed into functions. I'm sure you know all of this already. RVO, COW, RAII, and other wonderful acronyms. If you're honest, you'll admit it's one big mess. If you're not convinced, read "Want speed? Pass by value" (sorry, nonURL again:). On the other hand, Python is amazingly simple. Variables are names for objects. Objects are passed into functions by rebinding ("renaming") them in function scope. And that's it, mostly. The only problem is that it's different than it is in C++. But it has to be, if you want consistent and simple rules. :-) Another thing that's sometimes hard to swallow to folks from Land of Compiled Code: Python is interpreted. Not directly from text, but from bytecode that's pretty parallel. That means that if you write less code, VM will have less to do. And it is (embarassingly) often most deciding factor. Read <a href="http://asserttrue.blogspot.com/2009/03/how-to-write-fast-code.html">http://asserttrue.blogspot.com/2009/03/how-to-write-fast-code.html</a> (yay, URL!). :-D

Lasica on April 22, 2014, 11:31 a.m.
For others interested: article by Dave Abrahams URL: <a href="http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/">http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/</a> (seems to be out of order atm) Thanks for your help and interest =)

veky on March 6, 2014, 9:16 p.m.
You must be kidding... don't at least 10 more people have exactly the same solution? :-)

Cjkjvfnby on April 22, 2014, 9:47 a.m.
For Speedy category at March 6, 2014 1:20 p.m. :)

xiongbiao on May 20, 2014, 10:13 a.m.
same

veky on May 20, 2014, 12:57 p.m.
Not really surprising, considering the task. :-)

Jiyoqisv on May 24, 2014, 3:11 p.m.
use strings instead of bit wise => short but not speedy

Cjkjvfnby on May 24, 2014, 6:14 p.m.
try timeit module to find which is more speedy.

veky on May 24, 2014, 4:12 p.m.
Care to timeit? You might get surprised. ;-P I really hate it when people learn something from another language, and then they parrot it without context everywhere. No, Python is not C. Not even remotely.

bcristian on July 27, 2014, 12:07 p.m.
Mine is almost 3 times faster (0.5464256655597524 vs 1.3981143273321095) - but it does have a few issues, most importantly that it's not really mine, just a result of google-ing for bit counting :D

veky on July 27, 2014, 12:18 p.m.
Have you tried it on bigger numbers (for example, 1000-bit ones)? It could be faster, but it could be not. :-)

bcristian on July 27, 2014, 3:03 p.m.
Did a few tests with large numbers (1024 bits) - only on the bit-counting part though. As expected, it depends on how that number is represented. If it comes as a binary representation string, the obvious winner is string.count("1") by far. I assumed the other likely possibilities would be as a list of shorts or ints - or 64bit qwords on x64 processors. My method remains fastest in this case - working best with a list of shorts. Using string.count comes close though, with the fastest approach being joining all the binary representations together from a list of ints (32 bit).

veky on July 27, 2014, 9:40 p.m.
Hm, interesting. Have you seen the above comment (<a href="http://www.checkio.org/mission/hamming-distance2/publications/veky/python-3/publication/">http://www.checkio.org/mission/hamming-distance2/publications/veky/python-3/publication/</a>#comment-12131)? It seems you and Lasica have something to talk about. :-D Ahm... I don't see the solution you've written here on the above list. The big problem in many of the above, as far as I can see, is that they only work on C ints (32bit), not Python ints (unbounded).

bcristian on July 28, 2014, 4:42 a.m.
Ooooops, missed the part that long is unbounded. At least in 2.7, Int is the same as in C: 32 bit, so in my mind long was just double that. Obviously that as the number of bits increases your approach wins, since it contains a fixed number of interpreter calls, while any other that performs actual computations in Python will eventually fall behind due to Python to native call overhead. Since I've always written compiled code, to me casting an int to string in order to count bits is abhorrent. But at least I got to learn another thing today. And I did beat you on the problem as it was formulated (inputs < 10**6). :P

veky on July 28, 2014, 8:08 a.m.
<blockquote> Ooooops, missed the part that long is unbounded. At least in 2.7, Int is the same as in C: 32 bit, so in my mind long was just double that. </blockquote> Yes, as I am fond of saying, C has poisoned so many people's minds. :-P <blockquote> Obviously that as the number of bits increases your approach wins, since it contains a fixed number of interpreter calls, while any other that performs actual computations in Python will eventually fall behind due to Python to native call overhead. </blockquote> You have a powerful insight. Now apply it to practically everything you can write in Python, and you'll realize why I write code the way I write it. ;-) <blockquote> Since I've always written compiled code, to me casting an int to string in order to count bits is abhorrent. </blockquote> (-: I understand. That's what I mean by saying "this is another side of the looking glass, where things look superficially the same, but they really are fundamentally different". BTW I think "compiled" is not really of main relevance here. The most important thing is that you think of int as a fixed-size box, and of string as a variable-sized one. Even that freedom you wouldn't have if you wrote in assembler, for example - unless you wrote your own memory manager and string library. <blockquote> But at least I got to learn another thing today. </blockquote> I'm glad to hear that. BTW int vs. long distinction was one of main design errors in Py2. BDFL was blinded by the internal representation, and he promised it won't happen again. :-) <blockquote> And I did beat you on the problem as it was formulated (inputs < 10**6). :P </blockquote> Of course. But in my defense, that condition was added after I solved the problem. :-9 And I must also say, for inputs < 10**6, the absolute difference in times is so small it's practically irrelevant. Of course, if you have many small inputs, then it becomes relevant, but many small inputs is practically the same as one big input in this task, and there I win again, with apologies to Bee Gees. :-DD

bcristian on July 28, 2014, 3:37 p.m.
I'll continue this here, although it's at least somewhat off-topic, because either this site is missing a message-to-user function or I cannot find it :) <blockquote> You have a powerful insight. Now apply it to practically everything you can write in Python, and you'll realize why I write code the way I write it. ;-) </blockquote> And armed with said insight (thanks for the cheers, BTW), I proceeded to solving the next problem - <a href="http://www.checkio.org/mission/find-sequence/publications/bcristian/python-27/first/">Find sequence</a> Imagine my surprise when I found that using itertools.groupby and/or zip is much slower than explicit functions. Which leads to the question - how do you know which way to go? Gut feeling (backed by extensive experience)? Knowledge of the underlying implementation? Take itertools.groupby for example. It does of course perform much more than is needed for that task, but I was really expecting it to outperform my user function, along the lines of the bit counter. Especially since what I imagined the function to be is pretty much the same as my function, only on the native side. BTW, even a version of my function that returns the length of the longest sequence is still faster than max(len(groupby))). Sorry if I bother you too much :D

veky on July 29, 2014, 10:25 a.m.
<blockquote> Which leads to the question - how do you know which way to go? Gut feeling (backed by extensive experience)? Knowledge of the underlying implementation? </blockquote> To be honest, the correct answer is "I don't". :-D Neither does Guido (read "an optimization anecdote" by him:). I just write what seems natural, believing Python will do the right thing. Sometimes it doesn't, and it doesn't bother me too much. Of course, I learn what I can from these things. But mostly other people measure speed of my code for me, and inform me if something is unusual. :-) The takeaway: don't be obsessed by performance. And don't even think about performance unless you haven't written at least a hundred programs. If you're designing a backend for a high frequency trading algorithm, then of course you have to think about performance, but if you're doing that in Python you're doomed from the start anyway. :-P And one more thing: don't use Py2. It makes some really bad decisions regarding trading off performance for readability and vice versa. For example, its iterators are much more primitive and "grafted on" the language than in Py3.

veky on July 29, 2014, 10:50 a.m.
One thing comes to mind: <blockquote> Especially since what I imagined the function to be is pretty much the same as my function, only on the native side. </blockquote> You do realize that this cannot be? If you call max of lens of groups, groupby must go through the entire sequence, split it in groups, and calculate the len of each group, and calculate max of them, and compare with 4. Your algorithm, on the other side, stops as soon as it finds 4 in a row, so it takes two shortcuts from the above: first, it doesn't have to go through the whole sequence, and second, it doesn't have to go through the whole group if it is longer than 4. Another detail: len is not the same as "count". It works only on "unfolded" sequences, so group must first be converted to a tuple or something similar, which is also a needless distraction, because of memory management.

bcristian on July 29, 2014, 12:32 p.m.
I meant another version of that function, which returns the maximum length of any sequence, i.e. going through the entire list. And it was still faster that groupby. The docs for itertools suggested they are just wrappers for that functionality implemented in native code, so for example I thought groupby only allocates a pair of pointers per group. The problem (I can only suspect) lies in the fact that the VM marshals that native group back to the Python level in the form of Python objects to be passed back to the len() function, then the process repeats for max(). I was somehow expecting that the interpreter does a look-ahead, sees that those intermediate Python objects are only used for the next function call, and avoids the whole back-and-forth marshaling. I don't really worry about performance that much, especially since in real life optimization is the last phase and is done based on profiling results. This is mostly a personal curiosity. <blockquote> And one more thing: don't use Py2. It makes some really bad decisions regarding trading off performance for readability and vice versa. For example, its iterators are much more primitive and "grafted on" the language than in Py3. </blockquote> Unfortunately I'm stuck with 2. The primary reason I'm learning Python now is that I want to modify the LinuxCNC controlling the router machine I've built, and to do that I need Python. Although I've been a programmer for many years, somehow I never really needed Python, and on the few occasions I've run into it it was easier to work around using the tools I am familiar with :)

LewisFogden on Oct. 22, 2014, 8:48 p.m.
This is the first time I've come up with the same solution as Veky :)

veky on Oct. 23, 2014, 11:24 a.m.
If I were you, I'd be worried. :-P :-D

GitHub

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!