Szybkie i eleganckie jednokierunkowe mapowanie znanych wartości całkowitych

Question

Muszę odwzorować zestaw znanych liczb całkowitych na inny zestaw znanych liczb całkowitych, relację 1-do-1, wszystkie wstępnie zdefiniowane i tak dalej. Więc załóżmy, że mam coś takiego (C++, uproszczony, ale dostaniesz pomysł):

struct s { int a; int b; }; 

s theMap[] = { {2, 5}, {79, 12958 } }; 

Teraz podano liczbę całkowitą wejściowy, powiedzmy 79, to muszę znaleźć odpowiedni wynik z theMap (oczywiście 12958). Jakąkolwiek dobrą i szybką metodę to zrobić, zamiast swojej pętli for-the-mill for? Inne sugestie dotyczące struktury danych również są mile widziane, ale mapa powinna być łatwa do ręcznego zapisu w źródle.

Wartości w obu zestawach mieszczą się w zakresie od 0 do 2^16, a istnieje tylko około 130 par. To, nad czym się również zajmuję, to bardzo prosty sposób statycznej inicjalizacji danych.

Answer 1

Użyj mapy

#include <map> 
#include <iostream> 

int main() { 
    std::map <int, int> m; 
    m[79] = 12958; 
    std::cout << m[79] << std::endl; 
} 

pomocą mapy jest najbardziej ogólne rozwiązania i najbardziej przenośne (++ standard C nie obsługuje jeszcze tablic hash, ale są one bardzo powszechne rozszerzenie). Nie jest to jednak najszybszy najszybszy sposób. Zarówno rozwiązanie do wyszukiwania binarnego, jak i do rozwiązań wymuszania sugerowane przez innych może (ale nie będzie) wykonać go z wyprzedzeniem. Prawdopodobnie nie będzie to miało znaczenia dla większości aplikacji.

Answer 2

Dlaczego nie zaszyfrowana mapa? Zapewni ona mniej lub bardziej stałe czasy pobierania dla dowolnego klucza.

Answer 3

std::map<int, int> theMap; 
theMap[2] = 5; 
std::map<int, int>::const_iterator iter = theMap.find(2); 
if (iter != theMap.end()) 
    iter->second; // found it 

Wstawianie par wartości int, pobieranie wartości przez klucz, złożoność logarytmiczna. Jeśli masz naprawdę duży zestaw danych i potrzebujesz szybszego pobierania, użyj std :: tr1 :: unordered_map lub boost :: unordered_map (w przypadku, gdy twoja biblioteka standardowa nie ma implementacji TR1).

Answer 4

std::map lub std::unordered_map jest prawdopodobnie najczystszym, jaki dostaniesz. Niestety C++ nie ma wbudowanych tablic asocjacyjnych.

std::map<int,int> mymap; // the same with unordered map 

// one way of inserting 
mymap.insert (std::make_pair(2,5)); 
mymap.insert (std::make_pair(79,12958)); 

// another 
mymap[2] = 5; 
mymap[79] = 12958; 

Aby sprawdzić

std::map<int,int>::const_iterator iter = mymap.find(2); 
if (iter != mymap.end()) 
{ 
    // found 
    int value = iter->second; 
} 

unordered_map ma tę zaletę O(1) zamortyzowanego czasu przeglądowej w przeciwieństwie do O(log n) z map.

Answer 5

Masz dobry pomysł, to mapa. Użyj std::map.

Answer 6

Sortuj tablicę według klucza i wykonaj wyszukiwanie binarne.

Answer 7

Jeśli jesteś w 100% pewny, że theMap nie wzrośnie do ponad 1000 wpisów (profil!), Prawdopodobnie szybciej zrobi wyszukiwanie binarne.

Jeśli wartość a ma rozsądną granicę (na przykład poniżej 1000), można po prostu utworzyć prostą tablicę o wartości a jako indeks gwarantowanej złożoności O (1). Jeśli używasz gcc można użyć tej składni (http://gcc.gnu.org/onlinedocs/gcc/Designated-Inits.html#Designated-Inits):

int theMap[256] = { [2] = 5, [79] = 12958 }; 

(To nie jest obsługiwana przez g ++, niestety)

W innych przypadkach należy użyć std::unordered_map jak pokazano w innych odpowiedzi.

Answer 8

Jeśli liczba twoich liczb źródłowych i jest stosunkowo wysoki (tak, że Direct Search staje się nieskuteczny), ale jeszcze do opanowania, można stosunkowo łatwo zbudować idealny funkcji skrótu hash(i) dla liczb wejściowych (z wykorzystaniem Pearson hashing, na przykład) i następnie użyj zaszyfrowany wartość jako wejścia w tabeli wyjściowej map

output = map[hash(i)]; 

oczywiście, jeśli zakres wartości wejściowych jest stosunkowo niewielka, można użyć funkcji tożsamości zamiast hash i po prostu obrócić całość w zmienione odwzorowanie

output = map[i]; 

(chociaż gdyby tak było byś nie prawdopodobnie nawet pytać.)

Answer 9

Twój pseudokod jest prawie poprawny kod C++ 0x - ale C++ 0x wymaga mniej!

map<int, int> theMap = { {2, 5}, {79, 12958 } }; 
assert (theMap[ 2 ] == 5); 

W "normalnej" C++, trzeba zainicjować mapę tak, nadal dość elegancki:

pair< int, int > map_array[2] = { make_pair(2, 5), make_pair(79, 12958) }; 
map< int, int > theMap(&map_array[0], &map_array[2]); // sorts the array 
assert (theMap[ 2 ] == 5); 

to szybko pisać i szybko uciekać!

Edytuj: Po prostu nie zmieniaj mapy jako zmiennej globalnej. (Chociaż jest to bezpieczne w C++ 0x). Jeśli to zrobisz, zostanie ono zainicjowane poprawnie tylko wtedy, gdy kompilator zdecyduje się zainicjować go po map_array, który jest BARDZO nie gwarantowany. Jeśli chcesz być globalnym, zainicjuj go za pomocą theMap.assign(&map_array[0], &map_array[2]);.

Answer 10

Stół do skoków. Przełącznik prawdopodobnie to ustawi, jeśli będziesz w stanie go użyć, w przeciwnym razie możesz potrzebować jakiegoś zespołu, ale to prawdopodobnie najszybszy sposób.

Answer 11

Jeśli potrzebujesz kompilacji mapowania można użyć następującej formy:

// template to specialize 
template<int T> struct int2int {};  

// macro for simplifying declaration of specializations 
#define I2I_DEF(x, v) template<> struct int2int<x> { static const int value = v; }; 

// definitions 
I2I_DEF(2, 5) I2I_DEF(79, 12958) I2I_DEF(55, 100) // etc. 

// use 
#include <iostream>  
int main() 
{ 
    std::cout << int2int<2>::value << " " << int2int<79>::value << std::endl; 

    return 0; 
} 

Answer 12

jako dodatkowe, jeśli trzeba binarny wdrożenie wyszukiwarki, nie wychodzą z biblioteki standardowej C++. Dodaje się robi jeden na tablicy typu konstrukcji z wykorzystaniem algorytmu equal_range (przeprosiny za nieco hacky jakości kodu)

#include <algorithm> 
#include <iostream> 
using namespace std; 

struct S { 
    int k, v; 
}; 

bool operator <(const S & a, const S & b) { 
    return a.k < b.k; 
}; 

// must be sorted in key order 
S values[] = {{42,123},{666,27}}; 

int main() { 

    S t; 
    cin >> t.k; 

    S * valend = &values[0] + sizeof(values)/sizeof(S); 
    pair <S*,S*> pos = equal_range(&values[0], valend , t); 

    if (pos.first != pos.second) { 
     cout << pos.first->v << endl; 
    } 
    else { 
     cout << "no" << endl; 
    } 
} 

Answer 13

Istnieje również technikę znaną jako „xmacros”, który jest dobry sposób, aby zrobić dokładnie o czym mówisz. Jednak łatwo jest nadużywać tej techniki, więc zawsze zalecam używanie jej z ostrożnością. Sprawdź: http://en.wikipedia.org/wiki/C_preprocessor#X-Macros

Podstawowym Istotą jest, masz plik gdzie notować swoje mapowania powiedzieć foo.txt który wygląda tak: mapie (2,5)
mapie (79,12958)
. ..

Następnie należy zdefiniować makro MAP (A, B), które pobiera te dwa argumenty i wykonuje dla Ciebie inicjalizację. Następnie wstaw plik (foo.txt). Możesz nawet zrobić to w wielu przejściach, jeśli chcesz, redefiniując makro pomiędzy każdym z nich. Następnie, aby dodać więcej mapowań, po prostu dodajesz je do pliku foo.txt i rekompilujesz. Jest bardzo potężny i może być używany do wielu różnych rzeczy.

Answer 14

Jeśli nie chcesz korzystać z mapy z jakiegoś powodu (na przykład, po prostu chcesz użyć tablicę skonfigurowanej w czasie kompilacji), można również używać w połączeniu z functor<algorithm>:

#include <windows.h> 
#include <cstdlib> 
#include <functional> 
#include <algorithm> 
#include <iostream> 
using namespace std; 

struct s { int a; int b; }; 

s theMap[] = { {2, 5}, {79, 12958 } }; 

struct match_key : public unary_function<s, bool> 
{ 
    match_key(int key) : key_(key) {}; 
    bool operator()(const s& rhs) const 
    { 
     return rhs.a == key_; 
    } 
private: 
    int key_; 
}; 

int main() 
{ 
    size_t mapSize = sizeof(theMap)/sizeof(theMap[0]); 
    s* it = find_if(&theMap[0], &theMap[mapSize], match_key(79)); 
    cout << it->b; 

    return 0; 
} 

Answer 15

Możesz użyć boost :: assign.

#include <iostream> 
#include <boost/assign.hpp> 

int main() 
{ 
    typedef std::map< int, int > int2int_t; 
    typedef int2int_t::const_iterator int2int_cit; 

    const int2int_t theMap 
     = boost::assign::map_list_of 
      (2, 5) 
      (79, 12958) 
      ; 

    int2int_cit it = theMap.find(2); 
    if (it != theMap.end()) 
    { 
     const int result = it->second; 
     std::cout << result << std::endl; 
    } 
}