játékfejlesztés.hu
FórumGarázsprojectekCikkekSegédletekJf.hu versenyekKapcsolatokEgyebek
Legaktívabb fórumozók:
Asylum:    5455
FZoli:    4892
Kuz:    4455
gaborlabor:    4449
kicsy:    4304
TPG:    3402
monostoria:    3284
DMG:    3172
HomeGnome:    2919
Matzi:    2521

Pretender:    2498
szeki:    2440
Seeting:    2306
Geri:    2189
Orphy:    1893
Joga:    1791
Bacce:    1783
MaNiAc:    1735
ddbwo:    1625
syam:    1491
Frissebbek | Korábbi postok
[1] > 2 < [3] [4] [5] [6] [7] [8] [9] [10] [15] [20] [21]
Pretender - Törzstag | 2498 hsz       Online status #190309   2013.01.13 18:44 GMT+1 óra  
Az ütközést úgy értettem, hogy ha nem megfelelő a hash függvény (bár, még akkor is előfordulhat, ha szinte tökéletes), akkor kijöhet ugyan az az index. Akkor keresek majd valami stringhez optimalizált kis hash függvényt, a legtöbbször úgyis arra használom a mapet, hogy string key alapján azonosítsak.
A számolás mondjuk annyival bonyolódik, hogy meg kell határozni egy átlagos műveletigényt két string összehasonlítására, mert ugye egy keresőfához ezt k-szor végre kell hajtani.

   
Asylum - Törzstag | 5455 hsz       Online status #190306   2013.01.13 17:25 GMT+1 óra  
Az ütközést nem értem.

A hashmap teljesitménye a hash függvénytöl függ. Számold ki, hogy n db elemre ha létezik olyan hash fv ami tökéletesen egyenletesen szór, akkor vajon a keresési idö milyen M nagységu táblára lesz < mint 1.44 * log2(n)
C++ fordítóval és macival alszom
http://darthasylum.blog.hu/
   
Pretender - Törzstag | 2498 hsz       Online status #190303   2013.01.13 16:31 GMT+1 óra  
Érdemes hashmappel foglalkozni valamilyen bináris keresőfa helyett, ha mondjuk néhány ezer elemnél több nem kerülne a mapbe? A hasmaphez ugye kell egy hash function, amit talán nem tart túl sokáig végrehajtani, de akkor is. Egy AVL fában 1,44*log2(n) a keresési idő, a hashmapről konstans idejűt mondanak. Mennyire igaz ez, hogy érdemes kivitelezni, stb.? No meg a hasmapnél előfordulhat ütközés, ami egy keresőfában nyilván nem.

   
bolyzsolt - Törzstag | 607 hsz       Online status #189850   2012.12.29 16:48 GMT+1 óra  
A bitwise XOR művelet mit ad vissza C-ben, ha az egyik, vagy mindkét integer negatív? Adhat vissza negatív integert eredményül? Tehát pl. a (int)10 ^ (int)-2 végeredménye mi lesz?

Szerk.: közben meglett, ne fáradjatok

Ezt a hozzászólást bolyzsolt módosította (2012.12.29 16:59 GMT+1 óra, ---)

   
Asylum - Törzstag | 5455 hsz       Online status #189817   2012.12.27 12:02 GMT+1 óra  
Úgy hivják, hogy std::deque
C++ fordítóval és macival alszom
http://darthasylum.blog.hu/
   
Pretender - Törzstag | 2498 hsz       Online status #189812   2012.12.27 09:07 GMT+1 óra  
Amin inkább meglepődtem az az volt, hogy gyorsabb leallokálni egy nagyobb memóriát, és belemásolni az addigi adatokat, mint egyes node-okat külön allokálni, és összefűzni. Persze ilyen kombóval lehetne spórolni, hogy a node-okat pl. placement new-al hozom létre. Sőt, ez nem is rossz ötlet És az akkor a két dolog (vector, list) előnyeit ötvözi... talán...

   
Asylum - Törzstag | 5455 hsz       Online status #189787   2012.12.25 21:45 GMT+1 óra  
Azért a nagy számitási igényü dolgokat nem egy tableten kéne csinálni (milliós listák). Gyakorlatiasabb dolgokban pedig a tabletek is lazán birják a strapát, eleve speciális az architekturájuk.

Eddig az egyetlen dolog amivel sikerült kiakasztanom az az std::set volt, mert tényleg baromi hülyén van leimplementálva; lecseréltem a sajátomra és máris gyorsabb lett (pedig én semmi ilyen lenti trükköt nem alkalmazok, de lehet hogy kibövitem egy default allocatorral).
C++ fordítóval és macival alszom
http://darthasylum.blog.hu/
   
ddbwo - Tag | 1625 hsz       Online status #189784   2012.12.25 21:24 GMT+1 óra  
Pretender: "Csináltam egy tesztet"

Nálam 200 ezer elemre millisec-ben (clock):
Kód:
Pusing to vector: 0
Pushing to list: 62
Reading from vector: 0
Reading from list: 0
Remove first elements from vector: 52250
Remove first elements from list: 63


10 millio elemre millisec-ben:
Kód:
Pusing to vector: 203
Pushing to list: 3156
Reading from vector: 0
Reading from list: 125


A törlést nem várom meg, mert hülye azért nem vagyok... Elég gyors ütemben nőhet.

A clock() csak millisec pontos.
A Half-Life 2: Deathmatch promóció megszűnt! [B¤°
Kezdetben volék az üresség. Ám akkor a Struktúrfüggöny megteremté az Urat.
DrunkenDragon* Blackwolf
   
versio - Tag | 663 hsz       Online status #189779   2012.12.25 20:00 GMT+1 óra  
Pretender: azert tag a memoria eleres intervalluma, mert sok mindentol fugg, a processzor orajeleteol , ami lehet 1.6ghz-es tabla, meg 5 ghz-es sandy bridge, a memoria lehet 1 utas vagy akar 3, sima processzor vagy igp-vel felvertezett(apu), az eddigi processzorok altalaban 64 byte-s cacheline-t alkalmaztak , a haswellnel atternek 128 byte-ra, sot meg a memoria tipusatol is fugg, nanosec -ben adjak meg az ertekeket
   
Pretender - Törzstag | 2498 hsz       Online status #189776   2012.12.25 18:39 GMT+1 óra  
Csináltam egy tesztet. Megírtam egy vectort (kvázi dinamikus tömböt), semmi trükközés, elem beszúrásakor szépen új memóriaterületet foglalok, és az addigi tartalmát átmásolom, az előzőt meg felszabadítom.

A beszúrás sokkal gyorsabb (azaz egyben lefoglalni adatterületet, és a szükséges adatokat (jelen esetben mindig a teljes tömböt) átmásolni (memcpy) olcsóbb, mint egyesével lefoglalni a Node-oknak memóriaterületet).

A bejárás megközelítőleg ugyan annyiba kerül, tehát szinte mindegy neki, hogy szétszórva van-e a memóriában, vagy egymás után.

Az utolsó elem törlése viszont sokkal de sokkal gyorsabbnak tűnik, hiszen míg a vector esetében nem, a list esetében törölni kell a node-okat, amit elég lassan csinál meg. Már fut egy ideje, de még nem fejezte be, és nem biztos, hogy meg fogom várni... Nem is sejtettem volna, hogy egy delete ilyen sokáig tarthat, és ennyire megnyújtja a futási időt.

A legelső elem törlése a vector esetében elég sokáig tart, mert az utána álló összes többi elemet copyzza 1-el előrébb. A memmove nem tudom mennyivel lenne jobb, most azt próbálom. Azért nem cserélem az utolsó elemmel, mert a sorrendet tartani kell. A legelső elem törlése a listából ugyan annyi ideig tart, mint bármely elem törlése a listából.

Nekem a tesztemen valami ilyesmik jöttek ki:
Kód:
// teszt: Vector<int>, List<int>, Size = 10000000
// idő mérése: time.h / clock()
Pusing to vector: 0.12
Pushing to list: 6.922
Reading from vector: 0 // az end-start között nem volt számottevő különbség
Reading from list: 0.059
Remove last elements from vector: 0.009


szerk.:
Egy későbbi teszten a bejárás 0.515 és 0.518 volt.

szerk.2:
Kód:
timeGetTime() használata, és elemszám csökkentése 100000-re:
push vec: 7
push list: 92
read vec: 5
read list: 5
remove first vec: 1994
remove first list: 4900


szerk.3:
Ezzel a két buta, be nem fejezett osztállyal teszteltem:
2044-test.zip

Ezt a hozzászólást Pretender módosította (2012.12.25 18:50 GMT+1 óra, ---)

   
Pretender - Törzstag | 2498 hsz       Online status #189775   2012.12.25 18:24 GMT+1 óra  
@versio: ez mondjuk igaz lehet, bár ezt sose tudtam, hogy ezek a "pontos" (mondjuk most elég tág intervallumot mondtál [200,1000]) órajelek hogy jönnek ki Most folyamatban van egy teszt, következő hsz-ként írom a végeredményt, de igazolódni látszik az, amit mondotok. Legalábbis ezen a gépen, ennyi memóriával.

   
versio - Tag | 663 hsz       Online status #189774   2012.12.25 18:00 GMT+1 óra  
Pretender: a mai processzoroknal memoria muveletre kell optimalizalni, gondolj bele ha egy adat nincs a cache-ben , akkor 200-1000 orajelre leall a processzor , es megvarja mig becsorog az adat a memoriabol az L3-ba ,onnan az L2-be ,onnan az L1-be , es vegul egy regiszterbe, es amikor ez megtortenik akkor indul ujra a feldolgozas, a veszteseg ezalatt az ido alatt 1200-6000 muvelet, AVX2 eseteben 3200-16000 muvelet
   
ddbwo - Tag | 1625 hsz       Online status #189773   2012.12.25 17:12 GMT+1 óra  
Mindennek megvan a maga helye, pl egy ilyen megoldás is legyilkolja az egész rendszer lényegét:
- a C++ fórumzsiványok és Bjorn szerint -

vector<int*> integetek;
A Half-Life 2: Deathmatch promóció megszűnt! [B¤°
Kezdetben volék az üresség. Ám akkor a Struktúrfüggöny megteremté az Urat.
DrunkenDragon* Blackwolf
   
Pretender - Törzstag | 2498 hsz       Online status #189772   2012.12.25 16:54 GMT+1 óra  
és tömböt hogy foglalsz le? táncsak nem megkéred az oprendszert, hogy adjon memóriaterületet?
És mi van az állítólagos 1 millió elemes tömbbel, ha mondjuk a 0. és az utolsó elemet akarom elkérni egymás után? Az ugyan olyan ugrás a memóriában.
Berakni és kivenni sorrendet tartva továbbra is sokba kerül: új memóriaterületet lefoglalni, az eddigieket átmozgatni, beszúrni / kivenni a megfelelő elemet, stb.
Ez a karácsonyfa, amit meg írtál versio, állítom, hogy lassabb, mint simán memcpy-zni a kódot. Eleve van 3 array, az index kiszámolása tovább tart, stb-stb.

Nomeg továbbra is fennáll a "hibrid megoldás", ami egy láncolt lista node-jait tárolja tömbben. Így aztán sorrendet tartva beszúrni / kivenni elemet is ugyan olyan gyors, mint egy egyszerű listánál. Itt, a valós időben nem ordóban kell beszélni, hogy: "hát ez 1000000*n, szóval n, azaz lineáris idejű"

Ráadásul mi van az olyan esettel, ha nem intet akarok a tömbben tárolni, hanem int*-ot mondjuk?
Kód:
int* a = new int[10];
int* b = new int[20];
// ...
// a T-be "behelyettesítve":
int** data;
data[0] = a;
data[1] = b;
// ...

én a tömbben hiába érem el gyorsan a címet, ha az egy tök másik memóriaterületre mutat. Akkor már ugyan ott vagy, mint egy listával.

   
Joga - Törzstag | 1791 hsz       Online status #189771   2012.12.25 16:46 GMT+1 óra  
úgy, hogy memóriát lefoglalni nem valami gyors, míg ha nagyobb blokkokban foglalsz és te magad manageled a lefoglalást, nem kell az operációs rendszernek szenvednie.
A tömb meg simán azért jobb, mert a proci cache-e jobban szereti azösszefüggő memóriaterületeket, mint az összevissza szórt memóriaszeleteket.
(ಠ ›ಠ) Stewie!

   
Pretender - Törzstag | 2498 hsz       Online status #189770   2012.12.25 16:41 GMT+1 óra  
Nem tudom ez a 200-1000 meg a 10 órajel hogy jött ki neked, de biztos igazad van
Többek között, ahogy látom elembeszúráskor / törléskor több tömböt is birizgálsz, szóval a nagy említett "lassú a memóriában ugrálni" dolog nálad is megvan, ráadásul 2x-3x. Hogy lesz az 10 órajel?
Mind1, inkább hagyom, tudjuk, hogy mindig neked van igazad, és (már megint) megváltod a világot.

   
versio - Tag | 663 hsz       Online status #189769   2012.12.25 16:28 GMT+1 óra  
vegyunk egy tok egyszeru listat ami INT tipust tarol: ebben az esetben a beszuras a listaba igy tortenik :

LISTELEMENT* elem = new LISTELEMENT(object)
List.Add(elem);

na ez a 2 sor 200-1000 orajel , en megoldottam 10 orajel alatt, tehat 20-100-szoros a gorsulas

-------------
muvelet a lista osszes elemen:

mive a processzor csak cacheline-okban tud memoriat olvasni ami 128 byte igy a lista egy elemehez 128 byte -ot kell beolvasni, pl egy 1 millio elemszamu listahoz 128 megabyte olvasas szukseges, holott az elmeleti maximum 4 megabyte, 30-szor tobb !!!
de ne higyjuk hogy megusszuk "csak" ennyivel, mivel a tombos megoldasnal az 1 millio elem befer a processzor cachebe az eleresi ido 1 orajel kornyeken mozog, mig a 128 megabyteos elavult STD, vagy altalanos lista totalis cache miss-t okoz, igy minden elem elerese 200-1000 orajel
tehat a gyorsulas 200-1000-szeres

a programozas muveszet...
   
Pretender - Törzstag | 2498 hsz       Online status #189759   2012.12.25 13:48 GMT+1 óra  
Az szarabb, a memcpy tesztek alapján gyorsabb. Na nem baj, majd valamit alakítok a saját kis listemben meg vectoromban.

   
Asylum - Törzstag | 5455 hsz       Online status #189757   2012.12.25 13:39 GMT+1 óra  
Minden STL konténernek meg lehet adni template paraméterben allocatort, szóval az std::list böven hatékonyabb a megfelelö esetben.

A vectornál ráadásul mégcsak nemis memcpy a másolás, hiszen ezt nem teheti meg; ott minden elemre meghivodik az operator =.
C++ fordítóval és macival alszom
http://darthasylum.blog.hu/
   
ddbwo - Tag | 1625 hsz       Online status #189755   2012.12.25 12:39 GMT+1 óra  
Olyankor átmásolja, de az csak esetenként fordul elő, mert előre sokat foglal.
A Half-Life 2: Deathmatch promóció megszűnt! [B¤°
Kezdetben volék az üresség. Ám akkor a Struktúrfüggöny megteremté az Urat.
DrunkenDragon* Blackwolf
   
Pretender - Törzstag | 2498 hsz       Online status #189752   2012.12.25 11:56 GMT+1 óra  
és szerinted ha új területet foglal le, akkor abba hogy kerül bele az adat?

   
ddbwo - Tag | 1625 hsz       Online status #189747   2012.12.25 09:59 GMT+1 óra  
Kicsit átcsapongott a téma c++ felé.

Gyakorlatilag az std::vector esetében nem kell folyamatosan új területeket foglalni és másolgatni. Ha kinövi magát, akkor lefoglal pluszba előre, de elem törlésnél is megmarad.
A Half-Life 2: Deathmatch promóció megszűnt! [B¤°
Kezdetben volék az üresség. Ám akkor a Struktúrfüggöny megteremté az Urat.
DrunkenDragon* Blackwolf
   
Pretender - Törzstag | 2498 hsz       Online status #189746   2012.12.25 08:28 GMT+1 óra  
hm... folyamatos elem kivétel és berakás mellett gyorsabb a szinte teljes adatterületet átmásolni egy másikba, mint átállítani 4 pointert, és azok mentén mászkálni? Az keménynek hangzik.

szerk.:
Erről viszont eszembe jutott egy olyan megoldás, hogy ezt a memóriaterületes ugrálást elkerüljem, a fejelemeket egy tömbben tárolom, amellett, hogy jobbra-balra hivatkoznak egymásra. Így amikor berakok egy elemet, ha betelt a tömb, lefoglalok egy 2x akkorát. Így ezek a Node-ok egy tömbben lesznek, azaz nem lesznek szétszórva a memóriában.
Bár ha jól sejtem, akkor ilyenkor nem használhatok pointereket meg new-t (mert az egy másik memóriaterületre mutat, és nem nyertem semmit), ami addig nem baj, amíg be nem telik a stack.

Ezt a hozzászólást Pretender módosította (2012.12.25 08:34 GMT+1 óra, ---)

   
Geri - Törzstag | 2189 hsz       Online status #189744   2012.12.24 23:19 GMT+1 óra  
ha ezerszer nem is, 5-15x gyorsabb a tömbös megoldás. a drónokként memóriában lebegő memóriaterületekről drónokként memóriában lévő memóriaterületekre ugrani 20-30 órajel.

   
versio - Tag | 663 hsz       Online status #189741   2012.12.24 16:09 GMT+1 óra  
Pretender : a feltetel vizsgalattol nem kell felni , amig jol csinalod , az if then else lefutasa ugy nez ki hogy az egyik ag 1 orajel vegrehajtasu, mig a masik 20 ( a 20 utasitas hosszu pipeline-t ujra kell tolteni) , a processzorban van erre egy egyseg ami ezeket elemzi , ugy hivjak hogy elagazasbecslo unit, es tarolja hogy az elagazasod merre megy tovabb nagyobb valoszinuseggel
tehat ha olyan feltetel vizsgalatokat hasznalsz mint ami ebben a kodban is van , hogy az egyik ag eselye 1% alatt van, mig a masik 99% folott, a vegrehajtasi ido 1.00001 orajel
   
versio - Tag | 663 hsz       Online status #189740   2012.12.24 16:05 GMT+1 óra  
"Ez meg miféle mutáns nyelv?"

sajat fejlesztes
   
Asylum - Törzstag | 5455 hsz       Online status #189738   2012.12.24 15:39 GMT+1 óra  
Ez meg miféle mutáns nyelv?

vector vs. list: aki érti az használja, aki nem érti az varacskol. Az STL implementációja lassú, nem a mögötte levö algoritmus; annál eltérőbbet pedig fölösleges csinálni.
C++ fordítóval és macival alszom
http://darthasylum.blog.hu/
   
versio - Tag | 663 hsz       Online status #189734   2012.12.24 14:50 GMT+1 óra  
Pretender: a cache miss rohadt draga, ha nem erted hogy ez mitol gyorsabb, akkor az baj ,
300 orajel egy memoria olvasas , egy mai APU-n amin a igp is szivattyuzza a memoriat meg 1000 orajel korul van

Ezt a hozzászólást versio módosította (2012.12.24 16:04 GMT+1 óra, ---)
   
ramoryan - Törzstag | 442 hsz       Online status #189733   2012.12.24 13:25 GMT+1 óra  
De legalább szépen fel van díszítve...

   
Pretender - Törzstag | 2498 hsz       Online status #189732   2012.12.24 13:09 GMT+1 óra  
Ahogy látom semmivel sem jobb, mint egy list Van ott szépen memória allokálás, meg másolás, ráadásul még az elem elérés is lassabb. De azért nem rossz gondolat... Ráadásul folyamatos feltételvizsgálat (hogy az éppen üres-e) még lassabbá is teszi. De azért köszi

   
versio - Tag | 663 hsz       Online status #189731   2012.12.24 12:10 GMT+1 óra  
karacsonyi ajandek , a sajat listam az enginembol

Kód:
///////////////////////////////////////////////////////////////////////////////////////////////////////////
// List
///////////////////////////////////////////////////////////////////////////////////////////////////////////
#pragma once
///////////////////////////////////////////////////////////////////////////////////////////////////////////
#include "Basic.h"
///////////////////////////////////////////////////////////////////////////////////////////////////////////
namespace
{
template <class T> class LIST
{
template <class T> struct DATA : REFERENCE
{
//*********************************************************************************************
bool* EmptyArray;
//---------------------------------------------------------------------------------------------
T* Array;
int ArraySize;
int ArrayCount;
//---------------------------------------------------------------------------------------------
int* FreeArray;
int FreeArraySize;
int FreeArrayCount;
//---------------------------------------------------------------------------------------------
int* IndexArray;
bool IndexArrayFlag;
//*********************************************************************************************
};

public:

POINTER<DATA<T>> Data;

//---------------------------------------------------------------------------------------------
// CONSTRUCTOR
//---------------------------------------------------------------------------------------------
LIST() { Init(); }
//---------------------------------------------------------------------------------------------
// DESTRUCTOR
//---------------------------------------------------------------------------------------------
~LIST()
{
if($.Reference == 0)
{
SAFE::DeleteArray($.Array);
SAFE::DeleteArray($.EmptyArray);
SAFE::DeleteArray($.FreeArray);
SAFE::DeleteArray($.IndexArray);
}
}
//---------------------------------------------------------------------------------------------
// FUNCTIONS
//---------------------------------------------------------------------------------------------
void Init()
{
$.EmptyArray=0;
$.Array=0;
$.ArraySize=0;
$.ArrayCount=0;
$.FreeArray=0;
$.FreeArraySize=0;
$.FreeArrayCount=0;
$.IndexArray=0;
$.IndexArrayFlag=false;
}
//---------------------------------------------------------------------------------------------
int Add(T object)
{
int index=GetIndex();
//Not Empty
$.EmptyArray[index]=false;
//Move Object To Array
$.Array[index]=object;
//Index Array Clear
$.IndexArrayFlag=false;
return index;
}
//---------------------------------------------------------------------------------------------
void Remove(int index)
{
if($.EmptyArray[index] == false)
{
//Remove From Array
$.EmptyArray[index]=true;
//Index Array Clear
$.IndexArrayFlag=false;

if ($.FreeArrayCount == $.FreeArraySize)
{
//Increment Free Array
$.FreeArraySize = ($.FreeArraySize << 1) + 1;
int* tempFreeArray = new int[$.FreeArraySize];
for(int i=0;i < $.FreeArrayCount;i++) tempFreeArray[i] = $.FreeArray[i];
SAFE::DeleteArray($.FreeArray);
$.FreeArray = tempFreeArray;
}
//Add Index To FreeArray
$.FreeArray[$.FreeArrayCount++]=index;
}
}
//---------------------------------------------------------------------------------------------
void RemoveAll()
{
SAFE::DeleteArray($.EmptyArray);
SAFE::DeleteArray($.Array);
SAFE::DeleteArray($.FreeArray);
SAFE::DeleteArray($.IndexArray);
Init();
}
//---------------------------------------------------------------------------------------------
int GetIndex()
{
if($.ArrayCount < $.ArraySize)
{
//Get Index From Array
return $.ArrayCount++;
}
else
{
if($.FreeArrayCount > 0)
{
//Get Index From Free Array
return $.FreeArray[--$.FreeArrayCount];
}
else
{
//Increment Array
$.ArraySize=($.ArraySize << 1) + 1;
bool* emptyArrayTemp=new bool[$.ArraySize];
T* arrayTemp=new T[$.ArraySize];
for(int i=0;i<$.ArrayCount;i++)
{
arrayTemp[i]=$.Array[i];
emptyArrayTemp[i]=$.EmptyArray[i];
}
SAFE::DeleteArray($.EmptyArray);
SAFE::DeleteArray($.Array);
$.EmptyArray=emptyArrayTemp;
$.Array=arrayTemp;
return $.ArrayCount++;
}
}
return BASE::Error("ERROR: List DataStructure don't get Index");
}
//---------------------------------------------------------------------------------------------
T& Get(int i) { return $.Array[i]; }
//---------------------------------------------------------------------------------------------
int GetCount()
{
//Create Array from List
int count=$.ArrayCount - $.FreeArrayCount;
if ($.IndexArrayFlag == false)
{
SAFE::DeleteArray($.IndexArray);

if(count > 0)
{
$.IndexArray=new int[count];

int c=0;
for(int i=0;i<$.ArrayCount;i++)
{
if ($.EmptyArray[i] == false) $.IndexArray[c++]=i;
}
$.IndexArrayFlag=true;
}
}
return count;
}
//---------------------------------------------------------------------------------------------
T& operator[](int i) { return $.Array[$.IndexArray[i]]; }
//---------------------------------------------------------------------------------------------
void Foreach(function<void (T)> f )
{
for(int i=0;i < GetCount();i++)
{
f($.Array[$.IndexArray[i]]);
}
}
//---------------------------------------------------------------------------------------------
};
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////
   
Pretender - Törzstag | 2498 hsz       Online status #189730   2012.12.24 12:04 GMT+1 óra  
Kód:
{ 1, 2, 3, 4, 5, 6 }

van egy ilyen tömböd. Nosza, vegyük ki az index szerinti 2. elemet (ami a 3-mas), azaz azt szeretném, hogy
Kód:
{ 1, 2, 4, 5, 6 }

legyen a tömb. Egy kivétel a tömb elejéről, esetenként hatalmas mennyiségű memcpy-val jár.

   
versio - Tag | 663 hsz       Online status #189729   2012.12.24 11:03 GMT+1 óra  
Pretender:

tomb piramissal nem kell masolni , ez egy olyan megoldas amikor exponencialisan novekedo meretu tomboket hozol letre, 1,2,4,8 ,16 ,32,.... es egy elemet a tomb sorszamaval, es a tombon beluli indexevel irhatsz le ,
viszont nem szuksegszeru a hasznalata , mivel az exponencialisan novekedo tomboket csak parszor kell atmasolni, hamar felporognek a szukseges meretre , es egy ido utan mar nincs szukseg masolasra, mindket megoldas egyetlen negativuma a memoria pazarlas , persze erre is van megoldas , ha beleepitjuk az automatikus meret csokkentest is
   
Pretender - Törzstag | 2498 hsz       Online status #189728   2012.12.24 10:47 GMT+1 óra  
Te meg talán nem számolod bele az újraallokálásokat és másolásokat

   
versio - Tag | 663 hsz       Online status #189726   2012.12.24 10:19 GMT+1 óra  
Pretender: ha szamszerusiteni akarnam akkor kb ezerszer gyorsabb a tombos megoldas, a kulonbseg abbol ered hogy talan nem szamolod bele az oprendszer memoria managerenek a meghivasat , ami brutalis sokba kerul

Ezt a hozzászólást versio módosította (2012.12.24 10:30 GMT+1 óra, ---)
   
Pretender - Törzstag | 2498 hsz       Online status #189723   2012.12.24 09:38 GMT+1 óra  
A lista egy nagyon jó dolog, mégpedig azért, mert egy elem berakása / kiszedése nagyon gyors. Gondolj csak bele... van egy dinamikus tömböd, abból kiszedni egy elemet úgy, hogy a sorrend ne változzon, nem egy olcsó művelet. Itt viszont csak pár pointer átállításába kerül az egész. Azaz egy tömbre épülő lista sosem lesz gyorsabb. Keresni nyilván költségesebb benne, de arra nem a lista van kitalálva.
Ráadásul egy tömbbe való elembeszúrás egy idő után elég költséges tud lenni, mert ha eléred az elemszámmal a méretet, akkor egy új tömböt kell allokálni, és az addigi tartalmat belemásolni az új tömbbe.

   
Geri - Törzstag | 2189 hsz       Online status #189721   2012.12.24 03:04 GMT+1 óra  
pretender: szerintem listát csak akkor szabad használni, ha nagyon muszáj
végszűkség esetén

   
versio - Tag | 663 hsz       Online status #189714   2012.12.23 21:03 GMT+1 óra  
Pretender: csinalsz egy olyan listat ami eleve tombre epul , sokkal gyorsaab eleve , mint egy a memoriaban szerteszet szort lista

Ezt a hozzászólást versio módosította (2012.12.24 04:11 GMT+1 óra, ---)
   
Joga - Törzstag | 1791 hsz       Online status #189707   2012.12.23 19:34 GMT+1 óra  
nincs
(ಠ ›ಠ) Stewie!

   
Pretender - Törzstag | 2498 hsz       Online status #189705   2012.12.23 19:33 GMT+1 óra  
Ha van egy kétirányú, fejelemes, ciklikus láncolt listám, akkor abból hogy lehet a leggyorsabb módon tömböt gyártani? Az std::vector-nál ugye működött a
T* arr = &vec[0];
mert az a háttérben csak egy sima dinamikus array volt. Nekem a lista ugye node-okból áll, így ilyet nem mondhatok. Nyilván a triviális megoldás az, hogy leallokálok egy megfelelő méretű tömböt, és egyesével feltöltöm... nincs valami elegánsabb és gyorsabb megoldás?

   
HomeGnome - Szerkesztő | 2919 hsz       Online status #189693   2012.12.23 08:36 GMT+1 óra  
Kéretik nem flamelni, hagyjátok meg ezt a topicot a Matematikának!



Peace!

Klikk, a JF.hu bulvárlap.
Klikk #6 WIP: 30% (Kuz, sade, ramoryan...)
   
versio - Tag | 663 hsz       Online status #189691   2012.12.22 22:31 GMT+1 óra  
LugaidVandroiy: nem gondolod hogy unalmas mar kisse a folyamatos ekezesed ? , inkabb szolj hozza a belinkelt pdf-hez ha tudsz , mert ugye szemelyeskedni minden balfasz tud
   
LugaidVandroiy - Törzstag | 504 hsz       Online status #189690   2012.12.22 22:13 GMT+1 óra  
Azért nem idézett pontos számokat, mert te is csak össze-vissza dobálózól velük. Nem feladata kibogarászni az állított dolgaid közül egyikünknek sem, hogy melyik a kisebb hazugság.

   
versio - Tag | 663 hsz       Online status #189689   2012.12.22 21:40 GMT+1 óra  
bolyzsolt: azert nem a pontos szamokat idezted , mert felsz hogy beteljesulnek ,ugye ?
   
bolyzsolt - Törzstag | 607 hsz       Online status #189688   2012.12.22 21:24 GMT+1 óra  
Idézet
ddbwo :
"10-szeres sebesseg"
Nem akarok ünneprontó lenni, de:

- az első grafikon (figure 2) tesztje alapján a leglassabbhoz mérten kb 2-szeres, az átlaghoz képest elenyésző a különbség

- a második grafikon (figure 3) tesztje alapján a különbség a többihez képest kb 3.7-szeres. Ami nem rossz, de mégsem tízszeres.


Semmi gond, versio egyszerűen csak szereti a kerek és egyben teljességgel irreális számokat 10 millió tablet, 500 millió eladott Windows 8 2020-ra, 2 milliárd kirenderelt polygon egy 4000*2000-es kijelzőn, 5 millió játék a storeban, stb. stb.

   
versio - Tag | 663 hsz       Online status #189687   2012.12.22 21:17 GMT+1 óra  
egy intervallumszamitogeppel barmikor, mivel ott egy lepes es megvan az eredmeny
   
ddbwo - Tag | 1625 hsz       Online status #189686   2012.12.22 21:14 GMT+1 óra  
Válaszokat e-mail-ben várunk "sity-suty" jeligére.

--- csak pontosítottam a grafikonról leolvasható adatokat.
A Half-Life 2: Deathmatch promóció megszűnt! [B¤°
Kezdetben volék az üresség. Ám akkor a Struktúrfüggöny megteremté az Urat.
DrunkenDragon* Blackwolf
   
Pretender - Törzstag | 2498 hsz       Online status #189685   2012.12.22 21:10 GMT+1 óra  
de ez hashmap... megnézném, hogy egy nem rendezett bináris fában hogyan keresel logn-nél gyorsabban

   
ddbwo - Tag | 1625 hsz       Online status #189684   2012.12.22 21:00 GMT+1 óra  
"10-szeres sebesseg"
Nem akarok ünneprontó lenni, de:

- az első grafikon (figure 2) tesztje alapján a leglassabbhoz mérten kb 2-szeres, az átlaghoz képest elenyésző a különbség

- a második grafikon (figure 3) tesztje alapján a különbség a többihez képest kb 3.7-szeres. Ami nem rossz, de mégsem tízszeres.
A Half-Life 2: Deathmatch promóció megszűnt! [B¤°
Kezdetben volék az üresség. Ám akkor a Struktúrfüggöny megteremté az Urat.
DrunkenDragon* Blackwolf
   
versio - Tag | 663 hsz       Online status #189680   2012.12.22 17:25 GMT+1 óra  
a hash tabla gyorsabb tud lenni mint a logaritmikus kereses, ha talal az ember jo kulcsot hozza, pl genetikus algoritmussal

http://www.cs.bham.ac.uk/~wbl/biblio/gecco2006/docs/p1861.pdf

es nem kell rendezni..., ez a kulonbseg az iskolaban tanult es az amator tudas kozott , 10-szeres sebesseg
   
Frissebbek | Korábbi postok
[1] > 2 < [3] [4] [5] [6] [7] [8] [9] [10] [15] [20] [21]