Jak nejrychleji porovnat 2 pole byte – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Jak nejrychleji porovnat 2 pole byte – C / C++ – Fórum – Programujte.comJak nejrychleji porovnat 2 pole byte – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
ingiraxo+15
Grafoman
15. 10. 2012   #1
-
0
-

čau, chci se jen zeptat, jestli je vůbec nějaká rychlejší metoda jak porovnat 2 pole byte bez použití cyklu

Momentálně používám memcmp, ale je to opravdu ten nejrychlejší způsob?
Předtim ještě musim ten blok bytů překopírovat do tempu (memcpy), což taky vezme nějakou rychlost

pokud chci porovnat pole, kde bude max 8 bytů, to jen explicitně přetypuju na short/int/long a jen porovnám čísla, takže tady rychlejší způsob už neexistuje, ale pokud pole bude větší jak 8byte, tak nějak nevim jak na to, aby to bylo opravdu rychlý

Nahlásit jako SPAM
IP: 213.168.183.–
Moje aplikace: http://ophite.cz
Tutoriály na: C#
Reklama
Reklama
ondra.holub+1
Stálý člen
15. 10. 2012   #2
-
0
-

> Momentálně používám memcmp, ale je to opravdu ten nejrychlejší způsob?
Předtim ještě musim ten blok bytů překopírovat do tempu (memcpy), což taky vezme nějakou rychlost

  1. Proč to musíš někam překopírovat? memcmp snad není destruktivní
  2. Záleží na tom, kde nesmí být ten cyklus. memcmp vysoce pravděpodobně obsahuje také cyklus
  3. Cyklus lze nahradit např. rekurzí, ale je samozřejmě nesmysl to tak dělat, protože cyklus má obvykle větší "kapacitu" naž zásobník.
  4. Můžeš ten cyklus rozbalit na sérii ifů. To dá obvykle dost práce, ale pokud ta pole budou krátká, tak to lze udělat s využitím šikovných maker. Nebo si ten zdroják můžeš rovnou vygenerovat.
  5. Zajímavý přístup může být s využitím šablon (ale opravdu jenom zajímavý, rozumně užitečné to asi nebude):
    #include <iostream>
    
    template<
        unsigned long L
    >
    bool array_equal(
        unsigned char* a1,
        unsigned char* a2
    )
    {
        return *a1 == *a2 && array_equal<L - 1>(++a1, ++a2);
    }
    
    template<>
    bool array_equal<0UL>(
        unsigned char* a1,
        unsigned char* a2
    )
    {
        return true;
    }
    
    int main()
    {
        unsigned char a1[] = { 1, 2, 3, 4 };
        unsigned char a2[] = { 1, 2, 3, 4 };
    
        std::cout
            << "a1 == a2 = "
            << std::boolalpha
            << array_equal<sizeof(a1)>(a1, a2)
            << '\n';
    }
    

Nahlásit jako SPAM
IP: 194.138.12.–
ingiraxo+15
Grafoman
15. 10. 2012   #3
-
0
-

s tím skopírováním jsem to neřekl přesně.. já porovnávám množinu bytů s jinou, která se nachází třeba uprostřed jinýho pole

pro lepsi pochopeni ukazka, jak to zhruba mam zatim reseny (pokud pocet hledanych bytu bude vic, nez 8)

// co hledam
byte find[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // velikost 9 byte

// buffer kde hledam
byte buffer[] = { 1, 9, 8, 1, 2, 3, 4, 5, 6 ,7 ,8 ,9, 4 ,2 ,3 };

// pro tech 9 bytu ktere hledam (zde bude kopie te pozice z bufferu)
// alokuje se mimo smycku...
byte* temp = new byte[9];

// prekopiruje tu cast bufferu do tempu (3 je offset)
memcpy(temp, buffer + 3, 9);

// porovnam vyjmute byty s tim co hledam
if (!memcmp(temp, find, 9)) { /* ... */ }

a prave resim, jestli tohle je opravdu ta nejrychlejsi moznost to porovnat


Nahlásit jako SPAM
IP: 213.168.183.–
Moje aplikace: http://ophite.cz
Tutoriály na: C#
vitamin+8
Grafoman
15. 10. 2012   #4
-
0
-

#1 ingiraxo
Majú tie polia známu velkosť pri preklade?

Nahlásit jako SPAM
IP: 195.28.77.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Ovrscout
~ Anonymní uživatel
72 příspěvků
15. 10. 2012   #5
-
0
-

#1 ingiraxo
Můj předpoklad je že memcmp je rozumně udělaný a optimalizovaný ačkoliv režie volání a optimalizace pro opravdu malá pole může být velká.

Teď několik tipů co mne tak z hlavy napadly:

-Použití maker pro jednotlivé velikosti porovnávaných polí, pokud jsou převážně jedné nebo několika málo stejných velikostí.

-Použití "šílených" maker, pokud to překladač zvládne optimalizovat tak si pro jednotlivé velikosti nadefinuješ přetypování/porovnání a pro moc velká pole použiješ memcmp. Bude ale třeba se kouknout do asm nebo změřit rychlost, to ostatně platí pro všechny optimalizace
něco jako  #define  mojecmp(data1,data2,velikost)  ((velikost==1)? ...:memcmp(data1,data2,velikost))

-pokud jsou data zarovnána např po 8byte tak si napsat cyklus nad polem uint_64 a skusit překladač přemluvit aby cyklus "rozvinul" tj přepsal na na kroky, skus kouknout co tvůj překladač umí.

-i když jsi nechtěl použít cyklus, existují specializované instrukce, pro x86 je to tuším REP+CMP.. kterými zapíšeš cyklus ve dvou instrukcích(+inicializace registrů). Toto by ale mněla dělat funkce memcmp i když s trochou režie na volání a ošetření okrajových podmínek(například lichý počet byte atp)

Nahlásit jako SPAM
IP: 78.80.163.–
ingiraxo+15
Grafoman
15. 10. 2012   #6
-
0
-

#4 vitamin
do funkce, ve který to hledam je jako parametr pole byte + jeho velikost fce(byte* data, const int size)

a buffer ma pevnou velikost, ale zapis do nej je dynamickej (nekdy 200 bytu, nekdy 5000 atd..) pocet zapsanych bytu si taky zjistuju - podle jejich poctu probiha pocet cyklů

Nahlásit jako SPAM
IP: 213.168.183.–
Moje aplikace: http://ophite.cz
Tutoriály na: C#
vitamin+8
Grafoman
15. 10. 2012   #7
-
0
-

Mozes skusit daco taketo:


template <size_t ArraySize>
inline bool array_cmp(char* array1, char* array2){
	return ((*array1) == (*array2)) & array_cmp<ArraySize-1>(array1+1, array2+1);	
}
template <>
inline bool array_cmp<0>(char* array1, char* array2){
	return true;	
}

Pripadne miesto char dat napr long, bohuzial to testuje cely buffer, takze si budes musiet nulovat nepouzite prvky.

A tazko povedat ci to bude rychlejsie :)

edit: Tak som si pozrel ten tvoj priklad a toto ti asi nepomoze :)

Preco nepouzies 

memcmp(buffer + 3, find, 9)

?

Nahlásit jako SPAM
IP: 195.28.77.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
ingiraxo+15
Grafoman
15. 10. 2012   #8
-
0
-

#7 vitamin
aha, já jsem trochu žil v představě, že memcmp potřebuje na porovnání pole o stejný velikosti... no na rychlosti to moc nepřidalo, když jsem dal pryč ten zbytečnej memcpy, ale nejspíš lepší možnost neni no

já právě když porovnávám něco do 8bytu, tak např. pokud jsou hledany 4 byty, tak to mam nasledovně 

if ((int&)*(buffer + offset) == (int)1234)
{
    // ...
}

což je podstatě instantní bez problevy, takže jsem se snažil najit nějakou možnost pro víc než 8byte :)

Nahlásit jako SPAM
IP: 213.168.183.–
Moje aplikace: http://ophite.cz
Tutoriály na: C#
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 51 hostů

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý