Diese Seite ist unverschlüsselt! Um sicherzustellen, das Ihr Passwort nicht ausgelesen werden kann, sollten Sie auf die verschlüsselte Seite wechseln!

    Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (ANSI-Standard) » XOR mit strings?
Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 < [ 2 ]
000
28.07.2005, 15:19 Uhr
tabin



 hi

ich möchte zwei strings vergleichen und wissen ob sie gleich sind

strcmp kommt allerdings nicht in frage (zu grosse laufzeit)
also auch positionsweises vergleichen mit einer for-schleife nicht

meine idee ist das ganze mit XOR zu probieren - das hat ja bekanntlich O(1)

das problem ist allerdings dass bei

Code:
(*temp1 ^ *temp2)

nur ein zeichen verglichen wird - was ja auch logisch ist - will ich also alle zeichen in meinen
(gleichlangen) char* vergleichen bin ich wieder bei O(n) (for-schleife)

also würde ich jetzt gerne die beiden speicher bereiche in denen die beiden strings stehen
mit XOR vergleichen - die adressen habe ich ja schon - und die längen stehen mir auch zur
verfügung

jetzt frage ich mich wie cih das ganze anstellen kann - gibt es eine funktion die das macht ?
oder komme ich um bitverschiebung oder for-schleifen nicht herum?

es würde ja schon reichen wenn es eine funktion gäbe die mir ab einer adresse k bits zurückgibt

danke schonmal!

--tabin--


[edit] schriebfeheler gäendaht
Dieser Post wurde am 28.07.2005 um 15:21 Uhr von tabin editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
28.07.2005, 15:56 Uhr
ao

(Operator)


Ganze Strings mit XOR geht nicht.
Es kann sein, dass memcmp etwas schneller ist als strcmp. Aber O(n) ist es trotzdem. Ich behaupte auch mal, dass es unter O(n) nicht geht; das würde nämlich eine CPU erfordern, die n Bits auf einmal vergleichen kann (n beliebig)

ao
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
28.07.2005, 16:15 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)


@ao
müsste es nicht möglich sein in einen anderen grösseren integralen datentypen (array) zu casten und dieses array dann zu xoren... das müsste doch dann prinzipiell schneller sein...
--
...fleißig wie zwei Weißbrote
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
28.07.2005, 16:33 Uhr
virtual
Sexiest Bit alive
(Operator)


@Windalf
Das ist aber noch immer O(n), denn O(1/2*n) = O(2*n) = O(n).
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
28.07.2005, 16:36 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)


Darf ich meine Frage wieder löschen?
Das mit den Aufwand hab ich irgendwie überlesen sondern nur nachgedacht wie man es schneller machen kann...
--
...fleißig wie zwei Weißbrote
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
28.07.2005, 16:44 Uhr
ao

(Operator)



Zitat von Windalf:
@ao
müsste es nicht möglich sein in einen anderen grösseren integralen datentypen (array) zu casten

Das kommt immer aufs konkrete Zielsystem an.

Aber wenn es was bringt, dann macht memcmp es höchstwahrscheinlich so. Auch wenn XOR besser ist als direkter Vergleich. Die C-Lib-Funktionen sind für gewöhnlich hoch optimiert; wenn mans besser machen will als die, muss man schon sehr früh aufstehen.

ao
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
28.07.2005, 17:34 Uhr
tabin



 jo ok - evt hab ich mich etwas falsch ausgedrückt was den aufwand angeht - prinzipiell ist für mich schon interessant wie man es schneller macht - bzw wie es am schnellsten geht

memcmp hm - naja - wie ist es denn mit dem typecast von dem windalf gesprochen hat?
das hört sich doch interessant an :-)

wie gesagt die adressen und längen sind vorhanden - die frage ist nur ob der cast und der vergleich zusammen schneller sind als memcmp


irgendwie will mir das nicht einleuchten dass es nichts schnelleres gibt - ich habe doch eigentlich nur zwei binäre ketten (gleicher länge) die ich vergleichen muss - welches format das nun ist dürfte dabei doch keine rolle spielen - oder?

--tabin--
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
28.07.2005, 17:42 Uhr
~Bahamamama
Gast


Du kannst z.B. Checksummen für die Strings berechnen (md5 = 128 Bit) und die Checksumme dann (auf Pentium Rechnern mit einer Instruktion vergleichen: PCMPEQB.

Ob es sich allerdings lohnt bei jeder Stringmanipulation die Checksumme neu zu berechnen (oBdA O(n)) ist fraglich. Wenn du allerdings oft Strings vergleichst und nur selten änderst kann sich dass schon lohnen.

Bahamamama
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
28.07.2005, 17:44 Uhr
tabin



 den md5vergleich mache ich vorher schon - bei den vergleichen geht darum das gemeinsame präfix zu finden - bisher mache ich eine abgewandelte binäre suche - dh also die srtings ändern sich sehr oft...
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
28.07.2005, 18:55 Uhr
ao

(Operator)



Zitat von tabin:
bei den vergleichen geht darum das gemeinsame präfix zu finden

Moment mal. Zwei Strings vergleichen, mit dem Ergebnis "ja, sie sind gleich" oder "nein, sie sind nicht gleich" ist aber was anderes als Suchen nach dem gemeinsamen Präfix. Hier weißt du doch gerade nicht im Voraus, wie lang der gemeinsame Bereich ist.

ao
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 < [ 2 ]     [ C / C++ (ANSI-Standard) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: