Seite 136 von 136 ErsteErste ... 3686126132133134135136
Ergebnis 2.026 bis 2.037 von 2037

Thema: [Programmiererstammtisch] "Zum ächzenden Compiler"

  1. #2026
    Civ4 BASE Coder Avatar von rucivfan
    Registriert seit
    10.07.11
    Ort
    Antarktika
    Beiträge
    18.584
    Zitat Zitat von Shakka Beitrag anzeigen
    Also:
    -keine Bücher mehr kaufen
    -keine Musik mehr kaufen
    -keinen werbefinanzierten Mist (TV, Radio, Website) mehr ansehen
    -keine Zeitung oder Zeitschrift mehr kaufen
    -keine Kinobesuche
    Mal von Fachbüchern und einigen wenigen Webseiten mit Ausnahmen beim Werbefilter abgesehen, halte ich mich daran schon lange. Bei Musik habe ich noch nie verstanden, warum man sich diese anhören sollte. TV und Radio braucht niemand.Zeitung und Zeitschriften schreiben immer nur über veraltete Sachen. Kinobesuche so teuer wie die spätere Scheibenveröffentlichung? Wer geht da noch ins Kino.

  2. #2027
    Registrierter Benutzer Avatar von SvenBvBFan
    Registriert seit
    12.05.13
    Ort
    BaWü
    Beiträge
    5.969
    Ich bin Brian und meine Frau ist auch Brian!
    - Life of Brian 1979

    Zitat Zitat von Yttrium Beitrag anzeigen
    Einen fünften Teil [Civilization] wird es 100%ig nicht geben, User.
    - civforum.de 2001

  3. #2028
    Registrierter Benutzer Avatar von Flunky
    Registriert seit
    21.03.12
    Beiträge
    15.733
    Willkommen Einheitsyoutube. Mit den großen Plattenfirmen werden Einheitsverträge gemacht und unbekannte Künstler sicherheitshalber gesperrt. Könnt ja einer gegen die kostenlose Werbung klagen...
    1525. Wir finden Astronomie in ner Hütte.

  4. #2029
    ❦ Ser Tira Tyrell ❦
    Registriert seit
    03.07.11
    Ort
    Leonberg, BW
    Beiträge
    17.095
    Wie lange dauert es eigentlich, bis so ein A*-Algorithmus zur Wegfindung abgeschlossen ist? Sagen wir mal, das Ziel liege in einem Abstand von 10 Feldern.

    Ich habe erst mal einen halbfertigen Algorithmus in Lua geschrieben, der alle Felder in alle Richtungen bis zu 10 Felder Abstand vom Startpunkt aus abtastet.
    Achtung Spoiler:
    Bild

    Dafür braucht er ein paar Sekunden, was mir ziemlich lange erscheint, vor allem da es dazu nur 4764 Schritte benötigt. Außerdem habe ich bereits darauf geachtet, so wenig wie möglich auf Tables zurückzugreifen und möglichst mit einfachen Zahlen zu rechnen, um die Performance zu schonen. Wenn ich zu sehr mit Tables anstelle von Zahlen arbeite, dauert der Algorithmus nämlich noch deutlich länger.

    Ich befürchte so langsam, dass Lua einfach viel zu langsam ist für einen gescheiten A*-Algorithmus. Oder kann man das noch retten?

    Edit: Hier mein Lua-Code, falls jemand was damit anfangen kann:

    Achtung Spoiler:
    Code:
    function GetPlotPriority( pPlot, pAdjacentPlot)
        return 0 --todo: needs some rework
    end
    
    function IsValidNextFrontPlot( FrontPlotList, pPlot )
        if not pPlot then return false; end
        local iPlotIndex = pPlot:GetIndex()
        for _,frontplotItem in pairs(FrontPlotList) do
            if( frontplotItem.iPlotID == iPlotIndex ) then
                return false;
            end
            for _,kNextPlot in pairs(frontplotItem.NextPlots) do             
                if( kNextPlot.iPlotID == iPlotIndex ) then
                    return false;
                end
            end
        end    
        return true;
    end
    
    function InitiateFront( pPlot ) --todo: add more parameters
        local NewFrontPlotList = {}
        local frontplotNew :table = {
            iPlotID = pPlot:GetIndex(),
            iPosX = pPlot:GetX(),
            iPosY = pPlot:GetY(),                    
            iStep = 0, -- needs rework
            NextPlots = {},
            PathPlots = {},                 
            iPriority = 0 --the lower this value the higher the priority
        };    
        table.insert( frontplotNew.NextPlots, {
            iPlotID = pPlot:GetIndex(),
            iNextPriority = 0
        });
        table.insert( frontplotNew.PathPlots, {
            iPlotID = pPlot:GetIndex(),
            iStep = 0
        });
        table.insert( NewFrontPlotList, frontplotNew )
        return NewFrontPlotList;
    end
    
    function NextFrontierPlots( OldFrontPlotList, iOldPriority )
        local iCalculationSteps = 0
        local NewFrontPlotList = {}
        local iHighestPriority = -1
        for _,frontplotOld in pairs(OldFrontPlotList) do    
            iHighestPriority = frontplotOld.iPriority
            if( frontplotOld.iPriority <= iOldPriority ) then
                local pFrontPlot = Map.GetPlotByIndex(frontplotOld.iPlotID)
                -- print("pFrontPlot Coordinates: " .. pFrontPlot:GetX() .. "; " .. pFrontPlot:GetY() )
                for _,kNextPlot in pairs(frontplotOld.NextPlots) do 
                    iHighestPriority = kNextPlot.iNextPriority
                    if( kNextPlot.iNextPriority <= iOldPriority ) then                    
                        local pNextPlot = Map.GetPlotByIndex(kNextPlot.iPlotID)
                        -- print("------- pNextPlot Coordinates: " .. pNextPlot:GetX() .. "; " .. pNextPlot:GetY() )
                        kNextPlot = nil --delete table item
                        local frontplotNew :table = {
                            iPlotID = pNextPlot:GetIndex(),
                            iPosX = pNextPlot:GetX(),
                            iPosY = pNextPlot:GetY(),                    
                            iStep = frontplotOld.iStep + 1, -- needs rework
                            NextPlots = {},
                            PathPlots = {},                 
                            iPriority = -1 --the lower this value the higher the priority
                        };    
                        
                        --Get Data for next plots:                        
                        local iHighestNextPriority = -1
                        for sDirection,iDirection in pairs(DirectionTypes) do
                            if iDirection ~= DirectionTypes.NO_DIRECTION and iDirection ~= DirectionTypes.NUM_DIRECTION_TYPES then                            
                                local pAdjacentPlot = Map.GetAdjacentPlot(pNextPlot:GetX(), pNextPlot:GetY(), iDirection)
                                if( IsValidNextFrontPlot( OldFrontPlotList, pAdjacentPlot ) ) then
                                    -- print("################ pAdjacentPlot Coordinates " .. "for " .. sDirection .. " : " .. pAdjacentPlot:GetX() .. "; " .. pAdjacentPlot:GetY() )
                                    iCalculationSteps = iCalculationSteps + 1
                                    local kNextPlotDatas :table = {
                                        iPlotID = nil,
                                        iNextPriority = nil
                                    };
                                    kNextPlotDatas.iPlotID = pAdjacentPlot:GetIndex()
                                    kNextPlotDatas.iNextPriority = GetPlotPriority( pNextPlot, pAdjacentPlot )
                                    table.insert( frontplotNew.NextPlots, kNextPlotDatas )
                                    if( iHighestNextPriority > kNextPlotDatas.iNextPriority ) then
                                        iHighestNextPriority = kNextPlotDatas.iNextPriority
                                    end
                                end
                            end
                        end
                        
                        frontplotNew.iPriority = iHighestNextPriority
                        -- table.sort(frontplotNew.NextPlots, function(a, b) return a.iNextPriority > b.iNextPriority end) --see ReligionScreen.lua
                        
                        --save path plots:
                        frontplotNew.PathPlots = frontplotOld.PathPlots            
                        table.insert( frontplotNew.PathPlots, {
                            iPlotID = pFrontPlot:GetIndex(),
                            iStep = frontplotNew.iStep
                        });
                        table.insert( NewFrontPlotList, frontplotNew )
                    end
                end    
            end
            if( next(frontplotOld.NextPlots) ~= nil ) then --if old front plot still has valid adjacent plots
                -- table.insert( NewFrontPlotList, frontplotOld ) --save old front plot in new front
            end
        end
        return NewFrontPlotList, iHighestPriority, iCalculationSteps;
    end


    Edit2: Es kann auch daran liegen, dass die Suche in alle Richtungen so rechenintensiv ist. Mein unfertiger Algorithmus könnte also noch viel schneller werden, wenn ich wie beim richtigen A* effizient suchen würde. Die Anzahl der Rechenschritte steigt jedenfalls deutlich an, wenn man in alle Richtungen sucht. Bei einem Abstand von 6 Feldern geht es noch sehr schnell, bei 8 "laggt" es ein klein wenig, aber spätestens ab 10 wird es spürbar langsamer:
    Achtung Spoiler:

    Abstand Rechenschritte
    5 186
    6 378
    7 762
    8 1274
    9 2536
    10 4764

    Angehängte Grafiken Angehängte Grafiken
    Geändert von Tiramisu (23. Juni 2018 um 03:02 Uhr)
    Tritt dem REICH bei und werde Teil von etwas Großem!


    Achtung Spoiler:
    PHP-Code:
                    ....77$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$..                   
                    ....
    DMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMD..                   
                    ..
    MM=:::::::::::::::::::::::::::::::::::~~=MM                   
                
    ... =+77~~~~~:::::::::::~::::::::::::~:::::~~~=II== . .             
               . . ,
    NM~:~~~~~::::::::,,::::::::~~::::,:::::~::~:~NM, .              
               .. .,
    MM~=~~:::::,::::::,:II~::::?I~,:::::::::~~~~~MM,...             
                   ,
    MM~~~~:::==~:::::,::==::,::==:,,::::::::::~:~MM, ..             
                .  ,
    MM:~:::::??=:::::::::::::,:::,,::::::::::::~:MM,     . . ....   
                .  ,
    MM:~::::::~,:::::::::::,:::DMMM?:::~I?:::::~:MM,.=MMMM.    . .  
                .  ,
    MM:~::,,:,:::::::::::::,+MNI++?ZND,,:::,:::~:MMNMZ+++?NM:. ...  
      ,  .. .    ..:
    MM:~::::::::::::::::::::=MM???+OMD::::::~::~~MMMMO????MM:   .   
      
    MMMMMMMMM  ..,MM:~::::::::::::::??::::=MM????++IMZ,::::::~~MMI??????MM:   .   
      
    MMOZZZZMM+?, ,MM:~::::::::::::::==:,::=MM???????OI???????IIZ$?++????MM:   .   
    MMZZ7I+Z7MMI?IMM:~:::::::~~~:::::,::::=MM????????I$$7$7$7$$+II?I????MM:   .   
     .
    MMMMO????MMMMMMM:~::,::::+I~:,::::::::=MM????????????????????++?II??MM:  ...  
    . . 
    MMMMD+II+ZMMMM:~::::::::~,::::::?7OMO??????+?+?????I?????????I???+?+DMM,.   
    ..  
    MMNMM?+??OMMMM:~::::~:::::::::,~??8MO???????????+?++?????++??+II????OMM ..  
    . .  .:
    NMMM??++IMM:~::+I?:::,:::::::,:ZM8=+I???: ,MO?+?????????, ~MM?I??OMM .   
      ...   .
    MMMMMMNMM:~::::::::::,::::::,$MO+??+??ZMMMO?+??I+?MN+?NMNMM+???OMM.    
      ...  ..??
    I?ZMMMM:~:::::,:::::~~=::::ZMO+?++++IOZO7????+??ZZ?+ZZZZZ++++OMM...  
      ....  .... 
    IMMMM:~::::,::::::=I?~:::$MO+?==~=+???????+???????+??+?====ZMM...  
               . . :
    MM~~~~:::?I~::::::,:::$MO?I~====?IMO????7MN????DMO??====ZMM...  
                  ..
    MM~~~::::==::::::::::,=?I$Z+++++?IMDZZZ$OMMZZZZNMO?+++$$+?+...  
                   :
    MM~~~~=~::::::::::::::::+MM???????MMMMMMMMMMMMMMMOI??+MM~. ...  
                 
    7MMMMMM=~:~~~~~~~~~~~~~~~~:~::NMI+??????????++?+?++???+MM........  
               ::?
    8O8OOO?==+++++==++++=+++??+==NM7II$I7I7I7II7II77III7I7$$ .        
               
    MM$+I???+MMMMMMMMMMMMMNMMMMMMMMMMMMNMMMMMMMMMMMMMMMMMMMMM. ..        
               
    NN7++??MMMM?.,MM7?+?7MM....... ...MM7++?IMM, +MM+???8MI..  ..        
               
    MMZ777$NMII~ .MMZ$7$7I+, . .     .?7I$77OMM..:I?7$$$I?=.             
               
    NMMMMMMMM. ..:MMMMMMI   . .      ,. IMMMMMM~ ,..MMMM: ,. 

  5. #2030
    ❦ Ser Tira Tyrell ❦
    Registriert seit
    03.07.11
    Ort
    Leonberg, BW
    Beiträge
    17.095
    Ich konnte meinen Code jetzt selber optimieren. Vielen Dank für eure Hilfe!
    Tritt dem REICH bei und werde Teil von etwas Großem!


    Achtung Spoiler:
    PHP-Code:
                    ....77$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$..                   
                    ....
    DMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMD..                   
                    ..
    MM=:::::::::::::::::::::::::::::::::::~~=MM                   
                
    ... =+77~~~~~:::::::::::~::::::::::::~:::::~~~=II== . .             
               . . ,
    NM~:~~~~~::::::::,,::::::::~~::::,:::::~::~:~NM, .              
               .. .,
    MM~=~~:::::,::::::,:II~::::?I~,:::::::::~~~~~MM,...             
                   ,
    MM~~~~:::==~:::::,::==::,::==:,,::::::::::~:~MM, ..             
                .  ,
    MM:~:::::??=:::::::::::::,:::,,::::::::::::~:MM,     . . ....   
                .  ,
    MM:~::::::~,:::::::::::,:::DMMM?:::~I?:::::~:MM,.=MMMM.    . .  
                .  ,
    MM:~::,,:,:::::::::::::,+MNI++?ZND,,:::,:::~:MMNMZ+++?NM:. ...  
      ,  .. .    ..:
    MM:~::::::::::::::::::::=MM???+OMD::::::~::~~MMMMO????MM:   .   
      
    MMMMMMMMM  ..,MM:~::::::::::::::??::::=MM????++IMZ,::::::~~MMI??????MM:   .   
      
    MMOZZZZMM+?, ,MM:~::::::::::::::==:,::=MM???????OI???????IIZ$?++????MM:   .   
    MMZZ7I+Z7MMI?IMM:~:::::::~~~:::::,::::=MM????????I$$7$7$7$$+II?I????MM:   .   
     .
    MMMMO????MMMMMMM:~::,::::+I~:,::::::::=MM????????????????????++?II??MM:  ...  
    . . 
    MMMMD+II+ZMMMM:~::::::::~,::::::?7OMO??????+?+?????I?????????I???+?+DMM,.   
    ..  
    MMNMM?+??OMMMM:~::::~:::::::::,~??8MO???????????+?++?????++??+II????OMM ..  
    . .  .:
    NMMM??++IMM:~::+I?:::,:::::::,:ZM8=+I???: ,MO?+?????????, ~MM?I??OMM .   
      ...   .
    MMMMMMNMM:~::::::::::,::::::,$MO+??+??ZMMMO?+??I+?MN+?NMNMM+???OMM.    
      ...  ..??
    I?ZMMMM:~:::::,:::::~~=::::ZMO+?++++IOZO7????+??ZZ?+ZZZZZ++++OMM...  
      ....  .... 
    IMMMM:~::::,::::::=I?~:::$MO+?==~=+???????+???????+??+?====ZMM...  
               . . :
    MM~~~~:::?I~::::::,:::$MO?I~====?IMO????7MN????DMO??====ZMM...  
                  ..
    MM~~~::::==::::::::::,=?I$Z+++++?IMDZZZ$OMMZZZZNMO?+++$$+?+...  
                   :
    MM~~~~=~::::::::::::::::+MM???????MMMMMMMMMMMMMMMOI??+MM~. ...  
                 
    7MMMMMM=~:~~~~~~~~~~~~~~~~:~::NMI+??????????++?+?++???+MM........  
               ::?
    8O8OOO?==+++++==++++=+++??+==NM7II$I7I7I7II7II77III7I7$$ .        
               
    MM$+I???+MMMMMMMMMMMMMNMMMMMMMMMMMMNMMMMMMMMMMMMMMMMMMMMM. ..        
               
    NN7++??MMMM?.,MM7?+?7MM....... ...MM7++?IMM, +MM+???8MI..  ..        
               
    MMZ777$NMII~ .MMZ$7$7I+, . .     .?7I$77OMM..:I?7$$$I?=.             
               
    NMMMMMMMM. ..:MMMMMMI   . .      ,. IMMMMMM~ ,..MMMM: ,. 

  6. #2031
    Macht Musik Avatar von Peregrin_Tooc
    Registriert seit
    21.05.05
    Ort
    Neunkirchen (Saar)
    Beiträge
    11.094
    Wir hatten alle vollstes Vertrauen in Dich
    Zitat Zitat von Leonard Bernstein
    This will be our reply to violence:
    to make music more intensely,
    more beautifully,
    more devotedly than ever before.
    Meine Stories:
    Civ VI aus der Sicht von Civ IV BTS, englischer Weltraumsieg auf König
    Der Erste Kaiser wieder aufgenommen

  7. #2032
    Frühstücksbonze Avatar von Gullix
    Registriert seit
    21.07.10
    Beiträge
    11.988
    ...also, hm, man sollte öfter mal seinen Code profilen und vor allem mehr an den Parametern herumspielen.


    Ich habe einen Code, der ein Vielteilchensystem simuliert, mit diversen Wechselwirkungen. Bisher immer so höchstens einige tausend Teilchen. Im Prinzip wechselwirkt jedes mit jedem, wenn man einfach blind die Kräfte ausrechnet sind das halt N² viele Terme, Laufzeit N². Im Code sind die kurzreichweitigen Wechselwirkungen mit Nachbarlisten erledigt (N log N), und die langreichweitigen mit ein paar Tricks über Fouriertransformationen (auch N log N, ich benutze FFTW). Profiler hat ergeben, etwa 70% der Laufzeit geht auf die FFT. Das heißt, wenn ich mich nicht gerade für schlauer halte als die FFTW-Jungs, kann ich da nicht viel herausoptimieren. Und die Performance war auch ganz gut - 2000 Teilchen, jedes wechselwirkt mit jedem in jedem Zeitschritt, und pro Zeitschritt brauche ich drei zweidimensionale FFTs mit 256x256 Samples, da schafft eine CPU zwischen 1000 und 1500 Zeitschritte pro Sekunde.

    Naja. Stellt sich raus, das N log N bei der Fouriertrafo hängt nicht an der Teilchenzahl, sondern an den Samples, und die hängen nur schwach von der Teilchenzahl ab, da ist mit 256 Samples noch Luft. Habe heute mal testweise die Teilchenzahl von 2000 auf 24000 erhöht (also mehr als verzehnfacht) und die Laufzeit nur verdoppelt
    Zitat Zitat von Decimus Iunius Iuvenalis
    Es ist schwierig, keine Satire zu schreiben.
    Im Übrigen bin ich der Meinung, dass Deutschland von einer Minderheitsregierung regiert werden soll.

  8. #2033
    Say My Name Avatar von Zulan
    Registriert seit
    13.03.08
    Ort
    Tal der Ahnungslosen
    Beiträge
    8.810
    FFTW ist nicht ganz trivial effizient zu nutzen. Unbedingt aufpassen dass die Elemente entsprechende vielfache des optimierten Polynom sind (256 ist natuerlich ok) - da hab ich mir auch schon ordentlich in den Fuss geschossen. Dazu dann das ganze Plan Zeugs, spielt bei kleineren Mengen ne rolle. Zu FFTW kann man ausrechnen wieviele FLOPs theoretisch benoetigt sind - dazu messen wielange die FFT selbst braucht, da bekommt man ein gewisses Bild von der tatsaechlichen Effizient.

  9. #2034
    ¡Olé! Avatar von Harleen
    Registriert seit
    07.01.06
    Ort
    Bremen
    Beiträge
    9.219
    Wenn du nur eine FFT brauchst (also keine DFT) und auf Portabilität zu nicht-PC-Architektur pfeifst, lohnt sich auch ein Blick auf Intels ipp. Vielleicht einfach mal als Alternative einbauen und ausprobieren. Eine schnellere Implementierung wirst du wahrscheinlich nicht finden.

  10. #2035
    Frühstücksbonze Avatar von Gullix
    Registriert seit
    21.07.10
    Beiträge
    11.988
    ...also, eine FFT, aber keine DFT (diskrete FT)? Was ist das? Geht doch nicht ohne Diskretisierung oder?

    Ich muss da eine Funktion fouriertransformieren, mit einer Funktion im k-Raum multiplizieren und wieder zurücktransformieren. Genau genommen je Raumrichtung mit einer verschiedenen Funktion im k-Raum multiplizieren, aber das sollte egal sein.


    FFTs wollen ja gut primfaktor-zerlegbare Arraygrößen. Habe heute etwas größeres als 256 gebraucht. Stellt sich raus, 384 (also 128*3) ist schneller als 512.
    Zitat Zitat von Decimus Iunius Iuvenalis
    Es ist schwierig, keine Satire zu schreiben.
    Im Übrigen bin ich der Meinung, dass Deutschland von einer Minderheitsregierung regiert werden soll.

  11. #2036
    ¡Olé! Avatar von Harleen
    Registriert seit
    07.01.06
    Ort
    Bremen
    Beiträge
    9.219
    Zitat Zitat von Gullix Beitrag anzeigen
    ...also, eine FFT, aber keine DFT (diskrete FT)? Was ist das? Geht doch nicht ohne Diskretisierung oder?
    Eine FFT ist eine besonders schnelle Fourier Transformation, die aber nur in bestimmten Längen (üblicherweise Zweier-Potenzlängen) funktioniert. Das Ergebnis ist das gleiche wie bei der DFT, nur eben schneller.

    Zitat Zitat von Gullix Beitrag anzeigen
    Ich muss da eine Funktion fouriertransformieren, mit einer Funktion im k-Raum multiplizieren und wieder zurücktransformieren. Genau genommen je Raumrichtung mit einer verschiedenen Funktion im k-Raum multiplizieren, aber das sollte egal sein.
    Funktionen transformieren? Geh mir weg mit diesem theoretischen Zeug. Ich arbeite nur auf richtigen Messdaten. Ich habe irgendwie das Gefühl, dass meine FFT-Erfahrungen für dich nicht sonfderlich hilfreich sind.

    Zitat Zitat von Gullix Beitrag anzeigen
    FFTs wollen ja gut primfaktor-zerlegbare Arraygrößen. Habe heute etwas größeres als 256 gebraucht. Stellt sich raus, 384 (also 128*3) ist schneller als 512.
    Kommt auf den Algorithmus an. Ich habe FFTs bisher nur mit Zweierpotenzen gesehen. Deiner scheint ein anderer zu sein...

  12. #2037
    Advocatus Diaboli Avatar von Mr. X
    Registriert seit
    01.04.12
    Beiträge
    9.268
    Ingenieurwesen vs. theoretische Physik

Seite 136 von 136 ErsteErste ... 3686126132133134135136

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •