[C++] Podatkovne Strukure - Kombinacije

Stvar je taka: imam recimo kombinacije C(100,5) in vsaki tej kombinaciji priredim neko vrednost, ki je popolnoma neodvisna od številk, ki so v kombinaciji. Problem pa je to shraniti v neko strukturo. V petdimenzionalno tabelo je tole spravljati overkill, saj potem bo zasedena le 1/120tina celotne tabele, program pa bo rezerviral vso, kar pa verjetno pripelje do pomanjkanja pomnilnika, česar pa sploh nočemo saj potrebujemo hiter dostop do podatkov. Torej zanima me če ima kdo že spisano kakšno tako strukturo, ki ima konstantno O(1) hitrost iskanja podatkov glede na podano kombinacijo(recimo getData(0,1,2,3,4)). Čas ustvarjanja strukture in dodajanja elemntov ni pomemben, ker pri mojem problemu to predstavlja le majhen delček proti iskanju po strukturi. Zato bi prosil če kdo že ima spisano kakšno tako strukturo, ali pa vsaj kakšen namig kako narediti, saj sem trenutno v C++ še bolj kot ne zelen :)

lep pozdrav,
Rok

Če boš vsem možnim kombinacijam priredil neko vrednost potem uporabi enodimenzionalno tabelo in definiraj funkcijo, ki ti za vsako kombinacijo izračuna enolično pozicijo.

Drevo oz. asociativni kontejner imaš pa implementiran v <map> Z map zna biti zadeva lažje izvedljiva (ne rabiš funkcije za pozicijo) ampak bo pa bolj počasna, ne bo več O(1).

Bleeh, stringi so pocasna rec. Jaz bi tole se precej bol zbanaliziral kot Sergio... ;)

Koliko je vseh mogocih kombinacij? 100.000? Torej naredimo nekako takole (pogoj je, da imas prej dvodimenzionalno tabelo kljucev in vrednosti):

  char *key[100000];

  for (i = 0; i < NUMBER_OF_PAIRS; i++)
  {
    if (start_table[i].key > 0)
    {
      temp = i;
      key[temp] = malloc(LENGTH_VALUE);
      memcpy(key[temp], start_table[i].value, LENGTH_VALUE);
    }
  }

Tako napolnis 'lookup tabelo'. V bistvu bi se lahko se tistega malloc+memcpy znebil, da ne bi podvajal podatkov ampak bi namesto tistih dveh vrstic v zanki naredil kar:

  key[temp] = &start_table[i].value;

Do posamezne vrednosti za neko kombinacijo pa potem prides kar z:

  int some_key = 44433;
  printf("Key: %d, Value: %s\n", some_key, key[some_key]); // Tole izpise vrednost za kombinacijo 44433...

Tako ostanes pri O(1), porabil bos tistih 400kB rama za key[], 4MB, ce imas 1mio kombinacij. Tabela teh pointerjev bo res v vecini prazna ampak, 400kB? :)

Dodajanje novih elementov je trivialno. Brisanje pa tudi. Se mi zdi, da katerakoli druga resitev ne bo vec O(1) in bo ponucala vec procesorskih ciklov za opravljanje svojega dela. :) Tukaj niti ne isces vec svojih vrednosti, ker ze takoj ves kjer so.

No ja, vse skupaj ni nic kaj C++ resitev. Jo pa lahko nardis tako. :)

Ja, ce sta lahko poljubna, je moj predlog zmerno, do pretezno neuporaben. ;)