Trójwymiarowa mapa vs iteracja w poszukiwaniu wektora

Question

Cześć, zastanawiam się co jest wydajniejsze? Użycie 3 wymiarowej mapy intów i odwoływanie się bezpośrednio do wybranego elementu, czy przeiterowanie tablicy w poszukiwaniu wskazanej wartości? Taki przykładowy pseudo-kodzik, co mam na myśli

 

TMap<int32, TMap<int32, TMap<int32, UChunkComponent*> > > chunks;
	
	chunk[0][0][0];

	//vs

	TArray<UChunkComponent*> chunks;

	for (int i = 0; i < chunks.Num(); ++i)
	{
		if (chunks[i].findPosition(0, 0, 0))
		{
			break;
		}
	}

 

Comments

Imo ta metoda "findPosition" zawiera błąd logiczny. Nie możesz znaleźć pozycji pozycji. Możesz znaleźć pozycję elementu. Albo element na pozycji. Reasumując. findPosition powinien zawierać szukany element. Nie numery "komórek".

Answer 1

IMO jednym z najszybszych sposobów jest użycie kontenera unordered_map, i napisanie funkcji haszującej dla własnej struktury danych. Zaletą tego jest stały czas wyszukiwania - średnio O(1).

C++20

#include <iostream>
#include <unordered_set>

struct Point
{
    int a {}, b {}, c {};
    auto operator<=>(const Point&) const = default;
};

std::ostream& operator<<( std::ostream& out , const Point& point )
{
    out << '(' << point.a << ',' << point.b << ',' << point.c << ')';
    return out;
}

namespace std
{
    template <>
    struct hash<Point>
    {
        size_t operator()( const Point& point ) const noexcept
        {
             return ( std::hash<int>()(point.a) ^ ( std::hash<int>()(point.b) << 1) ) ^ std::hash<int>()(point.c);
        }
    };
}

int main()
{
   std::unordered_set<Point> points;

   for( int i {0} ; i<1000 ; ++i ) points.insert( { std::rand()%1000 , std::rand()%1000 , std::rand()%1000 } );
   points.insert( {5,6,7} );

   auto iter = points.find( {5,6,7} );
   if( iter != std::end(points) ) std::cout << "Found point " << *iter << std::endl;
}

https://godbolt.org/z/8Yx6G7rbP

Answer 2

Nie no zawsze operacja odwołania się do elementu bez iteracji będzie wydajniejsza, niż przeliterowanie listy... chociaż spierałbym się bo to "zależy" od tego jak długa jest np lista.
Też ważne jest jaki rozmiar ma trójwymiarowa tablica, tzn  czy statycznie jest określany jej rozmiar na starcie i jest np duża. dużo zmiennych, dochodzi też "Warunek" bo wiesz w 1 założeniu na starcie wiesz, że wybrany element ma "takie i takie pozycje" a na liście nie wiadomo gdzie on jest.

 

Z tego jeszcze co analizuje to wydajnie ten załączony fragment jest dramatem, dla każdego elementu listy wywoływana jest funkcja

Answer 3

W sumie mnie to zaciekawilo, wiec zrobilem prosty, durny test. Uzywajac twoich struktur mapy i arraya i zakladajac, ze klucze to:

1,1,1

2,2,2

3,3,3 itd..

to liczac zawsze najgorszy case dla wyszukiwania przez iterowanie (wyszukiwany element jest ostatni) to na tej maszynce godbolta wyszukiwanie przez mape zaczyna byc szybsze od iterowania przy okolo 100 elementach, pozniej jest coraz gorzej dla iterowania.

https://godbolt.org/z/ndYGhvj83

Ilosc elementow mozna zmienic w tym define:

#define ARRAY_SIZE 100

Comments

dobra przy założeniu też faktu, że mamy wywołanie funkcji na - 1 iteracje tablicy w pętli ?

---

@Wiciorny nie rozumiem

---

w każdej iteracji, na każdy element wywołanie jest funkcji chunks[i].findPosition(0, 0, 0)
... w tym wypadku, weżmy jeszcze sytuacje, pętli w pętli gdzie np implementacjca findPossition zawiera rekurencje itd?

---

ah, mowisz o tym if (chunks[i].findPosition(0, 0, 0)) z posta? nie, nie uwzglednialem tego, pytajacy nie podal zawartosci funkcji, wiec zrobilem zamiast tego

struct ChunkKey
{
    int32_t x;
    int32_t y;
    int32_t z;
};

i sprawdzanie poprzez

if (chunksArray[i]->x == x && 
    chunksArray[i]->y == y && 
    chunksArray[i]->z == z)
{
    return chunksArray[i];
}

 

---

Nie zmieniaj standardowych czcionek bo nic nie widać!

---

@manjaro fakt, dzieki, kod skopiowal sie razem z kolorami, wyedytowalem i wstawilem kod w bloczek 'code'. W nim mam nadzieje nie ma znaczenia jak pokolorowany jest tekst w schowku kiedy go wklejam.

---

Teraz jest OK.