» »

[C++] Podatkovne Strukure - Kombinacije

[C++] Podatkovne Strukure - Kombinacije

Rokm ::

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

ježek ::

Brez rezervacije pomnilnika bi po mojem mnenju bilo najhitrejše AVL drevo. Sicer ni O(1), je pa O(logN/log2). To pomeni, če imaš 1000 elementov iskanega v najslabšem primeru najde v desetem poskusu, če imaš miljon elementov v dvajsetem poskusu ... Potem pa se da vse skupaj še malo optimizirati (z uporabo statističnih metod, preslikav ...), samo to je zelo težaško delo.

Gundolf ::

Č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).

Sergio ::

Sej najbrž preveč banaliziram, ampak jaz bi uporabil hash tabelo s ključem std::string, offsete pa delimitiral z vejico.

Torej ce imas 0,1,2,3,4 kljuc, naredis "0,1,2,3,4" string, in spravis stvar v razprseno tabelo.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

BigWhale ::

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. :)

Zgodovina sprememb…

  • spremenil: BigWhale ()

nevone ::

> imam recimo kombinacije C(100,5)

A tale recimo pomeni, da sta k in n lahko poljubna? Oziroma, kakšne so omejitve za to nalogo?

o+ nevone
Either we will eat the Space or Space will eat us.

BigWhale ::

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


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Python - pomoč (strani: 1 2 3 )

Oddelek: Programiranje
10317114 (7862) black ice
»

največkrat pojavljeni element v tabeli

Oddelek: Programiranje
181842 (1217) pac1
»

[C] struct in int[] (strani: 1 2 )

Oddelek: Programiranje
656785 (5858) MrBrdo
»

Baza & c#

Oddelek: Programiranje
214005 (3063) xardas
»

[c++]iskalnik po bazi podatkov

Oddelek: Programiranje
12988 (888) Gundolf

Več podobnih tem