3 ms·

>A Vector Approach to Hashing is something author didnt bother to test at all. His word list includes words with apostrophes (hex #27), like basic's, his code

by rasz_pl 12y ago

>A Vector Approach to Hashing is something author didnt bother to test at all. His word list includes words with apostrophes (hex #27), like basic's, his code accounts only for ascii letters and crashes on that list :) > its O(26) for list creation hmm, no? unless python people create lists one element at a time ...tested and yes they do :o :D every additional byte takes ~10ms on my test computer(110K elements loop), hilarious :))) Its cheaper to create two lists outside main loop, and simply copy empty list over the work list instead of creating new list every time (or resetting global list manually), we are talking ~10% of whole algorithms time cheaper. Python is one hilarious way of benchmarking algorithms. Simple x=1 in your main loop will cost tens of milliseconds. >and its O(26) for creating the tuple Ehhh :/ Yes, sorting is faster in python, ONLY because sort function is highly optimized low level code, while anything you write yourself will be extremely slow due to interpreted nature of the language. You can easily write O(n) hash routine in low level language (assembler, c) and beat nlogn sort. >But, I think this time, we can actually use collections.Counter correctly correctly? yes, faster? NO, ~10% slower. Again seems author simply assumed something is going to work and didnt test. All in all main lesson from all this should be not use python to gauge algorithms speed, unless you are being hired to write speed critical python code (ahahahaha).

gamesbrainiac 12y ago
> is something author didnt bother to test at all. His word list includes words with apostrophes (hex #27), like basic's, his code accounts only for ascii letters and crashes on that list :) Oh, I know it crashes. I had to remove a total of ~20 words that had apostrophes from the original word list. I just added this since it was an interesting take on the problem that I hadn't thought of. Instead of assuming that you have only alphabetical letters, you can assume that you will be getting any ascii character, and hence make an array of 255, and not 26. Which only adds to the problem. > Ehhh :/ Yes, sorting is faster in python, ONLY because sort function is highly optimized low level code, while anything you write yourself will be extremely slow due to interpreted nature of the language. You can easily write O(n) hash routine in low level language (assembler, c) and beat nlogn sort. No argument there. In fact, I tried alternatives in Python which were algorithmically (is that a correct word?) superior, but sucked when put to the test. I even tried with array.array, but unfortunately, that takes a list as an initialiser. So, if you wanted to initiate a fixed size array, you would actually be creating the list, and then creating the array which makes the process even slower. > correctly? yes, faster? NO, ~10% slower. Again seems author simply assumed something is going to work and didnt test. You insist on saying that I didn't test it (your other comments seem to reflect a similar level of disdain for other people's intelligence as well). It is indeed slower, but the reason I added it is to showcase a bit of stdlib magic. Initially, I was using Counter the wrong way, and now there's a place for it (the whole story ties in at the end). But on the bright side, you tried out the code yourself, and hopefully learned something new (I know that's hard considering how impeccably smart you most certainly are). To be honest, I didn't really think people would read it that far.

by rasz_pl 12y ago

gamesbrainiac 12y ago

> is something author didnt bother to test at all. His word list includes words with apostrophes (hex #27), like basic's, his code accounts only for ascii letters and crashes on that list :) Oh, I know it crashes. I had to remove a total of ~20 words that had apostrophes from the original word list. I just added this since it was an interesting take on the problem that I hadn't thought of. Instead of assuming that you have only alphabetical letters, you can assume that you will be getting any ascii character, and hence make an array of 255, and not 26. Which only adds to the problem. > Ehhh :/ Yes, sorting is faster in python, ONLY because sort function is highly optimized low level code, while anything you write yourself will be extremely slow due to interpreted nature of the language. You can easily write O(n) hash routine in low level language (assembler, c) and beat nlogn sort. No argument there. In fact, I tried alternatives in Python which were algorithmically (is that a correct word?) superior, but sucked when put to the test. I even tried with array.array, but unfortunately, that takes a list as an initialiser. So, if you wanted to initiate a fixed size array, you would actually be creating the list, and then creating the array which makes the process even slower. > correctly? yes, faster? NO, ~10% slower. Again seems author simply assumed something is going to work and didnt test. You insist on saying that I didn't test it (your other comments seem to reflect a similar level of disdain for other people's intelligence as well). It is indeed slower, but the reason I added it is to showcase a bit of stdlib magic. Initially, I was using Counter the wrong way, and now there's a place for it (the whole story ties in at the end). But on the bright side, you tried out the code yourself, and hopefully learned something new (I know that's hard considering how impeccably smart you most certainly are). To be honest, I didn't really think people would read it that far.