std::istream - zagwozdka odnośnie szybkości.

std::istream - zagwozdka odnośnie szybkości.
Ola Nordmann
  • Rejestracja:ponad 11 lat
  • Ostatnio:ponad 8 lat
  • Postów:414
0

Hajo.
Pisząc program muszę przeszukiwać strumień w poszukiwaniu słów kluczowych (konkretniej odbieram stronę HTML przez POCO i szukam formularzy. Niestety XML::DOMParser wykłada się na skryptach JS).
Do rzeczy (sam nie lubię długich wątków czytać). Jak będzie wydajniej przeszukać strumień z pamięci(z pamięci ?)? Czytając go bajt po bajcie, czy może wczytać porcję danych i później ją przeszukać. Teoretycznie i tak wczytuję z pamięci i o wiele lepiej będzie wczytywać byte by byte, i od razu wyszukiwać niż 2 razy przeskakiwać przez to samo, ale nie pamiętam jak wyglądała operacja wypluwania ze strumienia i nie chcę się zdziwić. Wiem, że to znikoma różnica wydajności (ile może ważyć kod strony? 50kB?), ale lubię pisać wydajniej kiedy tylko mogę. ;)
Dzięki za odpowiedzi i to nie jest tak, że szukać się nie chce - zostałem po prostu natchniony avatarem @Rev'a. Poza tym zdania na ten temat mogą być podzielone, dopóki ktoś nie rzuci kodem z STL'a :)

@Edit:
Niestety w dokumentacji POCO nie napisano jak ten strumień wygląda w środku - równie dobrze może on pobierać dane bezpośrednio z socket'a co byłoby bardziej naturalne. Nie mam pojęcia gdzie (przykładowo) winsock przechowuje dane dla recv() i jak wygląda czas dostępu do nich.


<img src="http://scontent-a-vie.xx.fbcdn.net/hphotos-ash3/1379478_311850692288742_1730250652_n.jpg" />
Geniusz zua :>
edytowany 5x, ostatnio: Ola Nordmann
madmike
Popraw błędy bo poślę do kosza jako niewychowawczy - ludzie niestety czytając zapamiętuja pisownię. Tym bardziej, że te błędy są robione celowo :/
Ola Nordmann
Ale tam było serduszko :( Poza tym jestem skrajnie zmęczony.
lukasz1235
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad 8 lat
  • Postów:1105
0

Może pokaż kod który chcesz zoptymalizować.

Ola Nordmann
  • Rejestracja:ponad 11 lat
  • Ostatnio:ponad 8 lat
  • Postów:414
0

To nie tak, że chcę go zoptymalizować. Napisałem funkcję na szybko i przepiszę jak będę wiedział, co jest lepsze.

Kopiuj
std::istream& operator>>( std::istream& is, ISKeyword& Keyword )
{
	std::string Line;
	size_t		Pos;
	while ( std::getline( is, Line ) )
	{
		Pos = Line.find( (std::string&)Keyword );
		if ( Pos != -1 )
		{
			Keyword = Line.substr( Pos, (Line.length() - Pos) );
			return is;
		}
	}
}
Kopiuj
std::istream& operator>>( std::istream& is, ISKeyword& Keyword )
{
	std::string Line;
	size_t		Pos;
	char		c = 0;
	int			Found = 0;
	while ( !is.eof() )
	{
		is>>c;

		if( c == Keyword[Found] )
		{
			++Found;
		}
		else
		{
			Found = 0;
		}

		if ( Found == Keyword.length() )
		{
			return is;
		}
	}
}

Pisane na szybko z palca. Które szybsze? :>


<img src="http://scontent-a-vie.xx.fbcdn.net/hphotos-ash3/1379478_311850692288742_1730250652_n.jpg" />
Geniusz zua :>
Ola Nordmann
ISKeyword to klasa - nakładka na stringa, żeby zrobić kilka testów - w kodzie mam manupulator.
lukasz1235
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad 8 lat
  • Postów:1105
0
  1. Kody nie są równoważne (pierwszy modyfikuje Keyword, a drugi nie)
  2. Na oko pierwszy jest szybszy
  3. Nie możesz po prostu sprawdzić?
Ola Nordmann
  • Rejestracja:ponad 11 lat
  • Ostatnio:ponad 8 lat
  • Postów:414
0
  1. Przy rozwiązaniu z getline muszę jakoś oddać to co zabrałem ze strumienia, a znajduje się za szukanym elementem.
  2. Na oko? Znaczy, że jest krótszy? Z pamięci na raz nie pobiorę więcej niż największy rejestr procesora. Czyli w pierwszym wypadku (z tego co mi się wydaje) 2 razy iteruję tablice.
  3. Mogę, ale wtedy nie będę wiedział dlaczego tak jest :)

<img src="http://scontent-a-vie.xx.fbcdn.net/hphotos-ash3/1379478_311850692288742_1730250652_n.jpg" />
Geniusz zua :>
edytowany 1x, ostatnio: Ola Nordmann
lukasz1235
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad 8 lat
  • Postów:1105
0

No to profiler w łapki i wszystko stanie się jasne ;)

Ola Nordmann
Chciałbym, ale nie wiem, czy mam czas na takie rzeczy ;)
RE
Nasz czas jest równie cenny, więc jeżeli możesz coś sprawdzić sam to zrób to i podziel się z nami.
Ola Nordmann
Zaraz sprawdzę czemu poniższe rozwiązanie okazało się najszybsze ;)
Ola Nordmann
  • Rejestracja:ponad 11 lat
  • Ostatnio:ponad 8 lat
  • Postów:414
0

Co ciekawe oba rozwiązania okazały się równie niewydajne. Po kilku eksperymentach doszedłem do formy, która zdaje się być wielokrotnie szybsza od starych, wolnych poprzedniczek:

Keyword to std::string - parametr manipulatora.

Kopiuj
std::istream& ISSearch::operator()(std::istream& is) const
{
	assert( Keyword.length() > 0 && Keyword[0] );

	char	Buffer[4096];
	int		Found = 0;
	char	Curr = 0;

	while ( is.get(Buffer, 4096, Keyword[0]) )
	{
		while( true )
		{
			is.get( Curr );

			if ( Curr == Keyword[Found] )
			{
				++Found;
			}
			else if ( !std::isspace( Curr ) )
			{
				Found = 0;
				break;
			}

			if ( Found == Keyword.length() )
			{
				return is;
			}
		}
	}

	return is;
}

@Edit:
Kod nie zadziałał jeśli szukany znak jest na początku strumienia. Jutro naprawię :)


<img src="http://scontent-a-vie.xx.fbcdn.net/hphotos-ash3/1379478_311850692288742_1730250652_n.jpg" />
Geniusz zua :>
edytowany 2x, ostatnio: Ola Nordmann
_13th_Dragon
  • Rejestracja:ponad 19 lat
  • Ostatnio:dzień
0
Kopiuj
std::istream &operator>>(std::istream &is,const ISKeyword &Keyword)
  {
   char c=0;
   int Found=0;
   while(is>>c)
     {
      if(c!=Keyword[Found]) Found=0;
      else if(++Found>=Keyword.length()) break;
     }
   return is;
  }

I nawet oko @lukasz1235 zauważy że to jest szybsze.
Można też tak:

Kopiuj
std::istream &operator>>(std::istream &is,const ISKeyword &Keyword)
  {
   char c;
   //for(int Found=0;(Found<Keyword.length())&&(is>>c);Found+=(c==Keyword[Found])) {}
   for(int Found=0;(Found<Keyword.length())&&(is>>c);Found=(c==Keyword[Found])?Found+1:0) {}
   return is;
  }

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 2x, ostatnio: _13th_Dragon
Zobacz pozostały 1 komentarz
_13th_Dragon
Powiedz jakiego rodzaju słów szukasz, bo jeżeli to coś w rodzaju: - "kakakakakakakao" to na to jest lepszy algorytm.
Ola Nordmann
Różnie. Napisałem na początku - chcę parsować DOM z POCO. Muszę znaleźć początek formularza, koniec, (czyli "<form" albo "< form") i "</form>" z pomijaniem białych znaków. Do tego jeszcze pola formularzy, atrybuty etc, etc. Będę też go musiał rozszerzyć o wiecej niż jedno słowo kluczowe, bo atrybuty mogą być w losowej kolejności. Nie mam czasu i ochoty parsować całego html, ale niektóre dane muszę wydobyć. Parser od POCO wykłada się na XML. Poza tym niepotrzebnie by parsował cały dokument. Parsować, a później szukać - bez sensu.
Ola Nordmann
Z innej beczki. Nie wiem czemu na tych algorytmach Profiler nie chce mi pokazywać wywołania funkcji. Dobrze, że ma opcje 'Time lines', to przynajmniej 'coś' widać :) (skompilowałem na debug, żeby właśnie wywołania zachować na tym poziomie to i tak nie ma raczej znaczenia.)
Ola Nordmann
W drugim kodzie nie zerujesz found w przypadku złego znaku :)
_13th_Dragon
Racja, jakoś mi to "wymkło".

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.