Porówanie stringów - problem czasu

Chce sprawdzić czy jeden string jest substringiem innego (ale polozonym na początku porównywanego).
Dałem:
str1.find(str2) == 0
Ale czas w jakim dokonuje się to porównanie jest zbyt duży
Próbowałem też jakby na około, używając
str1.compare(0, str2.size(), str2) == 0
Ale ta operacja jest dwa razy wolniejsza

Zależy mi na czasie porównania bo porównań jest miliony co kumuluje się i daje kiepski rezultat

Co polecacie?
Inna funkcja??
A może całkiem rezygnacja ze stringów??
Moze C-stringi są szybsze?
W sumie chwilowo mam brak pomysłów jak w ty miejscu przyśpieszyć program.

Ja bym Ci polecil tablice znakowe w C oraz funkcje strcmp i jej pokrewne.
W C porownanie bedzie wykonane wydajniej i szybciej, poniewaz w c++ zaimplementowano specjalna klase string do obslugi lancuchow znakow, a wiadomo ze cena prostoty(czyt. obiektowosci) jest w tym przypadku wydajnosc.

Nie wiem co dokładnie miałeś na myśli pisząc, że porównań jest miliony (jednego z wieloma czy wielu stringów z wieloma) ale przydatne mogło by się okazać hashowanie.

Chodziło mi o to, ze
str1.find(str2) == 0
a dokładniej:
str1[i].find(str2) == 0
jest w pętli gdzie i zmnienia się od zera do 1610241024
A to jest tylko jedna zewnętrzna iteracja

Trochę dziwne, że compare działa wolniej. Gdy szukasz podstringu w całym stringu, to czas wykonywania operacji zależy od rozmiaru obu stringów. Od iloczynu ich rozmiarów. Tymczasem sprawdzenie, czy jeden string zaczyna się od drugiego powinno zależeć liniowo od rozmiaru mniejszego z nich. Różnica na korzyść tego drugiego sposobu jest więc spora, choć może się ujawnić dopiero przy dłuższych stringach.

A próbowałeś użyć operatora [] i sprawdzać to ręcznie litera po literze? Możesz ewentualnie użyć tych c-stringów. Myślę, że ten zwracany przez string::c_str() raczej jest zaimplementowany dość sprawnie (po prostu zwróci wskaźnik do miejsca w pamięci, gdzie klasa przechowuje string), choć z tego co widzę to specyfikacja tego nie gwarantuje.

Tak jak wspomniał ktoś wcześniej, możesz spróbować użyć hashy. Przydaje się to, gdy sprawdzasz który z wielu stringów pasuje do podanego. Hasha dla podanego stringu obliczasz raz, przed pętlą. W każdej iteracji obliczasz hash dla jednego stringu i potem porównujesz tylko hashe. Oszczędza to wielu kosztownych instrukcji porównań (zamiast porównywać litery, porównujesz tylko gotowe hashe, przy czym jeden z nich obliczasz poza pętlą). Funkcja haszująca powinna być jak najbardziej nieskomplikowana. Gdy prawdopodobieństwo wystąpienia kolizji hashów nie jest pomijalne, to robi się tak, że gdy hashe się zgadzają, to wtedy (i tylko wtedy) wykonujesz normalne, pełne porównanie obu stringów. Niemal zawsze powinno wyjść, że stringi się zgadzają, więc to porównanie wykona się tylko raz.

Wydaje mi się jednak, że wystarczy skonstruować ręczne sprawdzenie pierwszych n liter, gdzie n jest liczbą liter podstringu.

Niestety ręczne porównanie wyszło jeszcze gorzej. Spróbuję na C-stringach to zrobić, ale to wymaga dość poważnej modyfikacji mojego programu. Być może hashowanie to całkiem niezły pomysł.
Dziś już późno. Będę myślał jutro nad tym.
Dzięki za pomoc,
Jeszcze się odezwe :)

@sq:
Spróbuj może zostawić te (C++) stringi, ale użyć tam gdzie trzeba c_str() i operować w krytycznym miejscu na c-stringach. W miarę możliwości na wszelki wypadek podstaw sobie to do zmiennej char*, żeby nie wykonywać w pętli nie wiadomo ilu wywołań c_str(). Choć zależnie od implementacji nie musi to być czasochłonne (gdy c_str() zwraca już istniejący bufor i niczego nie kopiuje, a funkcja jest inline).

Wiesz nie do końca Cię teraz zrozumiałem. Byc może dlatego że mi sie już przysypia :)
Ogólnie rzecz biorąc mam duuzą tablicę stringów. I po niej iteruje porównując z podanym stringiem.
Tak jak mówisz to za każdym razem musiałbym chyba wywoływać fcje c_str() czyż nie?

Spróbuję więc wyrazić się jaśniej. Algorytm powinien działać tak (pseudokod z elementami C++ :P):

int znajdź_string_rozpoczynający_się_od(lista_stringów, string prefix) {
  char* const cstr_prefix = prefix.c_str(); // (1)
  for (int i = 0, n = lista_stringów.size(); i < n; i++) {
    string str_z_listy = lista_stringów.string_nr(i); // (2)
    char* ptr_z_listy = str_z_listy.c_string();
    for (char* ptr_prefix = cstr_prefix; ... ; ptr_prefix++, ptr_z_listy++ ) {
      // tu sprawdzasz czy *ptr_prefix i *ptr_z_listy do siebie pasują
      // gdy pasują to wychodzisz z funkcji zwracając indeks
    }    
  }
  return -1;
} 

Więc tak, dla każdego stringu z listy musisz wywołać c_str(), ale chodziło mi o to, żebyś to zrobił raz, a nie np. przy każdej iteracji wewnętrznej pętli. Wydajność może też zwiększyć zastosowanie zapisu wskaźnikowego (*ptr_prefix) zamiast tablicowego (ptr_prefix[k]).

Wydajność zwiększysz znacznie gdy posortujesz stringi, a szukać będziesz binarnie (ciągle dzieląc zakres na pół). Ilość porównań nigdy nie przykroczy N dla 2^N stringów. Jedyne wymaganie jest takie, by funkcja porównująca stringi, porównywała je tak samo jak przy sortowaniu i szukaniu.

Poniższy przykład szuka binarnie kompletnego słowa, uwzględniając wielkość liter:

int IntelisenseFindStringInGroup(DBGROUP *group, LPSTR pszKeyword)
{
	int min = 0;
	int max = group->nKeywordCount-1;
	while (min <= max)
	{
		int pos = min + ((max - min) / 2);

		int cmp = strcmp(group->pszKeywords[pos], pszKeyword);

		if (!cmp)
		{
			return pos; // znaleziono
		}
		else if (cmp < 0)
		{
			min = pos+1;
		}
		else
		{
			max = pos-1;
		}
	}
	return -1; // nie znaleziono
}

Witam, jak wyszukiwanie binarne działa to ja wiem :) Ale dzięki za instrukcje
Z tym sortowaniem to różnie może być. Ale w sumie warto spróbować,i zobaczyć jaki będzie rezultat.
Tak w ogóle to nie musze sortować, bo moja tablica stringów jest pusta na początku.
Później się tym zajmę.