 |
dev.gamez.lv
Latvian Game Developers Community
|
| View previous topic :: View next topic |
| Author |
Message |
elvman
Indago Uzvarētājs
Joined: 09 Apr 2003
Posts: 1278
Location: Kuldiga
|
 Posted: Thu Jul 26, 2007 6:38 pm Post subject: identifikatori |
|
Principā šis būs diezgan plašs jautājums un ceru, ka kāds varēs palīdzēt.
Tātad piereģistrējoties manā spēlē MySQL piešķir lietotājam ID (nu kā jau MySQL to dara ar auto_increment). Uz klienta un servera tiek glabāta liste ar lietotājiem, kas šobrīd ir ielogojušies. Liste izskatās apmēram šādi:
| Code: | template <typename T>class CList
{
T* operator [](unsigned int nID)
{
if (nID==0 || nID>m_nNumElements)
return 0;
return m_pElements[nID-1]; //-1 tāpēc, ka listes pirmais elements ir 1 nevis 0
}
T** m_pElements; //šeit glabājas visi elementi
} |
m_pElements sevī glabā masīvu ar pointeriem, kas visu laiku tiek paplašināts. Problēma ir tāda, ka, ja ielogojas lietotājs ar ID, piemēram, miljons, tad m_pElements ir jāpaplašina līdz šim miljonam (tātad atmiņā glabājas miljons*4 baiti=4 megabaiti). Diezgan neizdevīgi, tāpēc domāju citu metodi:
glabājam atmiņā tikai tik elementu, cik ir ielogojušuies, bet katram elementam glabāt arī viņa id. Tādā veidā iegūstam kodu:
| Code: | T* operator [](unsigned int nID)
{
for (int i=0;i<m_nNumElements;i++)
if (m_pElements[nID-1]->m_nID==i)
return m_pElements[i];
} |
Otrajā gadījumā netiek tērēta tik liela atmiņa, taču lai iegūtu kādu saraksta elementu ir jābrauc cauri visiem elementiem, tātad šī metode atkal ir lēna.
Ir doma, ka varētu izmantot pirmo variantu, bet nepieļaut lielāku ID par, piemēram, 1000. Bet tādā gadījumā ir jādzēš laukā vecie/neaktīvie lietotāji. Problēma ar šo variantu ir tā, ka MySQL nav nekādu iespēju likt izmantot neizmantotos ID. Piemēram, ja lietotājs ar ID 1 ir izdzēsts, tad nākošajam lietotājam tiks piešķirts šis ID nevis nākošais aiz pēdējā. Var protams SETot ieraksta ID uz kautkādu tukšo, bet tas laikam nav labi.
Bija domas arī ar dažādākām savādākām metodēm, piemēram, glabājot atmiņa vairākus masīvus, kurā katrs satur sevī, teiksim, 10 elementus.
Pagaidām sistēma ir tāda, ka, ielogojoties, lietotājam tiek piešķirts kaut kāds ID, kas neatbilst tam ID, kas ir datubāzē, taču šādā variantā ir jātaisa lookup table, kur katram lietotāja ID atbils viņa ID datubāzē. Vopšim šis variants ir diezgan čakarīgs un dēļ šī varētu rasites daudz bagi (piemēram, netīšām no datubāzēs SELECTēt datus ar to ID, ko viņam piešķīra serveris, nevis MySQL). Tāpēc, es gribētu, ka lietotājam ielogojoties tiktu piešķirts tāds pats ID, kā datubāzē.
Vajadzētu jūsu padomus kā labāk šito visu noorganizēt, jo pats īsi nevaru izdomāt, kā to labāk/izdevīgāk darīt.
P.S. Ceru, ka sapratāt, ko es mēģināju pateikt/jautāt?
_________________
long time; /* know C */ |
|
| Back to top |
|
 |
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Thu Jul 26, 2007 7:21 pm Post subject: |
|
em.. par std::map esi dzirdējis? Man izklausās, ka ar savu CList tu centies realizēt to pašu, ko dara std::map<unsigned int, T>, ne tā?
No std::map var dzēst/ielikt/lookapout elementus O(logN) laikā. Ja gribi ātrāk, tad ņem "nestandarta" std::hash_map. Tas to pašu ļaus darīt O(1+c) laikā.
Ja jau programmējam C++, tad programmējam pa īstam un lietojam STL (Standart Template library) piedāvātās iespējas, nevis gudrojam divriteņus ;) |
|
| Back to top |
|
|
elvman
Indago Uzvarētājs
Joined: 09 Apr 2003
Posts: 1278
Location: Kuldiga
|
| Posted: Thu Jul 26, 2007 8:34 pm Post subject: |
|
Ok, paldies! STL esmu izmantojis diezgan maz, meegjinaashu laboties. Ja jau hash_map ir aatraaks kaa map, tad kaapeec lielaakaa dalja koderu izmanto leenaako variantu?
_________________
long time; /* know C */ |
|
| Back to top |
|
|
elvman
Indago Uzvarētājs
Joined: 09 Apr 2003
Posts: 1278
Location: Kuldiga
|
| Posted: Thu Jul 26, 2007 8:52 pm Post subject: |
|
Ok, hash_map neivero secibu un tapec ir atraks. Taka seciba man nu toch nav vajadziga, tad izmantoshu hash_map. Un paldies tev bubu, es jau domaaju, ka atrisinaajums buus galiigi savaadaaks, kaa biju domaajis.
_________________
long time; /* know C */ |
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Thu Jul 26, 2007 9:49 pm Post subject: |
|
| elvman wrote: | | Ok, paldies! STL esmu izmantojis diezgan maz, meegjinaashu laboties. |
Ui ku slikti, labojies gan! :) STL's ir dikti ērts, ja to pareizi sāk lietot, un padara daudzas lietas ātrāk uztaisāmas.
| Quote: | | Ja jau hash_map ir aatraaks kaa map, tad kaapeec lielaakaa dalja koderu izmanto leenaako variantu? |
Tāpēc, ka tās nav C++ standartā. Uz citādāka kompilatora (teorētiski pat uz citas kompilatora versijas) tam var būt sazinkāds-savādāks interfeiss.
| elvman wrote: | | Ok, hash_map neivero secibu un tapec ir atraks. |
Nepareizi. Ātrāks tas ir tikai tāpēc, ka apakšā par datu struktūru datu glabāšanai izmanto heštabulu, atšķirībā no bināra koka (parasti red-black) std::map gadījumā.
Lai efektīvi lietotu STL ir jābūt nojausmai par to kādas datu struktūras STL konteineriem ir apakšā un kā notiek darbības ar tiem. Citādi var iebraukt auzās (programma būs lēna/krašos un tml). |
|
| Back to top |
|
|
elvman
Indago Uzvarētājs
Joined: 09 Apr 2003
Posts: 1278
Location: Kuldiga
|
| Posted: Thu Jul 26, 2007 10:25 pm Post subject: |
|
| Quote: | | However, a map template automatically orders its elements as they're inserted, therefore lookups are a little slower. |
Taa ir visur skaidrots.
P.S. Man ir viens jautaajums. Es ar
izveidoju jaunu useri un ielieku 3. "slotā". Bet vai ir iespēja pārbaudīt, vai 3. slotā kautkas ir ielikts. Ja es pārbaudīšu šādi
tad viņš automātiski pievienos 3 "slotu", bet vai ir iespējams pārbaudīt bez "pievienošanas"? Meklēju dokumentācijās un kodā, bet neko neatradu.
_________________
long time; /* know C */ |
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Thu Jul 26, 2007 10:39 pm Post subject: |
|
Ielikt vajag ar insert metodi:
| Code: | | list.insert(std::make_pair(3, new CUser())); |
Pārbaudīt vai ir vajag ar find metodi:
| Code: | | if (list.find(3) != list.end()) { ir } else { nav } |
Last edited by bubu on Thu Jul 26, 2007 10:40 pm; edited 1 time in total |
|
| Back to top |
|
|
elvman
Indago Uzvarētājs
Joined: 09 Apr 2003
Posts: 1278
Location: Kuldiga
|
| Posted: Thu Jul 26, 2007 10:40 pm Post subject: |
|
Ok, atradu. Mappingu var pārbaudīt tā:
| Code: | | if (m.find(x) != m.end()) |
_________________
long time; /* know C */ |
|
| Back to top |
|
|
elvman
Indago Uzvarētājs
Joined: 09 Apr 2003
Posts: 1278
Location: Kuldiga
|
| Posted: Thu Jul 26, 2007 11:20 pm Post subject: |
|
Njā, <hash_map> includošana manai Debug versijas programmai izmaksāja nieka 700 KB.
_________________
long time; /* know C */ |
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Thu Jul 26, 2007 11:42 pm Post subject: |
|
| Kāds iemesls mērīt debug modes izpildāmo failu? Tur tka daudz kā lieka. |
|
| Back to top |
|
|
elvman
Indago Uzvarētājs
Joined: 09 Apr 2003
Posts: 1278
Location: Kuldiga
|
| Posted: Fri Aug 03, 2007 10:03 pm Post subject: |
|
Vai ir kaut kāds laibrarijs, kas pilda tādas pašas funkcijas, kā hash_map? Man īsti nepatīk, ka viņš nav cross-platform un map negribas izmantot dēļ ātruma (lēnuma).
_________________
long time; /* know C */ |
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Fri Aug 03, 2007 10:25 pm Post subject: |
|
Nu redz :) Tev arī nepatīk hash_map nestandartiskuma dēļ.
Jāgaida nākamais STL updeits (TR1), tajā būs iekšā unordered_map, kas dara to pašu ko hash_map.
Tikmēr vari paņemt piemēram STLport. Tā ir open-source STL implementācija, kuru var nokompilēt gan uz MSVC, gan GCC, gan BorlandC++, gan vēl uz sazinkā... Cilvēki baumo, ka tā esot ātrāka par MSVC STL implementāciju (stringiem, vektoriem, mapiem, strīmiem). Tik ja tu to ņem, tad neņem veco 4 versiju, ņem jauno 5 versiju. Ar 4 versiju man visādi brīnumi bija - grūti bija, piemēram, piedabūt to nokompilēties ar msvc2005ee.
Vēl jau ir diezgan vienkāršs un universāls variants - realizēt pašam savu mapu heštabulā - http://en.wikipedia.org/wiki/Hash_table Darbošanās algoritms ir diezgan vienkāršs. Pie tam domāju, ka katras universitātes datorzinātņu kursa pirmajos kursos lielais vairums ir realizējuši savu haštabulu kā mājasdarbu vai pratisko darbu. Tā ka nekas neiespējams tas nav ;) |
|
| Back to top |
|
|
elvman
Indago Uzvarētājs
Joined: 09 Apr 2003
Posts: 1278
Location: Kuldiga
|
| Posted: Fri Aug 03, 2007 10:34 pm Post subject: |
|
Njā, palasiju par RT1 un tas vairāk izklausās pēc sapņa varianta, nevis realitātes. Palasiju teoriju un izskatās, ka pašam uzkodet arī nebūtu tik nereāli, taka tagad jāizdomā, kodēt pašam, vai ņemt to STLPort.
_________________
long time; /* know C */
Last edited by elvman on Fri Aug 03, 2007 10:39 pm; edited 3 times in total |
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Fri Aug 03, 2007 10:37 pm Post subject: |
|
TR1 jau tagad ir diezgan liela realitāte - boost bibliotēka ir implementējusi gandrīz vai visu tr1, izņemot šos hash_xx konteinerus.
Īstenībā pat ir tā, ka dažas fīčas tr1 ir iespaidojies no jau boost'ā implementētām fīčām. |
|
| Back to top |
|
|
elvman
Indago Uzvarētājs
Joined: 09 Apr 2003
Posts: 1278
Location: Kuldiga
|
| Posted: Fri Aug 03, 2007 11:21 pm Post subject: |
|
Patiesībā, tas nemaz nebūtu tik grūti modificēt manu CList klasi, lai tā hashotu visus datus. Atgriežamies pie sākuma.
_________________
long time; /* know C */ |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
