CYFROWY BARON • PROGRAMOWANIE • Zobacz wątek - Pomoc przy optymalizacji funkcji

Pomoc przy optymalizacji funkcji

dział ogólny

Pomoc przy optymalizacji funkcji

Nowy postprzez Slynx » wtorek, 19 kwietnia 2011, 21:48

Mam taką jedną funkcję, która jest używana w bardzo dużych ilościach, pracująca na stringach, no i sam nie wiem czy rzeczywiście jest napisana do ****, czy takie operacje są po prostu czasochłonne.
Napisałem to na szybko, bo była mi potrzebna, a potem już nie miałem pomysłu jak ją poprawić, o ile to możliwe, więc pomyślałem, że zapytam.

KOD cpp:     UKRYJ  
 String^ Data::Find_Between(String^ search_data, String^ start_string, String^ end_string)
 {
   int s1 = search_data->IndexOf(start_string);
   int s2 = search_data->IndexOf(end_string, s1);

   int s3 = start_string->Length;

   return search_data->Substring(s1 + s3, (s2 - (s1 + s3)));
 }
Prosta funkcja zwraca fragment stringu pomiędzy dwoma wskazanymi miejscami. Oprócz tego ważnym elementem jest to, że end_string wyszukuje poczynając od pozycji start_string ( żeby się nie okazało, że początek będzie miał większą wartość od końca).
Jako, że z Visuala "nikt" nie korzysta

KOD text:     UKRYJ  
indexOf(string do wyszukania, pozycja startowa);
Substring(pozycja startowa, długość ciągu - length);
Avatar użytkownika
Slynx
Mądrosław
Mądrosław
 
Posty: 350
Dołączył(a): piątek, 17 grudnia 2010, 21:59
Podziękował : 11
Otrzymał podziękowań: 0
System operacyjny: Windows 7 32
Kompilator: Visual C++ 2005; Visual C++ 2008; Visual C++ 2010; Visual C# 2010;
Gadu Gadu: 0
    Windows 7Chrome

Re: Pomoc przy optymalizacji funkcji

Nowy postprzez Cyfrowy Baron » środa, 20 kwietnia 2011, 08:57

Trochę jest to dla mnie niezrozumiałe, gdyż używasz funkcji IndexOf w odniesieniu do zmiennej typu String (AnsiString, lub UnicodeString), a w RAD Studio 2010 (C++Builder 2010), ta funkcja występuje w klasie TStrings (i kilku innych, ale ta jest najbliższa temu co tu piszesz, z nazwy). Niemniej jednak, jak widzę po kodzie zasada użycia jest niemal identyczna, z tą różnicą, że funkcja pobiera tylko jeden argument. Rzecz w tym, że w TStrings ta funkcja wyszukuje wiersz listy, a nie ciąg znaków, więc to raczej nie o to chodzi.
Innymi funkcjami, która działają niemal identycznie są Pos, AnsiPos (tylko AnsiString), LastDelimiter, LastChar. Więc najbliższa Twojej jest funkcja Pos.

Tak czy owak, skoro zdecydowałeś się użyć gotowej funkcji wyszukującej pozycję tekstu w łańcuchu znaków, to niczego już tutaj nie zoptymalizujesz, gdyż funkcja IndexOf została już zoptymalizowana pod kontem jak najlepszej wydajności, a nawet gdybyś chciał, to niczego w tej funkcji nie zmienisz. Gdybyś chciał to zoptymalizować to musiałbyś skorzystać z zupełnie innej metody wyszukiwania, ale czy byłaby szybsza...

Zastanawia mnie jednak sposób użycia funkcji Find_Between. Za każdym wywołaniem funkcja zaczyna od początku, no chyba, że argument String^ search_data za każdym razem otrzymuje inny łańcuch znaków.
Avatar użytkownika
Cyfrowy Baron
Administrator
Administrator
 
Posty: 4716
Dołączył(a): niedziela, 13 lipca 2008, 15:17
Podziękował : 12
Otrzymał podziękowań: 442
System operacyjny: Windows 7 x64 SP1
Kompilator: Embarcadero RAD Studio XE2
C++ Builder XE2 Update 4
SKYPE: cyfbar
Gadu Gadu: 0
    Windows XPFirefox

Re: Pomoc przy optymalizacji funkcji

Nowy postprzez polymorphism » środa, 20 kwietnia 2011, 10:43

Nie uwzględniasz wariantu, gdy search_data nie zawiera ciągu start_string lub end_string:
KOD cpp:     UKRYJ  
String^ Data::Find_Between(String^ search_data, String^ start_string, String^ end_string)
{
        int s1 = search_data->IndexOf(start_string);
        if(s1 == -1)return "";  //<--- nie wiem, czy to dobra forma. Jak nie, to sobie popraw
        s1 += start_string->Length;
       
        int s2 = search_data->IndexOf(end_string, s1);
        if(s2 == -1)return "";  // <--- j/w
        return search_data->Substring(s1, s2 - s1);
}
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2156
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 21.1
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

Re: Pomoc przy optymalizacji funkcji

Nowy postprzez Cyfrowy Baron » środa, 20 kwietnia 2011, 12:23

Ten zapis:

polymorphism napisał(a):
KOD cpp:     UKRYJ  
return search_data->Substring(s1, s2 - s1);


czy raczej ten:

Slynx napisał(a):
KOD cpp:     UKRYJ  
return search_data->Substring(s1 + s3, (s2 - (s1 + s3)));


To zależy od tego, czy funkcja IndexOf zwraca pozycje ostatniego znaku w poszukiwanym ciągu (propozycja polymorphis), czy pierwszego znaku w poszukiwanym ciągu (propozycja Slynx).
Avatar użytkownika
Cyfrowy Baron
Administrator
Administrator
 
Posty: 4716
Dołączył(a): niedziela, 13 lipca 2008, 15:17
Podziękował : 12
Otrzymał podziękowań: 442
System operacyjny: Windows 7 x64 SP1
Kompilator: Embarcadero RAD Studio XE2
C++ Builder XE2 Update 4
SKYPE: cyfbar
Gadu Gadu: 0
    Windows XPFirefox

Re: Pomoc przy optymalizacji funkcji

Nowy postprzez polymorphism » środa, 20 kwietnia 2011, 12:38

IndexOf zwraca pozycję szukanego ciągu, czyli indeks pierwszego znaku (jakby było inaczej, byłoby to bez sensu). I dla takiego działania tej funkcji pisany był mój kod - przyjrzyj się dokładnie, a zobaczysz, że Substring dostaje te same wartości indeksów co u Slynxa (przy założeniu wariantu optymistycznego). Po prostu uprościłem zapis...
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2156
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 21.1
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

Re: Pomoc przy optymalizacji funkcji

Nowy postprzez Slynx » środa, 20 kwietnia 2011, 13:18

Więc tak - Jeśli chodzi o działanie IndexOf to ta funkcja przyjmuje chyba ponad 13 różnych argumentów, więc zastosowanie jest szersze zdecydowanie szersze. Ja wykorzystałem tylko dwa, bo tyle było mi potrzeba.

Zastanawia mnie jednak sposób użycia funkcji Find_Between. Za każdym wywołaniem funkcja zaczyna od początku, no chyba, że argument String^ search_data za każdym razem otrzymuje inny łańcuch znaków.


A jak mogłaby zaczynać inaczej ? Każde użycie funkcji to praca na nowym Stringu i wyszukiwanie.

Nie uwzględniasz wariantu, gdy search_data nie zawiera ciągu start_string lub end_string:

Wiem, ale wszystko było pisane na szybko i mi to nie przeszkadzało, a przynajmniej mam pewność gdzie wyskoczy błąd i nie muszę pamiętać o kontrolowaniu zwracanych wartości. Zwróć też uwagę na interpretację zwracanej wartości, w tym wypadku ciągu znaków, który może przecież zawierać wszystko (wycinam tym przeróżne kombinacje znakowe i wartości, które są nieprzewidywalne). Tak więc
return ""
na pewno odpada, bo pokazywałoby błąd gdy funkcja wykona się poprawnie. Takie rzeczy wolę łapać w bloki try i catch. Jednak mniejsza, bo to nie temat.

Ten zapis:

polymorphism napisał(a):
KOD cpp: � UKRYJ �
return search_data->Substring(s1, s2 - s1);


czy raczej ten:

Slynx napisał(a):
KOD cpp: � UKRYJ �
return search_data->Substring(s1 + s3, (s2 - (s1 + s3)));


To zależy od tego, czy funkcja IndexOf zwraca pozycje ostatniego znaku w poszukiwanym ciągu (propozycja polymorphis), czy pierwszego znaku w poszukiwanym ciągu (propozycja Slynx).


Kwestia bardzo istotna. IndexOf zwraca index pierwszego wystąpienia. Ale to nie miałoby i tak znaczenia. Mój zapis jest konieczny, bo funkcja wyszukuje ciąg końcowy (end_string) poczynając od indexu start_string. Ale o tym już pisałem wcześniej. Dlatego to takie skomplikowane i dlatego taki zapis mi się nie podoba. Wygląda trochę zbyt skomplikowanie jak na zwykłe wyszukiwanie ciągu znaków. Albo po prostu tylko mam takie wrażenie.
IndexOf zwraca pozycję szukanego ciągu, czyli indeks pierwszego znaku (jakby było inaczej, byłoby to bez sensu). I dla takiego działania tej funkcji pisany był mój kod - przyjrzyj się dokładnie, a zobaczysz, że Substring dostaje te same wartości indeksów co u Slynxa (przy założeniu wariantu optymistycznego). Po prostu uprościłem zapis..

Nie do końca. Jeśli end_string będzie częścią start_string to funkcja zwróci niepoprawną wartość lub po prostu wyrzuci błąd.
To co zapisałem uwzględnia dodatkowe przesunięcie wynikające z długości start_string (length), by szukanie zacząłem PO a nie PRZED wystąpieniem start_string.

Zastanawiałem się nad użyciem wyrażeń regularnych, ale nie wiem jak i czy to w ogóle będzie miało jakiś sens co do wydajności.
Avatar użytkownika
Slynx
Mądrosław
Mądrosław
 
Posty: 350
Dołączył(a): piątek, 17 grudnia 2010, 21:59
Podziękował : 11
Otrzymał podziękowań: 0
System operacyjny: Windows 7 32
Kompilator: Visual C++ 2005; Visual C++ 2008; Visual C++ 2010; Visual C# 2010;
Gadu Gadu: 0
    Windows 7Chrome

Re: Pomoc przy optymalizacji funkcji

Nowy postprzez polymorphism » środa, 20 kwietnia 2011, 13:24

Nie do końca. Jeśli end_string będzie częścią start_string to funkcja zwróci niepoprawną wartość lub po prostu wyrzuci błąd.
To co zapisałem uwzględnia dodatkowe przesunięcie wynikające z długości start_length, by szukanie zacząłem PO a nie PRZED wystąpieniem start_string.

Następny. Przyjrzyj się dokładnie ;) Zresztą Twój kod to uwzględnia, ale w złym miejscu.

Tak więc
return ""
na pewno odpada, bo pokazywałoby błąd gdy funkcja wykona się poprawnie. Takie rzeczy wolę łapać w bloki try i catch.

Pusty string oznacza, że funkcja wykonała się poprawnie, tyle tylko, że string nie spełnia kryteriów przeszukiwania, innymi słowy funkcja nic nie znalazła. Wyjątkiem czy też błędem tego bym nie nazwał.
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2156
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 21.1
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

Re: Pomoc przy optymalizacji funkcji

Nowy postprzez Cyfrowy Baron » środa, 20 kwietnia 2011, 13:29

Nie prawda! Twój kod zwraca tekst pomiędzy pierwszym odnalezionym znakiem, a ostatnim, czyli dla zdania:

KOD text:     UKRYJ  
start_string = "uaktualnienia";
end_string = "Windows";
search_data = "Test uaktualnienia systemu Windows XP nie wykrył niezgodności ani problemów."


Twój kod zwróci: s1 = u z wyrazu uaktualnieniam, czyli pozycja 6

polymorphism napisał(a):IndexOf zwraca pozycję szukanego ciągu, czyli indeks pierwszego znaku


s2 - s1 = W z wyrazu Windows, czyli pozycja 28 - 6 (s1) = 22, czyli zwrócony zostanie tekst: "uaktualnienia systemu "

Kod Slynx zwraca: s1 (jak wyżej), czyli 6 + długość wyrazu "uaktualnienia", czyli 13, czyli 6 + 13 = 19, potem:
s2 jak u Ciebie, czyli 28 - 19 (6 + 13) = 9, czyli zwrócony zostanie tekst: "systemu W", też źle, gdyż powinno być:

KOD cpp:     UKRYJ  
return search_data->Substring(s1 + s3, (s2 - (s1 + s3)) - 1);


Gdyż jak sądzę chodzi o zwrócenie ciągu znaków pomiędzy start_string i start_end, a nie jak u Ciebie pomiędzy start_string + start_end i start_end.
Avatar użytkownika
Cyfrowy Baron
Administrator
Administrator
 
Posty: 4716
Dołączył(a): niedziela, 13 lipca 2008, 15:17
Podziękował : 12
Otrzymał podziękowań: 442
System operacyjny: Windows 7 x64 SP1
Kompilator: Embarcadero RAD Studio XE2
C++ Builder XE2 Update 4
SKYPE: cyfbar
Gadu Gadu: 0
    Windows XPFirefox

Re: Pomoc przy optymalizacji funkcji

Nowy postprzez polymorphism » środa, 20 kwietnia 2011, 13:50

:D Panowie, nie kompromitujcie się.

s1 = 5 + 13 = 18
s2 = 27
s2 - s1 = 9

KOD text:     UKRYJ  
Test uaktualnienia systemu Windows XP nie wykrył niezgodności ani problemów.
                  ^        ^
                  |        |
                  s1      s2


Dlaczego s1 ma 18 a nie 5? Ponieważ jest tam linia:

KOD cpp:     UKRYJ  
s1 += start_string->Length;


ale chyba jakaś niewidzialna...

czyli pozycja 6

Baron, cały świat informatyczny indeksuje od zera. Tylko w Delphi ktoś wpadł na durny pomysł indeksowania od 1, i niestety VCL posiada ten mankament.
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2156
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 21.1
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

Re: Pomoc przy optymalizacji funkcji

Nowy postprzez Cyfrowy Baron » środa, 20 kwietnia 2011, 13:55

polymorphism napisał(a)::D Panowie, nie kompromitujcie się.

s1 = 5 + 13 = 18


Człowieku! Nie odwracaj kota ogonem! Przecież wyraźnie pytałem: ostatni, czy pierwszy znak w wyszukiwanym ciągu - napisałeś:

polymorphism napisał(a):IndexOf zwraca pozycję szukanego ciągu, czyli indeks pierwszego znaku


Napisałeś że pierwszy, więc 6, lub 5 jeżeli funkcja pobiera przed znakiem - różnica 1, a teraz twierdzisz, że chodzi o ostatni znak, a nie pierwszy - zdecyduj się, gdyż sam sobie przeczysz.

KOD text:     UKRYJ  
Test uaktualnienia systemu Windows XP nie wykrył niezgodności ani problemów.
     ^           ^
     |           |
   1 znak    ostatni znak
Avatar użytkownika
Cyfrowy Baron
Administrator
Administrator
 
Posty: 4716
Dołączył(a): niedziela, 13 lipca 2008, 15:17
Podziękował : 12
Otrzymał podziękowań: 442
System operacyjny: Windows 7 x64 SP1
Kompilator: Embarcadero RAD Studio XE2
C++ Builder XE2 Update 4
SKYPE: cyfbar
Gadu Gadu: 0
    Windows XPFirefox

Re: Pomoc przy optymalizacji funkcji

Nowy postprzez polymorphism » środa, 20 kwietnia 2011, 14:03

Haha, nigdzie sobie nie przeczę. Pytałeś o metodę IndexOf, więc dostałeś odpowiedź.

Kontrowersyjny fragment mojego kodu dla Twojego przykładu:
KOD cpp:     UKRYJ  
int s1 = search_data->IndexOf(start_string); //<--- s1 będzie 5 (bo indeksy liczymy od zera)
if(s1 == -1)return "";
s1 += start_string->Length; //<--- s1 będzie 18
...

Zgadza się?
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2156
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 21.1
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

Re: Pomoc przy optymalizacji funkcji

Nowy postprzez Slynx » środa, 20 kwietnia 2011, 14:09

Nie prawda! Twój kod zwraca tekst pomiędzy pierwszym odnalezionym znakiem, a ostatnim, czyli dla zdania:

Nie wiem dokładnie czego dotyczy to "nie prawda", ale jak przeanalizowałem, kod tej funkcji to zauważyłem, że jeśli end_string zawiera część start string i jeśli oby występują w search_string, to indexy zwrócone przez funkcję "indexof" się pokryją. Zapomniałem o jeszcze jednym parametrze, czyli szukanie indexu OD pozycji start_index + length. Jednak jak mówiłem, ta funkcja była pisana na szybko więc jej nie testowałem, a póki działała dobrze to jej nie ruszałem. Ale tak, trzeba to dopisać.
Poza tym, bardzo istotne, opcja polymorphisma zwróciła by literkę "u", moja wyrzuciła by błąd, więc w sumie tak jak miało być w założeniach.

ale...
jak to czytam, to Ty w ogóle nie o tym mówisz ; p Ja znalazłem inny błąd, Tobie chodzi o to, że funkcja zwróci index o jeden za duży. Jeśli dobrze zrozumiałem, bo widzę, że na wyjściu pokazujesz przesunięcie znaku o 1 pozycję. Więc się mylisz, bo index to numeracja liczona od 0, a nie od 1, więc to przesunięcie o którym mówisz nie jest potrzebne.

---
Cholera, tak szybko piszczecie, że nie zdążyłęm odpisać :/ To odpowiedź na post C. Barona, zaraz po moim.

---
Tak więc
return ""
na pewno odpada, bo pokazywałoby błąd gdy funkcja wykona się poprawnie. Takie rzeczy wolę łapać w bloki try i catch.

Pusty string oznacza, że funkcja wykonała się poprawnie, tyle tylko, że string nie spełnia kryteriów przeszukiwania, innymi słowy funkcja nic nie znalazła. Wyjątkiem czy też błędem tego bym nie nazwał.


A co jeśli wyszukiwana wartość JEST pusta ? A jeśli string nie spełnia kryteriów to błąd MUSI być, nie może wyrzucić pustego stringa, bo to oznacza, że wprowadzone dane były poprawne. Więc... funkcja działała by niepoprawnie.
Ostatnio edytowano środa, 20 kwietnia 2011, 14:14 przez Slynx, łącznie edytowano 1 raz
Avatar użytkownika
Slynx
Mądrosław
Mądrosław
 
Posty: 350
Dołączył(a): piątek, 17 grudnia 2010, 21:59
Podziękował : 11
Otrzymał podziękowań: 0
System operacyjny: Windows 7 32
Kompilator: Visual C++ 2005; Visual C++ 2008; Visual C++ 2010; Visual C# 2010;
Gadu Gadu: 0
    Windows 7Chrome

Re: Pomoc przy optymalizacji funkcji

Nowy postprzez polymorphism » środa, 20 kwietnia 2011, 14:12

Poza tym, bardzo istotne, opcja polymorphisma zwróciła by literkę "u" (...)

Jakie "u"?! Slynx, sprawdzałeś moją funkcję w ogóle?
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2156
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 21.1
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

Re: Pomoc przy optymalizacji funkcji

Nowy postprzez Slynx » środa, 20 kwietnia 2011, 14:14

Tak, sprawdzałem. Skompilowałem i wyrzuciła mi "u"

--
Oczywiście po zmianie Stringa ! Czyli tak jak wspomniałem wcześniej "Start" na "aktul".
Wy tu się kłóćcie, a ja muszę poprawić błąd z początkiem wyszukiwania dla funkcji IndexOf ; p
Avatar użytkownika
Slynx
Mądrosław
Mądrosław
 
Posty: 350
Dołączył(a): piątek, 17 grudnia 2010, 21:59
Podziękował : 11
Otrzymał podziękowań: 0
System operacyjny: Windows 7 32
Kompilator: Visual C++ 2005; Visual C++ 2008; Visual C++ 2010; Visual C# 2010;
Gadu Gadu: 0
    Windows 7Chrome

Re: Pomoc przy optymalizacji funkcji

Nowy postprzez Slynx » środa, 20 kwietnia 2011, 14:25

Kod: Zaznacz cały

MessageBox::Show(Data::Get()->Find_Between("Test uaktualnienia systemu aktual XP nie wykrył niezgodności ani problemów.", "uaktualnienia", "aktual"));

return search_data->Substring(s1 + s3, (s2 - (s1 + s3)));

Efekt: Błąd

return search_data->Substring(s1, s2 - s1);

Efekt: "u"
Avatar użytkownika
Slynx
Mądrosław
Mądrosław
 
Posty: 350
Dołączył(a): piątek, 17 grudnia 2010, 21:59
Podziękował : 11
Otrzymał podziękowań: 0
System operacyjny: Windows 7 32
Kompilator: Visual C++ 2005; Visual C++ 2008; Visual C++ 2010; Visual C# 2010;
Gadu Gadu: 0
    Windows 7Chrome

Następna strona

Powrót do Ogólne problemy z programowaniem

Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zalogowanych użytkowników i 72 gości

cron