Forum huvudsida -> Programmering -> Java svår slumpning
Sidor: 1
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 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 ------------------------- 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:
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
Du får inte posta i den här tråden | Till toppen
Datum
2024-05-05 19:10
Vecka: 18
Besökare
Inloggade: 0
Gäster: 605
Medlemmar
Medlemmar: 53576
Forum
Senaste inlägget: HAHA MÄNNISKAN LEVER ÄN (13:45 - 18:e Januari 2019, av Hetzz)
Wiki
Senaste ändringen:
3D (rev: 1, tid: 09:40 - 13:e November 2015)
Chatt
#blinkenlights @ Libera.Chat
Gratis shellkonton för IRC, webbsidor mm.