Forum: Java svår slumpning

Forum huvudsida -> Programmering -> Java svår slumpning

Sidor: 1

Till botten

JavaChick 16:25 - 13:e Mars 2007 | Post #1
Medlem
Inlägg: 1


Skicka PM 		Hejsan!

Har problem som jag inte ser någon direkt lösning på själv...

Jag ska ha en vektor som lagrar inmatade ord (inget problem där inte) MEN sedan ska dessa inmatade ord (vektorspositioner) slumpas genom att 2 slumpmässigt valda ord byter plats med varandra i vektorn och denna procedur ska också utföras lika många gånger som antalet valda ord som man matat in.

Hur gör jag en metod i Java som blandar dessa ord som ovan nämnt?

-------------------------


Independence 17:01 - 13:e Mars 2007 | Post #2
Administratör
Inlägg: 1800


Skicka PM 		Pseudo-kod, lite blandning av java och python eller nåt:


for word in vector
{
pos1, pos2 = random(), random();
vector[pos1], vector[pos2] = vector[pos2], vector[pos1];
}


Um, vet inte om det gör vad du ville heller riktigt, men det kanske ger något tips Smiley
Jag förstod inte exakt vad du ville göra

-------------------------

Vi är riddarna som säger fiskbulle!



Senast redigerad 17:02 - 13:e Mars 2007


FunkyChicken 20:45 - 13:e Mars 2007 | Post #3
Nyhetsredaktör
Inlägg: 800


Skicka PM 		Möjligt att det där funkar i java, men i C++ exempelvis krävs väl att man mellanlagrar det första värdet i en extra variabel, och sedan skriver in det på sin nya position (annars kommer man ju bara kopiera tillbaka det andra värdet) - men det är kanske uppenbart...


Independence 21:41 - 13:e Mars 2007 | Post #4
Administratör
Inlägg: 1800


Skicka PM 		    Citat av FunkyChicken:
Möjligt att det där funkar i java, men i C++ exempelvis krävs väl att man mellanlagrar det första värdet i en extra variabel, och sedan skriver in det på sin nya position (annars kommer man ju bara kopiera tillbaka det andra värdet) - men det är kanske uppenbart...


Det var där python-biten kom in Smiley

-------------------------

Vi är riddarna som säger fiskbulle!


sdac 15:00 - 16:e Mars 2007 | Post #5
Medlem
Inlägg: 235


Skicka PM 		    Citat av FunkyChicken:
Möjligt att det där funkar i java, men i C++ exempelvis krävs väl att man mellanlagrar det första värdet i en extra variabel


Ja, det är lite märkligt i och med att det finns en processorinstruktion som skulle kunna göra jobbet på bara några få klockcykler, men vill man göra det i C++ får man använda temporära variabler och hålla på?

Det går visserligen att emulera en XCHG-instruktion genom att köra tre XOR:

  1.  
  2. int x = 1, y = 2;
  3.  
  4. x ^= y;
  5. y ^= x;
  6. x ^= y;
  7.


Eller så kan man köra inlineassembler med en XCHG såklart, men det är ju inte så portabelt...

Ja just det, tråden handlade ju om Java märkte jag nu. Men det går antagligen att swappa med XOR där också.


FunkyChicken 22:20 - 16:e Mars 2007 | Post #6
Nyhetsredaktör
Inlägg: 800


Skicka PM 		Sen är frågan hur många instruktioner C++ använder för en XOR på sina variabler... knappast bara en? Men du har rätt i att det faktiskt är lustigt att det inte finns nån färdig funktion för detta.


ozamosi 22:39 - 16:e Mars 2007 | Post #7
Administratör
Inlägg: 1129


Skicka PM 		Jag finner det sannolikt att gcc kan se att tmp enbart används för att byta plats på värden, och därför optimera det hela så att det blir en XCHG.

-------------------------
Ljusblå


sdac 23:05 - 16:e Mars 2007 | Post #8
Medlem
Inlägg: 235


Skicka PM 		    Citat av ozamosi:
Jag finner det sannolikt att gcc kan se att tmp enbart används för att byta plats på värden, och därför optimera det hela så att det blir en XCHG.


Stämmer att det är väldigt sannolikt, och ännu mer sannolikt att den konverterar tre XOR till en XCHG, i och med att en XCHG egentligen är tre XOR utförda av processorn, bara att det är en instruktion.

x ^= y;
blir exakt en processorinstruktion.
xor x, y

Och tre XOR i rad fattar väl vilken kompilator som helst att den kan förkorta till en XCHG när den kör assemblyanalyseringspasset, annars är den dum.

FunkyChicken: Jo, det blir faktiskt bara en instruktion.


FunkyChicken 01:03 - 17:e Mars 2007 | Post #9
Nyhetsredaktör
Inlägg: 800


Skicka PM 		Faktiskt ganska intressant. Satt och läste lite på http://en.wikipedia.org/wiki/XOR_swap_algorithm

"On modern (desktop) CPUs, the XOR technique is considerably slower than using a temporary variable to do swapping. One reason is that modern CPUs strive to execute commands in parallel. In the XOR technique, the inputs to each operation depend on the results of the previous operation, so they must be executed in strictly sequential order"

"...compilers are more likely to recognize and optimize a conventional (temporary-based) swap than to recognize the high-level language statements that correspond to a XOR swap."

Men precis som du sa:
"when the target architecture supports it, the compiler can use a single XCHG (exchange) instruction which performs the swap in a single operation."

Och förklaringen (?) till att XCHG saknas i C++:
"The PDP-10 inherited the PDP-6's EXCH instruction, but the PDP-11 (the machine on which the C programming language was developed) did not. "

Dock:
"However, the XCHG instruction in modern processors (e.g. x86) should only be used to swap registers and not memory"

Logiskt, men komlicerar det hela en del:
"The XOR swap is also complicated in practice by aliasing. If an attempt is made to XOR-swap the contents of some location with itself, the result is that the location is zeroed out and its value lost."

Till sist kan man notera att metoden inte bara fungerar med XOR utan med alla reversibla operationer, tex:
X := X + Y;
Y := X - Y;
X := X - Y;
Tada!

Nej, jag har inget bättre för mig. Särskilt borde jag inte tentaplugga...


sdac 01:49 - 17:e Mars 2007 | Post #10
Medlem
Inlägg: 235


Skicka PM 		    Citat av FunkyChicken:

"On modern (desktop) CPUs, the XOR technique is considerably slower than using a temporary variable to do swapping. One reason is that modern CPUs strive to execute commands in parallel. In the XOR technique, the inputs to each operation depend on the results of the previous operation, so they must be executed in strictly sequential order"


Det där stämmer inte riktigt, temporära variabler är lika beroende av föregående operationer som tre XOR i rad är. Om X ska flyttas till Z utan att Z ska ersättas måste Z läggas i Y först. Z kan sedan flyttas från Y till X endast EFTER att X flyttats klart till Z. Processorn kan inte trolla och göra det "parallellt" utan att något ersätts och operationen går snett.

    Citat av FunkyChicken:

Till sist kan man notera att metoden inte bara fungerar med XOR utan med alla reversibla operationer, tex:
X := X + Y;
Y := X - Y;
X := X - Y;


Ja, det är ytterligare en metod. Gjorde en benchmark och fick fram att den är ungefär jämnsnabb med XOR-metoden. Ren XCHG var snabbast.

Tror vi hamnat lite för mycket off topic.


main 02:44 - 17:e Mars 2007 | Post #11
Medlem
Inlägg: 40


Skicka PM 		Kan Java hantera pekare?

-------------------------
- Real programmers code in binary


FunkyChicken 14:28 - 17:e Mars 2007 | Post #12
Nyhetsredaktör
Inlägg: 800


Skicka PM 		Typ. Java använder "referenser".


main 16:27 - 17:e Mars 2007 | Post #13
Medlem
Inlägg: 40


Skicka PM 		Som referensvariabler i C++?

-------------------------
- Real programmers code in binary


Sidor: 1

Forum huvudsida -> Programmering -> Java svår slumpning
Atom feed

Du får inte posta i den här tråden | Till toppen