Alexandre commented on Only Idiots Use Java For High Frequency Trading
The only idiots I know are those who say things that doesn't know about. I have a Java implementation algo engine that has the same latency than a C++ implementation. It's much easier to built. It's using Java Real Time, there is no GC pauses for your information. People who says things like "C++ guys are smarter..." are the real idiots. Let them be idiots...
Alexandre commented on Only Idiots Use Java For High Frequency Trading.
Neither Java nor C++. The big players are using FPGA for developing HFT; other parts of system could be done with Java or C++, it depends. A lot of people doesn't know about Java Real Time. It could be used to build very low latency systems. The latency could be as low as with C++.
Anonymous commented on Don't Sign An NDA Before A Programming Job Interview
Funny, a "major" real estate company asked me to sign an NDA for the interview. I declined. There was also a code assignment after an initial phone call (but before the NDA), not overly difficult and thus not a big deal.
Out of principle I don't want to be under an NDA, i.e. in a position where I cannot speak or act freely. Also the NDA covered confidential information that maybe wasn't even divulged during the interview. So basically, if I signed the NDA and ever used or talked about something that they considered their confidential information then they could pursue me in court. Doesn't that basically turn into a non-compete then? Adding further insult, the main HQ of the company is located in another state so if they were to pursue me in court, I'd have to appear in that (distant) state.
Don't sign NDA's for interviews.
I wrote a Python implementation at home. Here on a Core 2 Quad 2.4GHz I get a cpp time of about 470 ms per run, and in Python about 60s per run, or over 120x slower. I don't have profiling tools for Python, and haven't done any testing for correctness.
My python code is here. I kept as much of the original style as I could. I think your shuffle algorithm isn't robust in its randomness, but I kept the same algorithm (shouldn't affect timing anyway).
This should give you another data point at least.
Really? 60 seconds for one hand on Python? That's pretty awful. I'm glad I didn't waste time learning Python, especially with the 2.0 vs 3.0 fiasco.
Testing for correctness is easy. Compare the output to the CPP version! You can set the hand manually instead of letting it deal for you.
Actually, my shuffling algorithm is the correct one. Assuming the rng is fair (it isn't though), it will produce every possible hand with equal probability.
I did not do
for (i is 1 to n)
Swap i with random position between 1 and n
for (i is 1 to n)
Swap i with random position between i and n
Mine is correct.
Re: shuffle algorithm--yes, I read your code wrong, my mistake. Using the % operator on a rand() result can add bias as well.
Re: Python, my version I tested on is ActivePython 18.104.22.168. It should work in 3+ (though I could have used the // operator in 3+). Since I'm unclear on what typically exists in server environments, I left it at 2.7.
You may want to run my code on your platform to get more useful timing numbers.
That is correct, %n on rand is slightly wrong. If I wanted to be perfect, I should exclude the result when rand returns between MAXINT and floor(MAXINT/n)*n. It is a negligible error.
There are other issues with using rand(), such as the fact that it will repeat eventually. There are 52! possible ways to shuffle a deck, but rand() repeats before 52! hands are dealt. It is good enough if your goal is to deal sample practice hands.
60 seconds was convincing enough to me. 470ms per hand for the C++ version is close to the result on my PC, about 10% faster. I thought Python would do a lot better.
What I am convinced is that nothing beats C/C++ (other than raw assembly). I've heard people swear up and down that other languages are faster, but I haven't seen it in practice.
The other interesting test would be Java or .NET. I expect those would be worse than C/C++ also, but I'm not going to put the time in to try it.
If the process were I/O bound or had high overhead in malloc/free then I'd think .Net might have a shot. I didn't fully convert everything to "Pythonic" style -- getting rid of all globals, for instance, which might optimize better -- but I don't see much more gain.
It really seems to be a compute-bounded case, which is where C++ shines. Even techniques like JIT wouldn't be expected to help because you're processing random values, so the predictive branching can't get better each time you run through a loop.
I'd really be shocked to see anything beat well-written C++ in performance. The advantage of the other languages is primarily development time. I can crank out a Python script to convert data, etc. much faster than C++.
I believe that's why Rails works for many people--if your business model fits Rails precisely. I genuinely like the Ruby language, but community support seems to favor Python, which is why I adopted it as my primary scripting language (after Perl in the late 90s and Ruby in the mid-2000s).
As far as using rand() goes, yes the cycle is limited, but it's reasonable to test as proof of concept. If I were to write my own rand() function again I'd use a standard AES256 approach (crypto hashes are excellent pseudo-random # generators) rather than the old Mersenne twister implementation I used in a simulated annealing project from a few years back.
I find it pretty amazing that chrome js seems to be the best approach after C++. Kinda stunning.
If you want to write your own RNG, a better way is to take the XOR of your custom RNG with a standard RNG. If you XOR two independent RNGs, the result should be no less random than either of them. I thought about taking the XOR of several simple linear congruential random number generators with different periods, leading to a RNG with a VERY LONG period. I was looking for 256 bit and 1024 bit random number generators, but couldn't find anything decent.
Another advantage of writing your own RNG is in certain types of games, if you want to remember the state of the RNG.
The main reason is that, in C/C++, each arithmetic operation (usually) translates to 1 assembly instruction. For those other weakly typed languages, the interpreter does a lot of extra operations verifying the type of the object. Some older languages like FORTRAN and COBOL might outperform the 'modern' languages, because they were also designed closer to assembly.
Rails is useful if you're cranking out a toy demo of a stupid startup website idea. If you're writing something complicated, which is my specialty, Rails is more of a handicap than a help. A lot of these 'modern' fancy frameworks are useless if you try to implement something that isn't covered by the framework. At the same job, they're using D3. It's taking them longer for them to figure out how to make D3 behave the way they want and figuring out the correct D3 inputs, than it would take for them to just open a canvas object and draw on it directly. Seriously, it isn't that hard to open a canvas object, draw some axes, text, and your chart. Using a 3rd party library is another layer of indirection that makes the website slower.
commented on Reader Mail - 12/29/2013 To 01/04/2014
Hello FSK, what is happening with you? It's been a while since you last posted.
Yeah, I know. They took away the local train on the subway, so now I don't get a seat. It took away my blogging time.
I should get back to it, been too lazy.