Wydajny sposób na ponowne zamówienie kolekcji opartej na mapach C++

Question

Mam dużą kolekcję (ish -> 100K) odwzorowującą identyfikator użytkownika (int) na liczbę różnych produktów, które kupił (również int. Muszę ponownie zorganizować dane tak wydajnie, jak to tylko możliwe, aby dowiedzieć się, ilu użytkowników ma różną liczbę produktów. Na przykład, ilu użytkowników ma 1 produkt, ilu użytkowników ma dwa produkty itp.

Zrobiłem to poprzez odwrócenie oryginalnych danych z std::map na std::multimap (gdzie klucz i wartość są po prostu odwrócone). można wtedy wybrać się liczbę użytkowników mających N produktów wykorzystujących count(N) (chociaż ja też jednoznacznie zapisane wartości w zestawie, więc mogłem być pewny dokładnej liczby wartości byłem iteracji nad i ich kolejność)

Code wygląda tak:

// uc is a std::map<int, int> containing the original 
// mapping of user identifier to the count of different 
// products that they've bought. 
std::set<int> uniqueCounts; 
std::multimap<int, int> cu; // This maps count to user. 

for (map<int, int>::const_iterator it = uc.begin(); 
     it != uc.end(); ++it) 
{ 
    cu.insert(std::pair<int, int>(it->second, it->first)); 
    uniqueCounts.insert(it->second); 
} 

// Now write this out 
for (std::set<int>::const_iterator it = uniqueCounts.begin(); 
     it != uniqueCounts.end(); ++it) 
{ 
    std::cout << "==> There are " 
      << cu.count(*it) << " users that have bought " 
      << *it << " products(s)" << std::endl; 
} 

Po prostu nie mogę oprzeć się wrażeniu, że nie jest to najskuteczniejszy sposób na zrobienie tego. Ktoś wie o sprytnej metodzie robienia tego?

jestem ograniczony w tym Nie mogę korzystać podwyższenie lub C++ 11 to zrobić.

O, na wypadek gdyby ktoś się zastanawiał, to nie jest praca domowa ani pytanie do wywiadu.

Answer 1

Zakładając, że znasz maksymalną liczbę produktów, które mógł kupić jeden użytkownik, możesz zobaczyć lepszą wydajność za pomocą wektora, aby zapisać wyniki operacji. Będziesz potrzebował alokacji praktycznie dla każdego wpisu na oryginalnej mapie, co prawdopodobnie nie jest najszybszą opcją.

Spowoduje to również zmniejszenie obciążenia wyszukiwania na mapie, uzyskanie korzyści z lokalizacji pamięci i zastąpienie wywołania liczenia na multimapie (która nie jest operacją czasu stałego) ze stałym wyszukiwaniem czasu w wektorze .

Więc można zrobić coś takiego:

std::vector<int> uniqueCounts(MAX_PRODUCTS_PER_USER); 

for (map<int, int>::const_iterator it = uc.begin(); 
     it != uc.end(); ++it) 
{ 
    uniqueCounts[ uc.second ]++; 
} 

// Now write this out 
for (int i = 0, std::vector<int>::const_iterator it = uniqueCounts.begin(); 
     it != uniqueCounts.end(); ++it, ++i) 
{ 
    std::cout << "==> There are " 
      << *it << " users that have bought " 
      << i << " products(s)" << std::endl; 
} 

Nawet jeśli nie wiem maksymalną liczbę produktów, wydaje się, że można po prostu odgadnąć maksimum i dostosować ten kod, aby zwiększyć rozmiar wektor, jeśli jest wymagany. Z pewnością przyniesie to mniej przydziałów niż twój oryginalny przykład.

Wszystko to zakłada, że ​​w rzeczywistości nie wymaga się identyfikatorów użytkowników po przetworzeniu tych danych (i jak wskazano w poniższych komentarzach, że liczba produktów zakupionych dla każdego użytkownika jest stosunkowo niewielka & sąsiedni zestaw, w przeciwnym razie lepiej będzie użyć mapy zamiast wektora - nadal będziesz unikać wywoływania funkcji multimap :: count, ale potencjalnie stracisz część innych korzyści)

Answer 2

Jeśli możesz, zaleciłbym przechowywanie obu aktualnych danych przez cały czas. Innymi słowy, zachowałbym drugą mapę, która mapuje liczbę produktów zakupionych do liczby klientów, którzy kupili tak wiele produktów. Ta mapa zawiera dokładną odpowiedź na twoje pytanie, jeśli ją zachowujesz. Za każdym razem, gdy klient kupuje produkt, należy podać liczbę produktów, które klient kupił. Odejmij jeden od wartości kluczem n-1. Dodaj jeden do wartości kluczem n. Jeśli zakres kluczy jest wystarczająco mały, może to być tablica zamiast mapy. Czy spodziewasz się, że pojedynczy klient kupi setki produktów?

Answer 3

To zależy od tego, oznacza "bardziej efektywny". Po pierwsze, czy to naprawdę jest wąskie gardło?Oczywiście, 100k wpisów to dużo, ale jeśli musisz to robić tylko co kilka minut, to dobrze, jeśli algorytm zajmuje kilka sekund.

Jedynym obszarem, który można poprawić, jest wykorzystanie pamięci. Jeśli jest to problemem, można pominąć generowanie multimapy i po prostu mapę licznik dookoła, coś jak to (uwaga, mój C++ jest trochę zardzewiały):

std::map<int, int> countFrequency; // count => how many customers with that count 

for (std::map<int, int>::const_iterator it = uc.begin(); 
     it != uc.end(); ++it) 
{ 
    // If it->second is not yet in countFrequency, 
    // the default constructor initializes it to 0. 
    countFrequency[it->second] += 1; 
} 

// Now write this out 
for (std::map<int, int>::const_iterator it = countFrequency.begin(); 
     it != countFrequency.end(); ++it) 
{ 
    std::cout << "==> There are " 
      << it->second << " users that have bought " 
      << it->first << " products(s)" << std::endl; 
} 

Jeśli użytkownik dodaje i kupuje count przedmiotów, można zaktualizować countFrequency z

countFrequency[count] += 1; 

Jeśli istniejący użytkownik przechodzi z oldCount do newCount elementów można zaktualizować countFrequency z

countFrequency[oldCount] -= 1; 
countFrequency[newCount] += 1; 

Teraz, tak jak na marginesie, zalecam używanie do liczenia unsigned int (chyba że istnieje uzasadniony powód negatywnego liczenia) i wpisanie typu userID, aby zwiększyć czytelność.

Answer 4

Tylko dla skowronków, mamy mieszane podejście, które używa vector, jeśli dane są niewielkie, i map, aby uwzględnić przypadek, w którym jeden użytkownik kupił naprawdę absurdalną liczbę produktów. Wątpię, czy naprawdę będziesz potrzebował tego ostatniego w aplikacji sklepowej, ale może się z tego cieszyć ogólniejsza wersja problemu.

typedef std::map<int, int> Map; 
typedef Map::const_iterator It; 

template <typename Container> 
void get_counts(const Map &source, Container &dest) { 
    for (It it = source.begin(); it != source.end(); ++it) { 
     ++dest[it->second]; 
    } 
} 

template <typename Container> 
void print_counts(Container &people, int max_count) { 
    for (int i = 0; i <= max_count; ++i) { 
     if contains(people, i) { 
      std::cout << "==> There are " 
       << people[i] << " users that have bought " 
       << i << " products(s)" << std::endl; 
     } 
    } 
} 


// As an alternative to this overloaded contains(), you could write 
// an overloaded print_counts -- after all the one above is not an 
// efficient way to iterate a sparsely-populated map. 
// Or you might prefer a template function that visits 
// each entry in the container, calling a specified functor to 
// will print the output, and passing it the key and value. 
// This is just the smallest point of customization I thought of. 
bool contains(const Map &c, int key) { 
    return c.count(key); 
} 
bool contains(const std::vector<int, int> &c, int key) { 
    // also check 0 < key < c.size() for a more general-purpose function 
    return c[key]; 
} 

void do_everything(const Map &uc) { 
    // first get the max product count 
    int max_count = 0; 
    for (It it = uc.begin(); it != uc.end(); ++it) { 
     max_count = max(max_count, it->second); 
    } 

    if (max_count > uc.size()) { // or some other threshold 
     Map counts; 
     get_counts(uc, counts); 
     print_counts(counts, max_count); 
    } else { 
     std::vector<int> counts(max_count+1); 
     get_counts(uc, counts); 
     print_counts(counts, max_count); 
    } 
} 

Stąd można byłaby, aby utworzyć klasę szablonu CountReOrderer, która przyjmuje parametr szablonu informując go, czy użyć vector lub map dla hrabiów.