Programming Challenge !!

[Dru Lee Parsec]

It's time to get some life into this board. So I'm throwing down the gauntlet and serving up a challenge. IN ANY LANGUAGE YOU WANT perform the following.

1) Build a collection (array, vector, hashtable, whatever) of One Million integers counting sequentially from 0 to 999,999

(so far that's easy)

2) Start a timer or get the current time in milliseconds or somehow mark your time. Call it timeA

3) Randomize the million integers

4) Get another time. Call it timeB

5) Subtract timeA from timeB and get the number of milliseconds it took to randomize one million integers.

6) print out the first 100 numbers from your collection to show us that it's really randomized.

If we the judges (me and whoever else wants to volunteer) decide that your sequence is truely random them the fastest code wins. Obviously, I'll have to run all the entries on the same machine to level the playing field. I'll run it on Linux so I can do C, C++, Java, Perl, python, and probably a few other languages as well.

The Fastest Time Wins The Respect And Admiration Of Your Peers (In other words, I don't know if there's a prize yet)

I may at any time decide that there is a due date when the contest will end. Right now I havn't thought about it enough. So don't delay, Post your entries here. Once you post them, if you come up with an optimization then post it again. These code examples should be pretty small. So if your program is more than
60 or 70 lines then something is probably more complex than it should be.

Gentlemen, Start Your Engines! GO!

[Ch00k]

How about speed of writing one? :)

I whipped up a simple VB.NET console app. Shocking performance though. 38 seconds. I guess using a sort comparer to randomize was not a good idea :)

[Strike]

Well, it took me about twenty seconds to code the Python version (ten of which were looking up docs). But it's dying on me with SIGKILLs for some reason, I'll try in Python 2.2. Here's the code:

#!/usr/bin/env python

import time, random

foo = [x for x in range(1000000)]
start = time.time()
random.shuffle(foo)
end = time.time()
duration = end - start
for i in range(100):
print foo[i]

print "Took %d seconds to do." % duration

[Strike]

Ah, my swap is crazy filled, so I think it's an OOM killer killing it. I'll free up some mem and try again.

[sans-hubris]

I'm not sure I like this contest. Some languages, like Java and Perl, will have extra overhead that will affect the timing, even though the theoretical O(n) might be the same as some other code in, say, C/C++ or assembly. I would much rather have an intellectual contest, in which the code with the best O(n) performance wins.

Deadline?

By the way, Nafae, you don't need to shell out more cash for another t-shirt. You've already devoted quite a number of resources to this sight, and I'm sure we all appreciate it, but we don't want you broke or anything. And yes, a forum for just challenges is a good idea.

Everyone else, send your code to someone else that's participating, and don't look at other people's code until the start of judging.

... or just post it here, whatever.

[Strike]

Okay, the above code DOES work, but it is a memory HOG. Took 154MB of RAM on my machine to run and I got it done in 518 seconds (on a modest machine).

[Strike]

Oh, and sans-hubris, I don't think my code will give anyone any tips :) Like much python, it's basically the pseudocode already laid out by Dru, just written to Python specs. :D

[Ch00k]

Originally posted by Strike
Took 154MB of RAM on my machine to run and I got it done in 518 seconds (on a modest machine). yikes! maybe my 32 second job (when i put it on release build) will be worthy after all

then again, i do have a 1.2ghz.. define "modest" :)

[Strike]

P3-450, so going up a processor class AND tripling the clock speed of mine should take mine down by at least a factor of 5 I'd say.

[Dru Lee Parsec]

Remember, You're only timing the randomization, not the creation of the million int array.

I'm really throwing down the gauntlet here. Here it is in Java :



import java.util.*;

public class RandomTest {

private static int initialCapacity = 1000000;
private static int[] list = null;

public static void main(String[] args) {
list = new int[initialCapacity];
for (int i= 0;i< initialCapacity ;i++ ) {
list[i] = i;
}

Random random = new Random();
long time1 = System.currentTimeMillis();
// now randomize them
int t = 0;
for (int j= 0;j< initialCapacity ;j++ ) {
int x = random.nextInt(initialCapacity);
t = list[j];
list[j] = list[x];
list[x] = t;
}

long time2 = System.currentTimeMillis();
long delta = time2 - time1;
System.out.println("randomizing " + initialCapacity + " numbers took : " + delta + " milliseconds");

System.out.println("Here are the first 100");
for (int p=0;p<10;p++ ) {
for (int q=0;q<10;q++ ) {
System.out.print(list[(p*10)+q] + " ");
}
System.out.println("");
}
}
}



The output is :

randomizing 1000000 numbers took : 328 milliseconds
Here are the first 100
456870 245935 390993 291795 242620 457894 728628 416796 556342 496332
140796 608983 900587 70041 137376 88848 664295 218966 185330 769175
127115 800418 138914 65154 548489 167807 668745 903453 434954 823385
254993 315599 538771 64076 21378 429337 583280 304605 896114 154040
243180 280724 755526 260098 418285 729061 824325 286825 821225 57843
562315 419091 787430 193081 165491 30884 3873 640930 313135 847199
214191 420098 252941 853026 360083 145363 101128 701585 20763 518520
996211 466315 577907 315454 913424 444382 90891 235644 553916 71336
725828 18702 594552 599737 1870 364767 136123 33344 976897 915338
784891 140589 257978 188572 586644 831732 474588 919271 117609 947514


328 milliseconds !!!!!

Go for it.

[Nafae]

Good point sans ;) I'm moving this thread to the new competition forum, don't mind me...

[Dru Lee Parsec]

Strike: You used random.shuffle(foo) to shuffle the ints. Try walking through the million ints and picking a random number between 0 and 999999 each time. Then swap the ints at those two indecies (which is what my code does).

I'm really interested to see how this works in Python.

Any Perl or Assembler or C or C++ entries yet? I *KNOW* that assembler would probably kick my code's time. But I havn't coded in asm in too many years.

[Ch00k]

Interesting. Dru, what spec machine are you using?

I wrote versions in C# and VB.NET and got around 420 milliseconds for sorting (doing it properly, not using obfuscated OO cos i was bored).

If I had installed the MC++ component it would probably be even faster. Straight C would probably be faster again.

[GnuVince]

I wrote it in O'Caml. Here's the output:





[vince@vincent: ~/prog/ocaml/array]% ./dru

Randomizing 1000000 numbers took 0.62 seconds

Here are the first 100

375222 170398 288359 741643 191923 46386 576870 885822 830690 626632 343399 716364 187430 488294 508447 562975 706826 516354 340034 215402 68990 427598 388856 969998 493708 745346 132992 376065 434620 770577 91172 535260 559872 482669 857553 536853 154479 733057 690304 32196 920928 379566 369325 220916 302864 728370 125983 642616 61855 94 735192 276087 619940 747252 572218 345339 103203 120266 468440 470102 744972 243319 333132 815931 997228 975420 274148 65045 110470 910549 255616 895794 782360 141174 783810 230798 763498 123979 612615 497141 471919 827833 230415 882039 767089 553405 516309 199726 835422 905148 243701 603908 370595 280539 925630 175260 171748 377597 82817 670436

[vince@vincent: ~/prog/ocaml/array]%





This program was natively compiled on a Athlon 1GHz running GNU/Linux. I used the 3.04 version of O'Caml. Here's the actuall code:





let _ =
(* Creates an array of one million elements containing all zeros, so that all elements are integers (strict typing is forcing me) *)
let capacity = 1000000 in
let myarray = Array.make capacity 0 in

(* Initialize Random *)
Random.self_init ();

(* Put values from 0 to 999,999 in each array element *)
for i = 0 to (capacity-1) do myarray.(i) <- i done;


(* Get the start time. *)
let time1 = Sys.time () in

(* Let's shuffle the whole thing (I made it like Dru) *)
let t = ref 0 in
let x = ref 0 in
for j = 0 to (capacity-1) do
x := Random.int (capacity-1);
t := myarray.(j);
myarray.(j) <- myarray.(!x);
myarray.(!x) <- !t;
done;

(* Get the end time *)
let time2 = Sys.time () in

(* Get the difference (-. is used because we are working with floats) *)
let delta = time2 -. time1 in

(* Print the time it took *)
Printf.printf "Randomizing %d numbers took %.2f seconds\n" capacity delta;
print_endline "Here are the first 100";
flush stdout;

(* Print the first 100 elements *)
for p = 0 to 99 do
Printf.printf "%d " myarray.(p);
done;
print_newline ()

[GnuVince]

Errr.... that's one large blue rectangle... I put the code here (http://darkhost.mine.nu:81/~vince/ocaml/dru.ml)

[Dru Lee Parsec]

>Interesting. Dru, what spec machine are you using?

I did that at work and I'm not sure what the CPU speed is. But on my Athon 1.2Gig with 256Meg at home it took 490 milliseconds. I think my work machine is a slower CPU (probably about a 900 ), but it has 512 Meg of RAM so that's why it ran faster. Both machines are running Win 2000. I'll have to test on Linux later.

Gnu Vince: Where do I get o'Caml for Linux or Windows so I can test your code?

***

Added later:

Yep, if I cut it from one million to 500 thousand then the time comes down to 230 milliseconds which is less than half the 490. Cutting it down to 50,000 runs in 20 milliseconds.

So twenty times 50,000 would be one million and 20 times 20 milliseconds is 400 milliseconds which is close to what I got at work. So I must be losing about 20% of my time (that other 100 milliseconds) by swapping memory. I bet the 512 Meg of RAM at work is making a big difference.

[GnuVince]

Dru: http://caml.inria.fr

To compile: ocamlopt dru.ml -o dru

[kmj]

programming challenges.... qool (c:

[Strike]

Dru, your suggestion took the time down to about 84 seconds on my system. Still not quite in the millisecond range. I'm going to whip up a C/C++ example.

[Strike]

Okay, C goodness here:

#include <stdlib.h>
#include <sys/time.h>
#include <time.h>

#define SIZE 1000000

void main()
{
int *list = (int *)malloc(SIZE*sizeof(int));
int i, x, temp;
int usec;
struct timeval start, end;

for (i=0; i < SIZE; ++i) {
list[i] = i;
}

gettimeofday(&start, NULL);

for (i=0; i < SIZE; ++i) {
x = rand() % SIZE;
temp = list[i];
list[i] = list[x];
list[x] = temp;
}

gettimeofday(&end, NULL);

usec = end.tv_usec - start.tv_usec;
if (end.tv_sec - start.tv_sec) {
usec += 1000000;
}

for (i=0; i < 99; ++i) {
printf("%d ", list[i]);
}

printf("\nTook %d microseconds to do.\n", usec);
}

Sample output (on my modest system) shows that we have a real contender for speediest (duh):

[ddipaolo@quinn ...net/challenge2]% ./challenge2
289383 930886 295470 36439 747793 992619 578037 267191 451326 641421 664766 490027
798037 25538 107863 513926 180540 288756 89172 744096 630384 94819 389158 55016 591387 611582 37099 861398 174067 703135
513929 887740 368554 270946 531458 898167 877712 589429 502961 545501 10720 324656 484421 382355 622391 898537 468895 594324
798315 69242 384936 412774 776091 524207 759956 128692 429383 999170 227902 134826 439555 906717 180116 336327 8639 919877
568045 163240 61763 137049 284895 856565 399709 269688 290479 166408 169514 990364 413184 313750 171087 506 336808 947178
41704 393584 705403 390736 392754 864303 999932 31658 697723 174964 947739 210012 636226 698586 348094
Took 755878 microseconds to do.

[Strike]

Also, note that that says MICROseconds.

[GnuVince]

I guess it was all too predictable. Everytime there's a small trivial task to accomplish, the fastest language is always Asm. Then comes C, and other natively-compiled languages and Java. Next come the interpreted languages. It's always the same. Let's not view this as a contest on speed, cause the winners are pre-determined, let's instead watch how to do one same task in many languages.

[Strike]

I'm going to look into making an assembler version, but looking at the one spit out by gcc looks pretty well optimized already and I don't see much I could do to speed it up except use system calls instead of glibc

[GnuVince]

I tried the Strike's program. It took ~0.54 seconds on my box (Athlon 1GHz). I compiled with gcc -O6 -fomit-frame-pointer. My O'Caml program isn't that bad :) I'm going to try Dru's one now.

0.57 seconds. So I guess we're all in the same times.

[Dru Lee Parsec]

microseconds ? Millionths of seconds? or are those actually Milliseconds? Did it take about 3/4th of a second?

Still, we have a real contender here.

Something I was thinking of is this: What if we do an XOR swap? Given two ints A and B this psuedo code:

a = a XOR b;
b = a XOR b;
a = a XOR b;

will swap the values of a and b. In assembler this is really fast:

XOR a,b
XOR b,a
XOR a,b

But in Java it's an XOR and an assignment so it's actually slower than a pure assignment.

But if an XOR is faster than an assignment in C then we may have an optimization possibility.

I am swamped right now. I'm at work and it's my wife's birthday party tomorrow (over 60 people showing up) but on Sunday I should be able to compile and run each of these on my computer at home and well get some standardized times for these programs. So everyone work hard until Sunday afternoon. OK?

But I think this C program is a real contender. :)


P.S. I'm really looking forward to comparing the C version and the Java version since they're both using the same algorithm. I expect C's native code to come out ahead, but I thik Java will be close enough that thoughts of "Java is Slow" can be properly banished. :)

[Dru Lee Parsec]

Strike: Where do I get sys/time.h ? M$ Visual C++ didn't seem to know about that header file. (Be kind to me, it's been over 4 years since I've done C or C++ code) ;)

[GnuVince]

:( My program sucks?

[inkedmn]

~punish being out of town for three days and missing the beginning of the programming challenge... :(

[GnuVince]

I tried the xor technique. It took 0.64 seconds, so in O'Caml's case, it's a tad slower.

Edit: I tried this and it seems to work: instead of looping until capacity/2. The only itch I've noticed though is that the last element of the array is often the same than when it's not shuffled. Anyway, give it a shot. Here's a sample output (I printed the last element of the array):

Randomizing 1000000 numbers took 0.29 seconds
Here are the first 100
999999
Randomizing 1000000 numbers took 0.30 seconds
Here are the first 100
141306
Randomizing 1000000 numbers took 0.30 seconds
Here are the first 100
457954
Randomizing 1000000 numbers took 0.30 seconds
Here are the first 100
135113
Randomizing 1000000 numbers took 0.30 seconds
Here are the first 100
999999
Randomizing 1000000 numbers took 0.30 seconds
Here are the first 100
999999
Randomizing 1000000 numbers took 0.30 seconds
Here are the first 100
999999
Randomizing 1000000 numbers took 0.30 seconds
Here are the first 100
999999


You can see that 999999 comes back pretty often. But the rest of the serie is pretty random

[Strike]

Originally posted by Dru Lee Parsec
Strike: Where do I get sys/time.h ? M$ Visual C++ didn't seem to know about that header file. (Be kind to me, it's been over 4 years since I've done C or C++ code) ;)
I don't know where you would for MS stuff. Just find out whatever is needed to do the gettimeofday type stuff.

And yes, those are microseconds. Microseconds are 1/1000th of milliseconds.

[GnuVince]

This means his program is about the same speed than my O'Caml program or your Java program Dru

[GnuVince]

I made more tests this morning. I tried using a while loop, but it's a bit slower (0.67 seconds (that's without capacity/2)).

Time to try something else I guess

[Dru Lee Parsec]

It's looking like a half a second is pretty reasonable. But GnuVince's 0.29 is looking pretty quick.

GnuVince, if you're using a loop then then it may be a "loop end limit" issue. Are you sure you're looping fully from 0 to 999999?
Also, print out the first 20 or so to make sure that you're not getting the same series of numbers.

My program sucks?
????
I never said that. I think you've got the fastest time so far.


BTW everyone. I've been swamped this weekend and barely had time to turn the computer on. We had a party with about 60 people on Saturday. Sunday was a "Deal with the hangover's Mother's Day". And today I'm back at work. I'll try to find time to compile all these programs on my computer soon so I can publish some base line times.

[GnuVince]

Don't use the capacity/2 trick: the more number you have, the less likely the second half is to be changed.

Can we say that above .3 second and below 1 second is in the norms?

[Dru Lee Parsec]

Can we say that above .3 second and below 1 second is in the norms?

I think that's pretty good. The real fun in this challenge was to see how we could get away from the 20 or 30 second algorithms and move into the .3 to 1.0 range.

I think everyone who participated has done very well. (But don't stop yet, let's go for a less than .3 second randomization)

[GnuVince]

I can do it in 0.001 second if it's a 10 integers array :)

Seriously, how has the xor thing gone on Java? I'm gonna make a Ruby version for fun :)

[GnuVince]

Ruby took:

Randomizing took 5.398372 seconds


Code:


#!/usr/bin/env ruby

capacity = 1000000
myarray = [0] * capacity

for i in 0 ... capacity
myarray[i] = i
end

time1 = Time.now
"%f10.6" % time1.to_f

t = 0
for j in 0 ... capacity
x = rand(capacity)
t = myarray[j]
myarray[j] = myarray[x]
myarray[x] = t
end

time2 = Time.now
"%f10.6" % time2.to_f

delta = time2 - time1

puts "Randomizing took #{delta} seconds"
puts "Here are the first 100 elements"

for i in 0 .. 100
print "#{myarray[i]} "
end
print "\n"

[GnuVince]

Hahahhahaa! I got a new record (for my O'Caml program): 0.37 seconds


[vince@vincent: ~/prog/ocaml/dru]% ./dru6
Randomizing 1000000 numbers took 0.37 seconds
Here are the first 100
<snip>



Gnyahahahaha! I won't post this new solution yet just to see if someone can come up with it


edit: It's a 61% speed boot :)

[Dru Lee Parsec]

I came up with a very small optimization that brought my time from 312 milliseconds down to 297. I think I could shave a few more milliseconds off still, but somewhere around 270 may be the limit.

[GnuVince]

Dru, here's my new code. Could you try it on your box at work, cause it seems to have one heck of a processor (your old version akes .70 second on my box)


let _ =
(* Creates an array of one million elements containing all zeros, so that
all elements are integers (strict typing is forcing me)
*)
let capacity = 1000000 in
let myarray = Array.make capacity 0 in
let randomarray = Array.make capacity 0 in

(* Initialize Random *)
Random.self_init ();

(* Put values from 0 to 999,999 in each array element *)
for i = 0 to (capacity-1) do myarray.(i) <- i done;

(* Make the random array *)
for i = 0 to (capacity-1) do randomarray.(i) <- Random.int (capacity) done;

(* Get the start time. *)
let time1 = Sys.time () in

(* Let's shuffle the whole thing (I made it like Dru) *)
let t = ref 0 in
for j = 0 to (capacity-1) do
t := myarray.(j);
myarray.(j) <- myarray.(randomarray.(j));
myarray.(randomarray.(j)) <- !t;
done;

(* Get the end time *)
let time2 = Sys.time () in

(* Get the difference (-. is used because we are working with floats) *)
let delta = time2 -. time1 in

(* Print the time it took *)
Printf.printf "Randomizing %d numbers took %.2f seconds\n" capacity delta;
print_endline "Here are the first 100";
flush stdout;

(* Print the first 100 elements *)
for p = 0 to 99 do
Printf.printf "%d " myarray.(p);
done;
print_newline ()


All speed tests should be done on the same box so we can have accurate benchmarks. Since you started it Dru, how about you be our host?

[Dru Lee Parsec]

OK, I d-loaded O'Caml for Windows. I took the code you posted above and saved it as dru.ml

I ran the camlvars.bat program to put the proper directories in my path and so on.

I then typed:

D:\Dev_Projects\OCaml>ocamlopt dru.ml -o dru

And I got the response:

'ml' is not recognized as an internal or external command,
operable program or batch file.
Assembler error, input left in file C:\DOCUME~1\dv32873\LOCALS~1\Temp\camlasm0.asm


Any ideas how I could fix this? Thanks
***********

Oh wait, I tried ocamlc dru.ml -o dru and I get a series of files that makes it look like I've compiled something. One of them is a file called "dru" how do I run that file?

[Dru Lee Parsec]

Never mind: I found ocamlrun

Here's the output of Gnu Vince's code on my computer:
Randomizing 1000000 numbers took 0.88 seconds
Here are the first 100
535977 264640 197989 619338 583106 714044 677740 419710 116788 557199 453575 666044 499647
614664 17586 310708 24225 43532 151279 399591 441961 291031 350354 424260 66923 36202 218
748 613894 308915 929841 268436 153216 26155 96689 343479 148587 841925 111647 654408 8893
31 21 779493 47110 646325 947744 933156 727898 40154 292279 666374 732848 767458 601213 85
1281 270102 277274 218930 190474 423397 725832 91251 641254 324090 488283 57121 729929 154
405 780523 403825 195936 599422 926689 390038 129938 253034 711148 39951 856852 323340 568
349 8759 593509 399074 749454 781122 395280 974589 541001 620998 12542 163083 217043 38630
864562 893163 804972 224473 532357 97355 101807

Is there any optimization programs I should run? i.e. what exactly does ocamlopt do?

[GnuVince]

ocamlc is the byte-compiler. ocamlopt is the native-code compiler (the one you should use). You should also use O'Caml under Linux as it works a tad better and I have no idea how to get something to compile/run under Windows. I would propose my box as the testing box, but I only have Java 1.3.

[Dru Lee Parsec]

I think java 1.3 should be fine. I'm not using any code that's new since 1.2 (or even 1.1 actually).

What's the command line for ocamlopt ? I used
ocamlopt dru.ml -o dru

And I got the response:

'ml' is not recognized as an internal or external command,
operable program or batch file.
Assembler error, input left in file C:\DOCUME~1\dv32873\LOCALS~1\Temp\camlasm0.asm

Whereas that command line ran great with ocamlc.

???

[GnuVince]

Probably Windows then... care if we use my box for benchmarks then?

[PrBacterio]

Originally posted by Dru Lee Parsec
I think java 1.3 should be fine. I'm not using any code that's new since 1.2 (or even 1.1 actually).

What's the command line for ocamlopt ? I used
ocamlopt dru.ml -o dru

And I got the response:

'ml' is not recognized as an internal or external command,
operable program or batch file.
Assembler error, input left in file C:\DOCUME~1\dv32873\LOCALS~1\Temp\camlasm0.asm

Whereas that command line ran great with ocamlc.

???

That error means that you don't have the Microsoft Macro Assembler installed. ML.EXE is Microsoft MASM. There are two Windows versions of OCaml: One, which uses MS Visual Studio and MASM; and another which uses the cygwin port of GCC / GAS. Apparently, you use the one which needs MASM for native-code compilation (I do too by the way).

ocamlc is just the byte-code compiler.

Oh, and GnuVince, your program doesn't measure its running-time correctly. One would think you should need to include the time needed for generating the pseudo-random numbers in the timing as well, as this is the major part of the work this program does. Anyway this competition doesn't strike me as very interesting personally; isn't this problem basically O(n) no matter what you do?

[kozumo]

Originally posted by PrBacterio


That error means that you don't have the Microsoft Macro Assembler installed. ML.EXE is Microsoft MASM. There are two Windows versions of OCaml: One, which uses MS Visual Studio and MASM; and another which uses the cygwin port of GCC / GAS. Apparently, you use the one which needs MASM for native-code compilation (I do too by the way).

ocamlc is just the byte-code compiler.

Oh, and GnuVince, your program doesn't measure its running-time correctly. One would think you should need to include the time needed for generating the pseudo-random numbers in the timing as well, as this is the major part of the work this program does. Anyway this competition doesn't strike me as very interesting personally; isn't this problem basically O(n) no matter what you do?

If you ignore the data input (in this case, loading the 1 million numbers), then the operation to be measured is the shuffling, I think it's possible to do O(1), otherwise yes, well given that the input size is n, but in this case it's fixed.

[GnuVince]

There are no rules stating you can't cheat :) And in any case, I don't think my second program has any problem. I shuffle but in a different way.

[Dru Lee Parsec]

Anyway this competition doesn't strike me as very interesting personally; isn't this problem basically O(n) no matter what you do?

Sure, it's not a difficult or complex project. But there are quite a few people here who are learning to program and need some sort of project to focus on. As we get more involvment I'll come up with more Programming challenges.

Still, I find it interesting to see the same idea implemented in different languages.

[inkedmn]

here's a python version:


#!/usr/bin/env python

# for cf.net

import time, random

list = [x for x in range(1000000)]
begin = time.time()
for index in range(1000000):
x = random.randrange(1000000)
temp = list[x]
list[x] = list[index]
list[index] = temp
end = time.time()
for i in range(100):
print list[i],
total = end - begin
print "\nRandomization took %d seconds." % total


i'm averaging about 49 seconds on this.

[GnuVince]

20 seconds Brett

[Dru Lee Parsec]

GnuVince, you have Python, OCaml and Java on your box. Do you have Ruby installed? I just don't have the free time to install Ruby and learn to compile/run it right now (This week is getting really busy).

Would you like to use your computer as the base line? I can't seem to get any free time at home right now. Too many projects to accomplish first.

[inkedmn]

Originally posted by GnuVince
20 seconds Brett

my time was on my windows box here at work (not a speed demon by any stretch of the imagination)

on my linux box, it took 74 seconds :)

[GnuVince]

My box is used for benchmarks. Positions:
1. GnuVince (O'Caml) version 2
2. Strike (C)
3. GnuVince (O'Caml) version 1
4. Dru Lee Parsec (Java)
5. Inkedmn (Python)
6. Strike (Python)

[inkedmn]

well, at least i'm not last :)

[PrBacterio]

Here's a version in Scheme I did:

;; randomly shuffle the elements of the given vector
(define (shuffle vector)
(let ((l (vector-length vector)))
(let repeat ((n (quotient l 2)))
(let* ((i (random l))
(j (random l))
(t (vector-ref vector i)))
(vector-set! vector i (vector-ref vector j))
(vector-set! vector j t))
(if (> n 0)
(repeat (- n 1))))))


;; returns part of a vector, n elements starting
;; at index i0
(define (sub-vector vector i0 n)
(let ((r (make-vector n)))
(let next ((i 0))
(when (< i n)
(vector-set! r i (vector-ref vector (+ i0 i)))
(next (+ i 1))))
r))

;; make a vector containing the n
;; elements 1 2 ... n
(define (make-n-vector n)
(let ((r (make-vector n)))
(let next ((i 0))
(when (< i n)
(vector-set! r i (+ 1 i))
(next (+ i 1))))
r))

;; time the shuffling of a vector
;; containing 1 ... 1000000, and return
;; the first 100 elements of the result
(let ((v (make-n-vector 1000000)))
(time (shuffle v))
(sub-vector v 0 100))

But its running time is considerably worse than that of some of the programs already posted - but the DrScheme interpreter is not known for its high speed of execution anyway so maybe that has something to do with it ;).

Oh and the time primitive I used to measure the running time, I dont know if that is standard Scheme or one of those Mz Scheme extensions so ymmv.

[Dru Lee Parsec]

GnuVince:

Thanks for doing that.

What were the actual times for each of the code examples?

**************

PrBacterio

I have neither heard of nor seen "Scheme" before. Where did that language come from and what are it's advantages?

I'm learning so much about different languages with this challenge. I've been exposed to O'Caml, Ruby, and Python. This is Kool!

[PrBacterio]

Dru: Scheme is a dialect of Lisp. While I dont think it was intended by its inventors that way, I consider it to be a kind of "learner's version" of Lisp :) Also it has a good interpreter with a really very nice GUI IDE in DrScheme (http://www.plt-scheme.org/software/drscheme/), though that interpreter is not very fast, but it comes with a (not very easy-to-use) compiler (which I havent felt the need to try yet :p).

Its kinda neat in that its very clean and logically structured, but its not really very powerful. We did it in a University course once, and thats where I heard of it first, and its kind of grown on me. www.schemers.org is a good URL for information about it.

[GnuVince]

Here are the time outputs (I removed the 100 numbers for the sake of brievity)


[vince@vincent: ~/prog/ocaml/dru]% ./vince2
Randomizing 1000000 numbers took 0.35 seconds

[vince@vincent: ~/prog/ocaml/dru]% ./vince1
Randomizing 1000000 numbers took 0.58 seconds

[vince@vincent: ~/prog/ocaml/dru]% ./strike
Took 557747 microseconds to do.

[vince@vincent: ~/prog/ocaml/dru]% java Dru
randomizing 1000000 numbers took : 547 milliseconds

[vince@vincent: ~/prog/ocaml/dru]% ./inkedmn.py
Randomization took 21 seconds.

[vince@vincent: ~/prog/ocaml/dru]% ./strike.py
Took 12 seconds to do.

[vince@vincent: ~/prog/ocaml/dru]% ./vince.rb
Randomizing took 5.126147 seconds


So I guess I messed up my previous standings (I stopped a distributed client), so the new ones are:

1. GnuVince (O'Caml, version 2)
2. Dru (Java)
3. Strike (C)
4. GnuVince (O'Caml, version 1)
5. GnuVince (Ruby)
6. Strike (Python)
7. Inkedmn (Python)

Haven't tried BrBacteria's scheme one yet.

[inkedmn]

bah...
well, nevermind about not being last :)

do i get any sort of consolation prize? ;)

[PrBacterio]

Ok I did another one in Lisp for good measure :)
(declaim (optimize (speed 3) (space 0) (safety 0)))

(declaim (ftype (function (fixnum) (simple-vector fixnum)) make-n-vector))
(defun make-n-vector (n)
"make a simple vector with n elements: 1...n"
(declare (type fixnum n))
(let ((r (make-array n :element-type 'fixnum)))
(declare (type (simple-vector fixnum) r))
(dotimes (i n)
(setf (svref r i) (1+ i)))
r))

(declaim (ftype (function ((simple-vector fixnum)) nil) shuffle-vector))
(defun shuffle-vector (v)
"shuffle the given vector"
(declare (type (simple-vector fixnum) v))
(let* ((n (length v))
(iter-count (truncate (/ n 2))))
(declare (type fixnum n)
(type fixnum i)
(type fixnum j)
(type fixnum iter-count)
(type fixnum tmp))
(dotimes (ctr iter-count)
(let* ((i (random n))
(j (random n))
(tmp (svref v i)))
(setf (svref v i) (svref v j))
(setf (svref v j) tmp)))))

(defun shuffle-timer (n)
"shuffle an array of n elements: 1...n,
and time that operation"
(let ((v (make-n-vector n)))
(princ "now shuffling") (terpri)
(time (shuffle-vector v))
(princ "done") (terpri)
;; return the first 100 elements
(subseq v 0 100)))

Damn I spent the better part of an hour trying to get this to compile in Corman Lisp, but I failed. When run, the Corman Lisp version always crashed on me with some garbage collector error :(

So the only timing I have done is in CLISP where it did about the same as the DrScheme version (not surprising, since that is an interpreter too).

[inkedmn]

ok, got some more python code (Thanks Vince!)...

this took 7 seconds on my machine...


#!/usr/bin/env python

# for cf.net

import time, random

list = range(1000000)
randlist = [None] * 1000000
for i in xrange(1000000):
randlist[i] = random.randrange(1000000)
begin = time.time()
for i in list:
stuff = list[i]
list[i] = list[randlist[i]]
list[randlist[i]] = stuff
end = time.time()
for i in range(100):
print list[i],
total = end - begin
print "\nRandomization took %d seconds." % total


w00t!

[Dru Lee Parsec]

GnuVince:

Thanks for doing the time base line. When can we see the winning code? :)

[GnuVince]

The new version of inked takes 3 seconds! Good job!

Dru: it's already on page 3 or 4 of the thread. You can also see it at http://darkhost.mine.nu:81/~vince/ocaml/vince2.ml

[Dru Lee Parsec]

GnuVince:

I think I gotcha! ;)

This line of code is where your optimization came from

(* Make the random array *)
for i = 0 to (capacity-1) do randomarray.(i) <- Random.int (capacity) done;



If I'm interpreting this correctly then your'e looping i from 0 to capacity-1. You are then building a new array called RandomArray and you are taking a random entry from your initial array and putting it into the RandomArray.

Now, this is much faster HOWEVER, you will have duplicate integers and also missing integers. This command "Random.int (capacity) " returns a random number between 0 and capacity. But there's no guarantee that Random.int(capacity) will never return the same integer twice (If I understand the API correctly). If it ever does return the same number twice in 1 million hits then your RandomArray isn't really random because it has duplicates.

Example:

Initial Array: 0,1,2,3,4,5,6,7,8,9

Now we loop 10 times and we get 10 random numbers:
4,6,3,5,8,9,7,2,3,0

Your RandomArray would now be
4,6,3,5,8,9,7,2,3,0
which has a duplicate of 3 and is missing the number 1.

As a quick check you could sort the random array and then compare it against the original array. Or sort the original array and check to see if any 2 consecutive numbers are the same.

Or, if you just set capacity to 10 and ran the program about 20 times you could probably see it by eye.

[Dru Lee Parsec]

Oh I get it! It's OK if your random array has duplicates because what you're doing is making a list of random numbers and using that instead of calling your random function each time through the loop.

So your'e using a pre-constructed set of random numbers. Right?

But I still think I gotcha. I think to be fair you need to get your first time BEFORE you build your random array since building that array is an integral part of your shuffling process.

Change this:


(* Make the random array *)
for i = 0 to (capacity-1) do randomarray.(i) <- Random.int (capacity) done;

(* Get the start time. *)
let time1 = Sys.time () in



To this

(* Get the start time. *)
let time1 = Sys.time () in

(* Make the random array *)
for i = 0 to (capacity-1) do randomarray.(i) <- Random.int (capacity) done;



and I think your processing time is more accurate.

[GnuVince]

The processing time had to be calculated onto the actual shuffling, preperations were not mentionned (else we would time the entire program).

And I don't have duplicates. I use the numbers in randomarray as POSITIONS for myarray, not as the actual numbers:


let t = ref 0 in
for j = 0 to (capacity-1) do
t := myarray.(j);
myarray.(j) <- myarray.(randomarray.(j));
myarray.(randomarray.(j)) <- !t;
done;


This translates rougly to:


int t;
for (int j=0 ; j < capacity ; j++) {
t = myarray[j];
myarray[j] = myarray[randomarray[j]];
myarray[randomarray[j]] = t;
}


Do you understand what I'm doing? Here's a sample output with 10 numbers:


[vince@vincent: ~/prog/ocaml/dru]% ./vince2
Randomizing 10 numbers took 0.00 seconds
Here are the first 100
8 2 5 6 7 4 9 0 1 3
[vince@vincent: ~/prog/ocaml/dru]% ./vince2
Randomizing 10 numbers took 0.00 seconds
Here are the first 100
3 0 2 1 9 7 4 8 5 6
[vince@vincent: ~/prog/ocaml/dru]% ./vince2
Randomizing 10 numbers took 0.00 seconds
Here are the first 100
4 3 1 5 7 2 8 0 6 9



Unless I am mistaken, I see no duplicate numbers; do you? But yes, we can say that in a sense I improved my program by "exploiting" a flaw in the rules :p (Because, overall, this second program is slower to execute as a whole)

[Dru Lee Parsec]

I agree, I now see that there will be no duplicates.

Oh I get it! It's OK if your random array has duplicates because what you're doing is making a list of random numbers and using that instead of calling your random function each time through the loop.

So your'e using a pre-constructed set of random numbers. Right?


But since building the random array is a major part of the randomization portion of the code, I think it needs to be included in the time. I think that it at least follows the intention of the competition closer.

Anyone else have an opinion.

[Strike]

I agree that generation of the randomization (however it is done, with a separate index array or not) should be timed as well simply because that was the way it was specified originally. All of us could probably do the same sort of thing and shave time off of ours as well.

[xilica]

bahaha........... done...... easy as cake

[xilica]

i use visual basic 6 pro

[inkedmn]

Originally posted by xilica
i use visual basic 6 pro

let's see the code then :)

and the randomization time as well, please

[xilica]

jeeze........ what the heck

[inkedmn]

Originally posted by xilica


k, give me your e-mail..... you want all the code....... it'll take up 4 pages

why would it take up four pages?

even if you wrote this in binary it wouldn't take up THAT much room...

just post it

[xilica]

Originally posted by inkedmn


let's see the code then :)

and the randomization time as well, please


uh randomization.............. i didnt know it had to be random

[GnuVince]

Well, that's the whole point.

[xilica]

well, im out :stupid:

[inkedmn]

Originally posted by xilica
well, im out :stupid:

huh?

[xilica]

Originally posted by inkedmn


huh?

its a little bit of a challenge to randomize that many variables.... and slow...... but an SQL database could

[inkedmn]

forgive me if i seem condescending, but i'm not sure you understand exactly what the challenge entails...

- create a list/array with the numbers 0 - 999,999
- record the time (beginning)
- shuffle the list/array so that the numbers aren't in order
- record the time (end)
- print the first 100 numbers in the now-random list/array
- print the time it took to randomize the list/array (end - beginning)

i don't think a SQL db is necessary here :)

good luck!

[xilica]

dont worry about condescending....... its kew.....
anyway, can we use more then one programming language to create this??

[inkedmn]

are you asking if you can do the assignment using a combination of languages? or if the challenge can be done in any language?

please clarify

[xilica]

i already know it can be done in any language but can we criss cross in platforms ... example

use php, java, and mysql

[inkedmn]

let's put it this way...

do it however you want, just make the randomization as fast as possilbe.

ok?

[xilica]

got it.......



goes to the drawing board

[Dru Lee Parsec]

Wow, I leave town for 3 days and look at all the messages!

Inkedman, thanks for clarifying the competition in my absence.

Xilica: you can write your code in any language you like. But the current best times are in the range of 300 to 500 milliseconds (roughly 1/3rd to 1/2 of a second) So if you're using multiple languages you may have a tough time getting your code into that range.

Think simple and fast.

[xilica]

hey,
i am using visual basic for this....... and.....
the hardest part is making an array for that many variables!?!

[inkedmn]

isn't it something like this?


Dim number As Array(1000000)

?

[xilica]

incorrect inkedmn it is this:

Dim number(1 To 1000000) As Long

' or

Dim number(0 To 999999) As Long

' You can dim as any number type you like

[inkedmn]

ok...

[xilica]

by the way, as any completed this perfectly yet?

[GnuVince]

Of course. Inkedmn, Dru, Strike, PrBacterio and myself all have working versions (don't know if I forget someone). I made a "cheat" version, but my first attempt was correct and was as fast as any other that was compiled.

[inkedmn]

Originally posted by xilica
by the way, as any completed this perfectly yet?

i don't mean to be rude, but have you read this whole thread? many of the questions you're asking have been answered...

[file13]

howdy folks! Vince told me about this place. nifty! :D

anyways, here's an Ada 95 version and a Lisp version (for 3 free Lisp implemetations)

Ada 95
1. http://www.qlippoth.com/shuffle.adb
(works fine, but threading problems with Gnuada rpms. but i tested successfully on windows 2000 with GNAT 3.14 and slackware 8.0 with GNAT 3.14 Linux binaries.

2. http://www.qlippoth.com/shuffle2.adb
(rewrote so there's no use of realtime annex which was causing the threading problems Linux).

Lisp (CMUCL, Clisp, ECLS)
http://www.qlippoth.com/shuffle.lsp

on Cmucl i got a VERY fast speed.

BTW:

GNAT (GNU Ada):
ftp://cs.nyu.edu/pub/gnat/3.14p/

CMUCL:
http://www.cons.org/cmucl/

Clisp:
http://clisp.cons.org/

ECLS:
http://ecls.sourceforge.net/index.html

:)

[GnuVince]

[vince@vincent: ~/prog/ocaml/contest/dru/ada]% ./shuffle2
Populating collection list...
Randomizing collection list. Starting timer:

Time to shuffle in seconds: 1.056286000

372231 565820 524887 282104 791747 664607 939933 467181 812174 815231
[vince@vincent: ~/prog/ocaml/contest/dru/ada]%

[vince@vincent: ~/prog/ocaml/contest/dru/shuffle_lisp]% ./rlisp shuffle2.x86f
Populating collection list...
Randomizing collection list. Starting timer:

Evaluation took:
0.4 seconds of real time
0.4 seconds of user run time
0.0 seconds of system run time

[Arker]

I know this thread has been dead for several months now, but since I just joined I thought I'd contribute my ugly code.

Isn't there a problem with some of the algorithms posted so far? Some of the swapping algorithms used will produce an array with less than a million valid elements since some of the values would be overwritten. I could be mistaken.

Anyways, here's my version written in C. My algorithm isn't perfect either but it appears to work. I'm fairly new to the whole coding scene so please bear with my sloppiness :)


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 1000000
#define PRINTNUM 100
#define EMPTY -1

int intlist[SIZE], rand_intlist[SIZE];

int
main()
{
int i, r, stepper;
time_t time_start;

/* initialize both arrays. one will hold the
original values from 0-SIZE, and the other
will eventually hold the randomized list. */
for( i = 0; i < SIZE; i++ )
{
intlist[i] = i;
rand_intlist[i] = EMPTY;
}

/* begin runtime timer */
time_start = time(NULL);

/* initialize random number generator */
srand((unsigned) time(NULL));

/* jam each int from intlist into a random index
in rand_intlist. if the index already has a
value in it, step forward to first empty index */
for( i = 0; i < SIZE; i++ )
{
/* generate a random index */
r = (rand() % SIZE) + 1;

if( rand_intlist[r] == EMPTY )
rand_intlist[r] = intlist[i];
else{
stepper = r;
while( rand_intlist[stepper] != EMPTY )
{
stepper++;
if( stepper >= SIZE)
stepper = 0;
}
rand_intlist[stepper] = intlist[i];
}
}

/* print out the first PRINTNUM indexes in the random
array */
for( i = 0; i < PRINTNUM; i++)
printf("%d ", rand_intlist[i]);

/* calculate and display total runtime in seconds */
printf("\n\nRuntime was %g seconds.\n",
difftime(time(NULL), time_start));

return(0);
}


Here is the output....


684249 696483 186011 757723 790090
86803 838656 861840 446115 490176
90094 710363 777080 427131 333770
484574 321165 468814 504111 775804
124038 209797 369018 578115 45509
303905 10493 17597 416348 636272
710910 279101 378716 417749 425735
608643 861936 180076 865423 429493
341501 109497 594007 409184 575247
693866 709235 721107 757550 866356
241557 873417 394898 404528 358844
117213 175058 816746 41901 800012
405271 544362 822467 857403 802918
874734 76681 87981 153156 879609
823081 776883 257624 852375 2318
882850 511778 615018 883251 537900
12375 891725 160775 580516 513739
691585 333839 80844 555306 478639
369062 123989 98238 233088 58424
525675 556211 602917 746998 810836


Runtime was 12 seconds.


Sorry about the size... I'm sure there are more elegant/efficient ways to do it.

Comments (constructive or otherwise) are appreciated.

Cheers,
Arker.

[inkedmn]

Arker-

thanks for contributing! and welcome aboard!

[bwkaz]

Yeah, this thread looks a little old, but since I wasn't here the first time either... how fast is this one on your test machine with your compiler options? 326 milliseconds on mine (the first time I ran it at least), but well, that doesn't really mean much. Seeing as I compiled with -O6 -march=athlon-xp :P

http://3dguios.resnet.mtu.edu/randomize.c

It's truly O(n), if that means anything... just walks the array and swaps each element with another randomly-chosen one. Sure, it's possible that it ends up swapping 1 with 485493 and then 485493 with 1 later, but I'm guessing the probability of that is abysmally low... ;)

[Arker]

Originally posted by bwkaz
Sure, it's possible that it ends up swapping 1 with 485493 and then 485493 with 1 later, but I'm guessing the probability of that is abysmally low... ;)

Maybe I am misinterpreting the swapping algorithm, but isn't it true that as the array approaches 50% "randomized", the chance of the program swapping an already swapped index also approaches 50%? This means that when the last index is being swapped, the chances are almost 100% that it will swap with an already swapped index...lol

I have no idea if what I just said made any sense but I don't know of other ways to say it. Basically, when the program is finished, there will be quite a few dups and quite a few integers between 0-1,000,000 missing from the finished, randomized array.

Am I misunderstanding something here? It's not only possible that I am, it's very likely.

Cheers,
Arker.

[GnuVince]

Arker: They'll all still be there. You just swap them:

[1, 2, 3, 4]
[3, 2, 1, 4]
[2, 3, 1, 4]
[2, 3, 4, 1]
[1, 3, 4, 2]

[Arker]

Originally posted by GnuVince
Arker: They'll all still be there. You just swap them:

[1, 2, 3, 4]
[3, 2, 1, 4]
[2, 3, 1, 4]
[2, 3, 4, 1]
[1, 3, 4, 2]


Ahhhhh... I do see it now. Looks like I made my program do a whole lot more than it needed to...haha Good practise regardless.

Thanks GnuVince,
Arker.

[bwkaz]

It's about a 50% chance that it swaps with an already-swapped element, yes, but that doesn't matter. That actually only makes the array more randomized, since the likelihood of it swapping with the element that should be in that position is still only one out of one million (and some change, because you need to have already swapped the element that should be in that position out to somewhere else).

[Halide]

Originally posted by Strike
Okay, the above code DOES work, but it is a memory HOG. Took 154MB of RAM on my machine to run and I got it done in 518 seconds (on a modest machine). :)

i ran it in 9 seconds

[Dru Lee Parsec]

Hey Arker, Welcome!

The odds of a number being swapped is the same for every entry in the array (at least with the algorithm I used). Essentially I created an array of ints from 1 to 1,000,000 sequentially. Then I looped from 1 to 1,000,000 taking the number at that *index* (note that it's now an index, not the actual int) and swapped it with another int at a random index.

Therefore, as more and more numbers are swapped the odds get higher that any individual integer is no longer in it's original location, but the odds are very low (in fact, it's 1 in a million) that it will get swapped back into it's original location.

Also, I think it's cool that this thread is ressurected. This was the very first programming challenge that we had here on Coderforumns. It makes me proud to see it live again. :D

[THINKPascalUser]

here's Some ol' fashioned BASIC:


word = 0
char = 0
Newchar:
if char = 0 then
print random(9);
char = char + 1
end if

if char <> 0 then
for y = 1 to 4
print random(9);
next y
print " ";
char = char + 1
if char = 10 then
char = char - 10
word = 1 + word
if word = 1000 then
goto Quit
end if
end if
end if


goto Newchar

Quit:
end


It only outputs numbers...
no hex.. any help?

---Edit---
Made presentation neater

[Strike]

Eeek, wrong thread.

[CaptainCode]

Since this thread was resurected, and I'm new here, here's mine done in C++:


#include <iostream>
#include <vector>
#include <algorithm>
#define WIN32_LEAN_AND_MEAN // Exclude rarely-used stuff from Windows headers
#include <windows.h>
#include <string>
#include <time.h>
using namespace std;
#define SIZE 1000000

int main(int argc, char* argv[])
{
__int64 frequency;
__int64 startticks;
__int64 endticks;
srand(time(0));
QueryPerformanceFrequency(reinterpret_cast<LARGE_INTEGER*>(&frequency));


cout << "Creating 1,000,000 element vector" << endl;
QueryPerformanceCounter(reinterpret_cast<LARGE_INTEGER*>(&startticks));
vector<int> a;
a.resize(SIZE);

for(int i=0;i<SIZE;i++)
a[i] = i;
random_shuffle(a.begin(), a.end());
QueryPerformanceCounter(reinterpret_cast<LARGE_INTEGER*>(&endticks));
double time = (static_cast<double>(endticks)-static_cast<double>(startticks))/frequency;
for(i = 0; i<100; i++)
{ if(i%9 == 0)
cout << endl;
cout << a[i] << " ";
}
cout << "\nTotal time: " << time << " seconds" << endl;
string line;
getline(cin, line);

return 0;
}


NOTE: will only run on Windows because of the calls to the windows API functions. I used them to get a very accurate number for the time.

Results on an 664MHz PIII:

Creating 1,000,000 element vector

550240 11857 28367 449739 126628 203278 32544 293811 695908
192198 86420 829776 765064 403212 31109 985149 5768 170317
686776 688747 746348 587237 978116 864372 796406 336161 695886
605328 888706 580286 621536 889065 707688 759756 257888 73345

804354 49637 33018 519945 31236 644776 148584 535627 275964
447485 951118 951597 962094 953301 340744 528162 89262 976168
734528 447828 31950 484121 646992 363363 911936 523201 366708
662879 881822 190301 392872 13365 995096 438297 353254 898613
346386 21164 593178 995765 326802 67218 737960 969519 636956
121153 77050 61510 48286 465576 3259 792343 7812 913844
32070 222709 226330 68614 142724 852398 663174 126593 47256
951729
Total time: 0.337116 seconds



I'll test it on my Athlon 1.4GHz later today :)
**takes about 270 ms on my Athlon.

Edited for small fixes like getting rid of _TCHAR*
Also realized that I needed to seed the rand function as the random_shuffle was shuffling in the same order all the time.
This does not change the time however.

[DNAunion2000]

DNAunion: CaptainCode, I have a few questions.

1) I doubt it would make any kind of measurable difference, but couldn't:


vector<int> a;
a.resize(1000000);


be done more efficiently as follows:


vector<int> a(1000000);



2) Again, not that it's going to make a huge difference, but shouldn't the screen output call (cout << "Creating 1,000,000 element vector" << endl; ) be moved from within the timed block to before it?

3) I seem to remember reading that prefix increment (++i) is faster than postfix (i++). If that is true (and it may not be), the following, after being repeated a million times, might shave a few "nanoseconds" off the process:


for(int i=0;i<1000000;++i)


4) I see you used reinterpret_cast<datatype> variable;. I've seen it and static_cast<datatype> variable; used in a couple of books, but a search of their indices and trips to the indicated pages does not really explain why they are used instead of, and also superior to, a simpler cast (datatype)variable;. Can you explain?

[CaptainCode]

Originally posted by DNAunion2000
DNAunion: CaptainCode, I have a few questions.

1) I doubt it would make any kind of measurable difference, but couldn't:


vector<int> a;
a.resize(1000000);


be done more efficiently as follows:


vector<int> a(1000000);



You'd think that that would be a bit faster, but I ran 3 tests with it being resized after creation, and 3 tests with it being sized at creation, and it's actually about ~10ms faster resizing after it's created.



2) Again, not that it's going to make a huge difference, but shouldn't the screen output call (cout << "Creating 1,000,000 element vector" << endl; ) be moved from within the timed block to before it?


Yes, you're right. Small oversight on my part. It doesn't seem to make a big(noticable) difference though.


3) I seem to remember reading that prefix increment (++i) is faster than postfix (i++). If that is true (and it may not be), the following, after being repeated a million times, might shave a few "nanoseconds" off the process:


for(int i=0;i<1000000;++i)



You might be right about that, but I have no idea if that's true or not.


4) I see you used reinterpret_cast<datatype> variable;. I've seen it and static_cast<datatype> variable; used in a couple of books, but a search of their indices and trips to the indicated pages does not really explain why they are used instead of, and also superior to, a simpler cast (datatype)variable;. Can you explain?

reinterpret_cast and static_cast(as well as dynamic_cast, const_cast) are ways of telling the compiler to treat something a different way than it thinks it should.

static_cast is basically the same as doing a regular cast like (int)some_double;

While you can use normal casting for everything that those cast operators can do, the operators make it clear what type of cast you are doing and so it makes it easier to read the code.

Example:
COM in Windows uses a lot of void pointers for creation of objects, and getting interface pointers. There are generic functions for creating any type of object and/or receiving any type of interface on that object. They do this by having you pass in a void pointer, and the UUID of the object/interface you want.

You get a void pointer to an interface, which is really not of type void at all. You can tell the compiler with reinterpret_cast to think of the void pointer as the type you requested.

[DNAunion2000]

DNAunion: 3) I seem to remember reading that prefix increment (++i) is faster than postfix (i++). If that is true (and it may not be), the following, after being repeated a million times, might shave a few "nanoseconds" off the process:

for(int i=0;i<1000000;++i)



CaptainCode: You might be right about that, but I have no idea if that's true or not.

DNAunion: I made myself curious, so checked into it a bit. Apparently…

1) preincrement is more efficient than postincrement for programmer-defined types

2) preincrement is at least as efficient as postincrement for built-in data types (preincrement may be more efficient, but if not, then the two are equally efficient).

3) For STL iterators, preincrement is more efficient than postincrement.


”3. for( /*...*/ i++ )
^3^

This one was more subtle. Preincrement [is] never less efficient than postincrement and it's often more efficient, because for postincrement the object must increment itself and then return a temporary containing its old value. Note that this is true even for builtins like int (although for builtins some compilers are smart enough to avoid the overhead associated with an unused return value for postincrementing a builtin).

[Guideline] Prefer preincrement, avoid postincrement.”
(http://pierre.aubert.free.fr/divers/gotw/gotw002a.html)

9. Use the preincrement and predecrement operators

The compiler is not always smart enough to figure out, if the rvalue of an increment is used or not. So it has to save and restore that value when producing code for the postincrement and postdecrement operators, even if this value is never used. To avoid the additional overhead, use the preincrement and predecrement operators if you don't need the resulting value. That means, use
...
++i;
...
instead of
...
i++;
...

(http://www.cc65.org/doc/coding-9.html )

”So, if you only want to use the increment operator to increment a value, and don't care about the returned value from the increment operator: use the preincrement form of your operator .

As an example, consider the familiar use of ++ in a for-loop. If your counter variable is a user-defined object, such as a Rational, use this code:

Rational r;
for ( r = 0; r < limit; ++r) …..


in preference to this code:


Rational r;
for ( r = 0; r < limit; r++) …..


The latter is much less efficient, as it involves the creation of an unused Rational object, and a call to the copy constructor to return its value to the caller of the operator++(int) method.

Note that such efficiency considerations apply only to user-defined versions of the increment operator. The built-in types handle both the preincrement and postincrement versions of the operator with equal efficiency.” (http://www.ul.ie/~flanagan/ee6721/basoper/basoper.html)

[CaptainCode]

Good to know. Thanks for the info.

[GnuVince]

Here it is in Squeak. it's quite slow though, it takes 27 seconds:


Array variableSubclass: #RandomArray
instanceVariableNames: 'size arr time '
classVariableNames: ''
poolDictionaries: ''
category: 'Array Shuffler'!

!RandomArray methodsFor: 'as yet unclassified' stamp: 'vfb 7/22/2003 09:24'!
getTime
^ time! !

!RandomArray methodsFor: 'as yet unclassified' stamp: 'vfb 7/22/2003 09:24'!
init
size _ 1000000.
arr _ Array new: size.
1 to: size do: [ :i | arr at: i put: i ].! !

!RandomArray methodsFor: 'as yet unclassified' stamp: 'vfb 7/22/2003 09:27'!
shuffleArray
| temp x random |
random _ Random new.
random seed: Time totalSeconds.
1 to: size do: [ :i |
x _ random nextInt: size.
temp _ arr at: i.
arr at: i put: (arr at: x).
arr at: x put: temp.
].

! !

!RandomArray methodsFor: 'as yet unclassified' stamp: 'vfb 7/22/2003 09:27'!
timeIt
time _ Time millisecondsToRun: [ self shuffleArray. ].! !


Copy that code in Array Shuffle.st and fileIn it in Squeak. Here's the output:


a _ RandomArray new init.
a timeIt.
a getTime 27259


I don't know why it takes so long, for most tasks Squeak was faster than Python and Ruby. Oh well.

[DNAunion2000]

/*DNAunion*/ Well, I wasn't going to do it VFP because it's not known as being a fast language (fast for database stuff, but not the "normal" things). But when I saw some results in or near the double digits....


RAND(-1) && seed pseudo-random number generator with system clock

CREATE CURSOR csrIntegers (value N(6))
FOR lnLcv = 1 TO 1000000
INSERT INTO csrIntegers (value) VALUES (lnLcv - 1)
ENDFOR


lnTimeA = SECONDS()
SCAN
lnRecno = RECNO()
lnFirstValue = value

lnGo = FLOOR((RAND() * 1000000)) + 1
GO (lnGo)
lnSecondValue = value
REPLACE value WITH lnFirstValue

GO (lnRecno)
REPLACE value WITH lnSecondValue
ENDSCAN
lnTimeB = SECONDS()


? lnTimeB - lnTimeA

lcString = "*"
GO TOP
SCAN NEXT 100
lcString = lcString + ALLTRIM(STR(value)) + ", "
IF (RECNO() % 10 = 0)
KEYBOARD lcString + CHR(13)
lcString = "*"
ENDIF
ENDSCAN

CLOSE ALL



Four runs:
7.454 seconds
7.360 seconds
7.344 seconds
7.422 seconds

Last run's output was as follows:

*1792, 28674, 500838, 224727, 806275, 720040, 891558, 30810, 814540, 705607,
*639757, 26211, 370596, 590510, 104542, 681139, 870121, 252319, 125592, 262707,
*622809, 354222, 17732, 464970, 558807, 590193, 724820, 285840, 657412, 712864,
*685917, 204145, 615869, 429641, 121214, 912238, 471115, 11018, 159027, 351616,
*193268, 91042, 33185, 265314, 347246, 923643, 862750, 431580, 647323, 94535,
*105277, 762408, 785537, 322612, 752453, 25927, 653151, 622173, 824885, 738546,
*162080, 787269, 589913, 634741, 569784, 127451, 737919, 303921, 371628, 427333,
*340732, 586380, 51905, 68198, 986866, 807692, 803079, 455548, 580565, 736421,
*423039, 6440, 253867, 414298, 18902, 219985, 320436, 306238, 70685, 806309,
*535184, 825735, 457012, 845159, 22158, 390591, 58471, 804996, 775097, 139176,

Run on a Pentium IV 1.8 GHz with 512 MB SDRAM running Windows 2000 Professional SP2

[gish]

nice...

[sirking]

Originally posted by Strike
Okay, the above code DOES work, but it is a memory HOG. Took 154MB of RAM on my machine to run and I got it done in 518 seconds (on a modest machine).

damn, if you're talking about the python code:

#!/usr/bin/env python

import time, random

foo = [x for x in range(1000000)]
start = time.time()
random.shuffle(foo)
end = time.time()
duration = end - start
for i in range(100):
print foo[i]

print "Took %d seconds to do." % duration


it took 2 seconds on my machine.

[geroditus]

<?php
/*
Results for 500mhz G4 TiBook 768MB RAM:

one million: 5.4 secs
hundred thousand: 0.4 secs

*/
$arr = range(0,1000000); // one million
//$arr = range(1,100000); // one hundred thousand

$start = microtime_float();
shuffle($arr);
$end = microtime_float();

echo "time: ".($end-$start)." seconds\n<br>\n";

for($i=0;$i<20;$i++) {
echo $arr[$i]." ";
}
echo "\n";

function microtime_float()
{
list($usec, $sec) = explode(" ", microtime());
return ((float)$usec + (float)$sec);
}

?>