tBane Temat założony przez niniejszego użytkownika |
Przechodzenie Listy jednokierunkowej z usuwaniem elementow » 2023-03-02 17:43:29 Czesc !! Mam Pytanie, jak usuwac dynamicznie elementy jednoczesnie przechodzac liste jednokierunkowa w Optymalny sposob ? kod listy jednokierunkowej: class Bullet
{
public:
int x, y;
bool toDelete;
Bullet * next;
}
class BulletManager
{
public:
Bullet * firstBullet;
}
int main()
{
for( Bullet * b = firstBullet; b != NULL; b = b->next )
{
cout << "[ " << b->x << " | " << b->y << " ]\n";
if( b->toDelete )
}
}
|
|
pekfos |
» 2023-03-02 18:01:43 Lista jednokierunkowa ma tu powiedzmy 50% narzutu i wolną iterację, która jest główną operacją na tej strukturze, a usuwanie jest drugorzędne. To tyle w kwestii "optymalnie".. Tablica jest lepsza do tego zastosowania. A co do pytania.. ewidentnie jest problem jak tu usunąć element w Jakikolwiek sposób. Martw się "optymalnością" jak będziesz mieć coś działającego. Jeśli nie napiszesz tego usuwania jakoś tragicznie, to i tak nie usuwanie będzie wymagać optymalizacji. |
|
tBane Temat założony przez niniejszego użytkownika |
» 2023-03-02 18:30:28 Napisalem ! Po swojemu, bo po swojemu ale dziala. Hej pekfos, Twoim zdaniem jest to optymalny algorytm ? void BulletManager::delOldBullets( Camera * cam )
{
Bullet * b = firstBullet;
bool removed = false;
while( b != NULL )
{
removed = false;
if( b->exploded == true || !cam->pointOnScreen( b->x, b->y ) )
{
if( b == firstBullet )
{
firstBullet = firstBullet->next;
b = firstBullet;
}
else
{
b = getPrev( b );
b->next = b->next->next;
}
removed = true;
}
if( removed == false )
b = b->next;
}
}
|
|
pekfos |
» 2023-03-02 18:35:38 Zła struktura danych i usuwanie wygląda na O(n2) więc nie jest optymalnie. Ale przynajmniej jest jakkolwiek. Teraz zmierz czas i sam oceń czy jest sens optymalizować i jaki efekt mają próby optymalizacji. |
|
tBane Temat założony przez niniejszego użytkownika |
» 2023-03-02 18:44:01 Jedyna optymalizacja, ktora wpadla mi do glowy to dodac wskaznik prev i z takowego korzystac wtedy chyba bedzie zlozonosc O( nlogn ). Nie mam teraz dojscia do kompa ehh .. |
|
pekfos |
» 2023-03-02 18:51:11 To powinno mieć O(n), nie wiem skąd chcesz tu wyczarować logarytm. Można tu dodać efektywne wyznaczanie poprzedniego elementu bez robienia z tego listy dwukierunkowej. Ta byłaby jeszcze gorszym wyborem struktury danych.
Cały ten "Optymalny sposob" zmienia całkowicie interpretację pytania. Pytasz jak coś zrobić sensem, podczas gdy już na start kombinujesz bez sensu, to co niby tu można napisać? Masz do przechowania 9 bajtów per rekord, w praktyce 12. Dodanie do tego wskaźnika na x64 robi z tego 24 bajty. Zgaduję że chcesz te węzły alokować dynamicznie (chociaż nigdzie tej pamięci nie zwalniasz), co też ma swoje narzuty zależnie od implementacji, powiedzmy 2 wskaźniki, to masz łącznie 40 bajtów na rekord. 48 jakbyś jednak zrobił listę dwukierunkową, także policz procent zmarnowanej pamięci.
Iterowanie po liście jest znacznie wolniejsze od iterowania po tablicy, bo lista nie ma przewidywalnego wzorca dostępu do pamięci, więc cache procesora nie jest efektywnie wykorzystywany. I to wszystko po to żeby usuwanie było optymalniejsze, bo nie trzeba przesuwać danych w pamięci? Dowolną ilość rekordów w tablicy można usunąć w jednym przebiegu, przesuwając każdy nie więcej niż raz. Użycie tego BulletManagera pewnie wymaga przeiterowania raz po pociskach żeby obliczyć nowe pozycje, drugi raz by sprawdzić i usunąć niepotrzebne obiekty i pomiędzy tymi pewnie N razy przy testowaniu kolizji, więc iterowanie jest operacją nr 1 którą powinieneś optymalizować.
Jak nie ręcznie robiona lista, to ręcznie robiona dynamiczna tablica? Nie, to znaczy kontener STL, konkretnie std::vector<>. Naucz się go, bo będziesz go używać w 99% przypadków (z tych których nie pokrywa std::string). Twoja implementacja kontenera jest zintegrowana z logiką obsługi tych rekordów, co jest bardzo złym pomysłem. Trudniej przetestować sam kontener, trudniej zadbać o jego poprawność, a jak będzie potrzeba przechowywać coś jeszcze innego to wtedy co, skopiujesz ten kod i zrobisz find&replace by zmienić nazwę typu elementu?
No i nie próbuj optymalizować kodu "bo tak". Możesz te usuwanie elementów zrobić w O(n3) jakimś cudem i to wcale nie musi być złe, bo może ten algorytm nigdy nie zobaczy więcej niż 5 elementów, a poświęcisz 10h na pisaniu lepszej wersji, w praktyce tylko dla własnej satysfakcji. Nie ma sensu optymalizować kodu który odpowiada za 0.1% czasu działania programu. Zysk będzie nie większy niż 0.1%. A jeśli na start celujesz w "szybszą wersję" (która wcale nie musi być szybsza, jeśli nie wiesz co robisz), to tylko wydłużasz czas do uzyskania czegoś działającego, a jak nie działa, to nie ma znaczenia czy robi to szybko czy nie. Najpierw niech działa, potem niech działa szybko. Jeśli piszesz dla siebie i chcesz pisać szybki kod dla własnej satysfakcji, to wierz mi - znacznie lepiej zmierzyć wydajność i mieć ten wymierny x12.3 improvement, a nie tylko tak sobie wyobrażać ;)
No i trzeba wiedzieć co w ogóle optymalizować. To może być algorytm o słabej złożoności, który przetwarza wielkie kolekcje danych, ale to może też być prosta operacja jak liczenie sinusa, która po prostu jest wykonywana miliony razy. Bardzo często wąskim gardłem programu jest coś nieoczywistego, więc zapoznaj się z jakimś profilerem, np gprof albo ten wbudowany w Visual Studio. |
|
tBane Temat założony przez niniejszego użytkownika |
» 2023-03-02 23:16:01 ok. Nauczę się tego std::vector i z jego uzyciem zrobię następną grę.
Co to jest profiler i jak to działa? Ja programuje w c++ z poziomu androida, bo nie mam komputera. |
|
pekfos |
» 2023-03-03 16:45:21 |
|
| « 1 » 2 |