XOR Aufgabe



  • Hi liebe Community,

    ich sitze gerade an einer schweren Aufgabe ich habe ein Array mit Zahlen und soll von stelle 3 bis 20 z.b alle integer xoren also (a xor b) bspielsweise.
    Dies wäre ja ganz einfach wäre da nicht das Problem das es in einer halben Sekunde erechnet werden muss mit einer Array größe bis zu 1 000 000 00 Integern.

    Gibt es einen Algorithmus dafür.

    Wäre für Tipps dankbar am besten nicht den Kompletten source posten sondern nur tipps MFG
    Sorry für die Rechtschreibung bin am Handy ^^


  • Mod

    Kerf schrieb:

    ich sitze gerade an einer schweren Aufgabe ich habe ein Array mit Zahlen und soll von stelle 3 bis 20 z.b alle integer xoren also (a xor b) bspielsweise.
    Dies wäre ja ganz einfach wäre da nicht das Problem das es in einer halben Sekunde erechnet werden muss mit einer Array größe bis zu 1 000 000 00 Integern.

    Ich verstehe die Aufgabe nicht. Was meinst du mit "von stelle 3 bis 20 z.b alle integer xoren"?

    Sind 1,000,000,000 gemeint oder 100,000,000? Einhundertmillionen Zahlen in einer halben Sekunde zu verarbeiten sollte auch mit semi-alten Rechnern kein Problem sein. Eine Milliarde könnte knifflig werden, daher ist es wichtig, die genaue Aufgabenstellung zu kennen.



  • SeppJ schrieb:

    Ich verstehe die Aufgabe nicht. Was meinst du mit "von stelle 3 bis 20 z.b alle integer xoren"?

    Ich verstehe das so
    [code]
    int i;
    int zahlen[42];
    int ergebnis=0;
    for(i=3;i<=20;i++) //oder welche Grenzen auch immer
    ergebnis^=zahlen[i];
    [/quote]

    @TO
    Ich vermute mal diese Zahlen sind nicht 1-2-3 usw sondern mehr oder weniger zufällig?


  • Mod

    xorknorr schrieb:

    SeppJ schrieb:

    Ich verstehe die Aufgabe nicht. Was meinst du mit "von stelle 3 bis 20 z.b alle integer xoren"?

    Ich verstehe das so

    int i;
    int zahlen[42];
    int ergebnis=0;
    for(i=3;i<=20;i++) //oder welche Grenzen auch immer
       ergebnis^=zahlen[i];
    

    Möglich. Aber in dem Fall verstehe ich die Sorge über die Arraygröße nicht.

    @TO
    Ich vermute mal diese Zahlen sind nicht 1-2-3 usw sondern mehr oder weniger zufällig?

    Wenn sie geordnet sind, ist das schon interessanter. Dann macht aber das Array keinen Sinn. Aber die Frage nach großen Zahlen macht dann plötzlich Sinn. Denn dann kann man bestimmt mit etwas Nachdenken das Ergebnis direkt anhand des Anfangs und Endwertes ausrechnen, ohne tatsächlich alle Zahlen verarbeiten zu müssen. Ich warte mit einer genauen Rechnung aber noch, bis der TE sich meldet, habe aber schon eine Idee im Hinterkopf.



  • 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. 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 wenn "alle Zahlen miteinander xoren" heisst, dass

    ergebnis = a[0] xor a[1] xor ... a[n-1] xor a[n]

    dann ist das eigentlich trivial.

    Ansonsten solltest du die Aufgabe möglichst eindeutig beschreiben.



  • @Der echte Tim genau das meine ich ^^


  • Mod

    Wie kommen denn die Daten ins Array? Können die sich ändern? Woher kommt die Anforderung mit der Zeit?



  • Die Daten im Array sind zufällig von 1 - 1000 mit ner random funktion die Zeitvorgabe steht in der Aufgabe 🙂


  • Mod

    Kannst du nicht einfach mal die Aufgabe nennen? Es ist mühsam, dir alles aus der Nase zu ziehen. Im Moment habe ich den Eindruck, dass jede Form von Arbeit, die ein Helfer in diesen Thread investiert, letztlich umsonst sein wird, da gewiss irgendwelche wichtigen Details nicht genannt wurden.

    PS: Einen guten Ansatz, ohne konkrete Ausarbeitung, habe ich: XOR ist sowohl kommutativ, als auch assoziativ. Das eröffnet gute Möglichkeiten für eine Vorberechnung.



  • 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


Log in to reply