XOR Aufgabe



  • ok, ich habe ein Array mit der größe 1 000 000. Das Array ist zufällig mit Zahlen von 0 - 1000 belegt.

    Nun ist die Aufgabe das ich einen Bereich bekomme beispielsweise 3-30001. Für diesen Bereich soll ich alles miteinander XOREN array[3] XOR array[4] XOR array[5] und so weiter. Das wäre ja alles kein Problem wenn nicht das Limit gegeben wäre das die Berechnung innerhalb von 0.5 Sekunden fertig sein muss. Jetzt suche ich nach einem Algortihums um die ganze Berechnung zu beschleunigen.

    Mfg


  • Mod

    Die Rechnung wirst du niemals schneller bekommen, als die naive Methode.

    Und der letzte Versuch, dir wirklich zu helfen, bevor ich es aufgebe:

    Kerf schrieb:

    Darum suche ich nach einem Algo z.b ne init methode die ein array schon verfüllt von 0-(array - stelle) doch das hat nicht funktioniert da ich nicht weiß wie ich es dann verarbeiten soll aber so wäre die Idee gewesen 🙂

    Also ist an der Aufgabe mehr dran, als du sagst. Denn sonst würde es keinen Sinn machen, einen Teil der Rechnung im Voraus zu erledigen. Aber so lange du nicht mit den Details raus rückst, kann man dir nicht helfen. Ich werde auch nicht noch einmal fragen. Beim nächsten Beitrag nennst du entweder alle Fakten oder ich gebe den Thread auf.



  • Kerf schrieb:

    Also ich habe ein Array mit einer größe bis 1 000 000 nun das Problem ich bekomme eine Spanne gegeben z.b 1-500 000 dort soll ich von 1 - 500 000 alle zahlen miteinander xoren ^ also das Problem alles soll in 0.5 Sekunden passieren.

    Ich glaube nicht das das ein durchschnittsrechner schafft.

    Implementier es einfach und miss die Zeit. Teil uns Deine Ergebnisse mit.



  • Kerf schrieb:

    Ich glaube nicht das das ein durchschnittsrechner schafft. Darum suche ich nach einem Algo z.b ne init methode die ein array schon verfüllt von 0-(array - stelle) doch das hat nicht funktioniert da ich nicht weiß wie ich es dann verarbeiten soll aber so wäre die Idee gewesen 🙂

    Also mein durchschnittsrechner braucht ca. 250 microsekunden für 500000 werte.

    Warum misst du also nicht erstmal nach?



  • Mit den größeren SSE-Registern kann man recht schnell xor machen. Die erweiterten Register sind als Stapel angeordnet - d.h. eine Art "Pfannkuch"-xoring wäre schon denkbar und nicht langsam.



  • Wäre auch dann wahrscheinlich bandbreitenlimitiert.



  • Kerf schrieb:

    ok, ich habe ein Array mit der größe 1 000 000. Das Array ist zufällig mit Zahlen von 0 - 1000 belegt.
    Nun ist die Aufgabe das ich einen Bereich bekomme beispielsweise 3-30001. Für diesen Bereich soll ich alles miteinander XOREN array[3] XOR array[4] XOR array[5] und so weiter. Das wäre ja alles kein Problem wenn nicht das Limit gegeben wäre das die Berechnung innerhalb von 0.5 Sekunden fertig sein muss. Jetzt suche ich nach einem Algortihums um die ganze Berechnung zu beschleunigen.
    Mfg

    Geht nicht schneller, als alle durchzugehen. Bißchen Beschleunigung mit SSE2 etc oder Multithreading.
    Und 0.5s ist ne ewig lange Zeit dafür.

    Gehts darum, die Zahlen bei Programmstart einmal in den Speicher zu laden und dann viele Abfragen zu machen, dann merk Dir alle 1000 Zahlen die Zwischensumme, dann kannste den Anfang und das Ende langsam machen und den großen Bereich dazwischen in 1000-er-Schritten hoppeln.



  • Es geht darum das ich es irrgendwie im Vorraus berechne.

    Meine erste überlegung wäre jede stelle array[i] mit dem Wert array[0] XOR ... XOR array[i-1] XOR array[i] zu initialisieren.
    Nun dachte ich das ich beispielsweise auf das Ergebnis der Spanne array[5] bis array[20] durch eine einfach Subtraktion kommen array[20] - array[5].
    Das hat aber nicht funktioniert nun suche ich eine Methode etwas mit dem Initialisieren Array anzufangen und dadurch die Berechnung zu beschleunigen.
    Ich habe überlegt das ganze auf die Multiplikation zu übertragen da XOR sowohl das vertauschungsgesetzt als auch das Verbindungsgesetz a*b = b*a und (a*b)*c = (a*c)*b

    Ich hoffe nun kennt sich jeder auf und irrgendwer kann mir tipps geben 🙂


  • Mod

    Kerf schrieb:

    Ich habe überlegt das ganze auf die Multiplikation zu übertragen da XOR sowohl das vertauschungsgesetzt als auch das Verbindungsgesetz a*b = b*a und (a*b)*c = (a*c)*b

    Das habe ich ja schon oben vorgeschlagen. Es böte sich beispielsweise an, jeweils zwei aufeinander folgende Werte im Voraus zu vorXORen, dann jeweils zwei aufeinander folgende Zwischenergebnisse zu verXORen, dann jeweils zwei aufeinander folgende Zwischenzwischenergebnisse und so weiter. Ein Baum, der das ganze Array aufspannt und an jedem Knoten ein Zwischenergebnis. Dann ist das Berechnen des Gesamtergebnisses einer Spanne nur noch eine Frage des verXORens der Zwischenergebnisse, die diese Spanne, äh, aufspannen.

    Zwei ist vermutlich nicht unbedingt die ideale Kinderzahl für einen Knoten. Aber dies zu optimieren (und überhaupt eine Theorie zu entwickeln, wie man dies optimieren kann), überlasse ich dir.

    Meine erste überlegung wäre jede stelle array[i] mit dem Wert array[0] XOR ... XOR array[i-1] XOR array[i] zu initialisieren.
    Nun dachte ich das ich beispielsweise auf das Ergebnis der Spanne array[5] bis array[20] durch eine einfach Subtraktion kommen array[20] - array[5].

    Rätst du nur oder rechnest du? Das passt doch überhaupt nicht.



  • Klingt nach einer guten Idee aber da hätten wir dann das Speicherlimit von 128 Mib. Und ich glaube der ganze Baum verbraucht mehr speicher bei Zahlen bis zu einer milliarde und nem array mit der length bis 500 000


  • Mod

    Kerf schrieb:

    Klingt nach einer guten Idee aber da hätten wir dann das Speicherlimit von 128 Mib. Und ich glaube der ganze Baum verbraucht mehr speicher bei Zahlen bis zu einer milliarde und nem array mit der length bis 500 000

    SeppJ schrieb:

    Zwei ist vermutlich nicht unbedingt die ideale Kinderzahl für einen Knoten.

    Außerdem ist dies DAS Paradebeispiel, wieso ich dir nicht helfen wollte, bevor du nicht mit allen Details raus rückst und es nun bereue, es doch getan zu haben 😡 . Die 128 MB hättest du schon viel früher erwähnen können, beispielsweise im ersten Beitrag.

    In diesem Sinne: Tschüss!


Anmelden zum Antworten