Re: AND-Problem
- From: "????" <georgl@xxxxxxxxxx>
- Date: Thu, 27 Jul 2006 22:51:58 +0200
Hallo Julius,
es gibt in C++ fur Dich etwas fertig:
schau Dir in der Docu: bitset oder std::bitset
das ist ein Ersatz für Deine arrays aus der STL.
Schau Dir die member Funktionen von diesem bitset an.
Und STL hat noch eine Menge Algorithmen die Dir helfen können.
Und perfomanter als in der STL wirst Du es nicht machen können.
Viel Spass beim lesen und ausprobieren.
Gruß
Georg
"Julius Kavay" <kavay@xxxxxxx> schrieb im Newsbeitrag
news:eWNKGParGHA.984@xxxxxxxxxxxxxxxxxxxxxxx
Hallo,
ich suche nach einem schnellen Algorythmus fuer das folgende
Problem. Scheinbar sehe ich den Wald vor lauter Baeume nicht...
Ich habe zwei Arrays, pattern1 und pattern2 sowie zwei Integers
items1 und items2. Die itemsX geben die Anzahl der
aktuell gueltigen Elemente in den Arrays pattern1 und pattern2 an
(die Arrays sind mit fixer Groesse definiert).
Jeder dieser Array mit den Elementen
pattern1[0], pattren1[1],... pattern1[items1-1] und
pattern2[0], pattren2[1],... pattern2[items2-1]
beschreibt ein Bitstream. Die Arrayelemente sagen aus,
wie viele Bits geloescht oder gesetzt sind in den Bitstreams,
von links beginnend, und unter der Annahme, dass das erste
Bit immer geloescht ist, und dann alternierend nach rechts gehend.
Beispiel1:
bits1: 00011111011110000000111
bits2: 0110011000010001
------------------------------
AND : 000001 result=1
short int pattern1[3000] = {3,5,1,4,7,3, 0,0,0,0...};
short int pattern2[3000] = {1,2,2,2,4,1,3,1, 0,0...};
short int items1 = 6;
short int items2 = 8;
(Anzahl der Bits: bitcount1 = 23, bitcount2 = 16)
Beispiel2:
bits1: 1001100011
bits2: 0110011000010001
------------------------
AND : 0000000000 result=0
short int pattern1[3000] = {0,1,2,2,3,2, 0,0,0,0,0...};
short int pattern2[3000] = {1,2,2,2,4,1,3,1, 0,0,0...};
short int items1 = 6;
short int items2 = 8;
Die Frage ist nun, wie kann ich schnell (und ich meine, so richtig
schnell) die zwei Bitstreams mit einander verUNDen, also etwa so:
result = bits1 AND bits2
oder in C geschrieben:
result=0;
for (i=0; i < min(bitcount1, bitcount2); i++) {
if (bits1[i] AND bits2[i]) { result=1; break; }
wobei die bits1 und bits2 die aufgeloeste Bits aus den Arrays
pattern1 und pattern2 beinhalten (siehe oben)?
Die tatsaechliche Daten schauen etwa so aus:
short int pattern1[3000] = {30,15,21,34,70,33,...};
short int pattern2[3000] = {12,26,52,27,281,7,...};
short int items1 = 62;
short int items2 = 47;
die laengste Fall wuerde dann so aussehen:
short int pattern[3000] = {1,1,1,1,1,1,1,1,1,1...}
short int items = 2600
Ein paar Hintergrundinfos.
Erstens, meine C-Kentnisse sind eher unterdurchschnittlich
(benuetze es nur selten). Ich habe jetzt eine *.dll geschrieben
(in C) welches ich in einer meiner Applikationen benuetze.
Es gilt, die Performance des dll's zu verbessern. Das dll enthaelt
eine Suchfunktion, welche mit Hilfe von Vektoren eine Aehnlickeit
zweier Saetze bestimmt. In einer Datenbank habe ich ca. eine halbe
Million Saetze, und von einer Messung einen anderen Satz.
Mein Abgleich dauert derzeit ca. 0.2 Sec, und es sollte durch die oben
beschriebene Methode eine Vorselektion bekommen. Das Ziel ist dann
eine Suchzeit von ca. 0.05 - 0.08 Sec.
Danke,
Julius
--
.
- References:
- AND-Problem
- From: Julius Kavay
- AND-Problem
- Prev by Date: Re: Frage zur MFC
- Next by Date: Re: Memory mapped files and caching?!?
- Previous by thread: Re: AND-Problem
- Next by thread: Daten aus c-projekt nach Excel schreiben
- Index(es):
Relevant Pages
|
