C vs dinamikus méretű tömb

C/C++

Üdv!

Van egy rövidke kérdésem: hogyan lehet C-ben dinamikus méretű tömböt definiálni? 

int valami_fgv(){
    static int[] dt; // ennek itt dinamikusnak kell lennie
    if(valami_feltetel_teljesul==1){
        dt[]=valami_szam; // itt új elemet kap a tömb
        return 1;
    }else return 0;
}

A dt tömb elemszámát nem lehet előre megjósolni, főleg nem a maximumát. Tudnátok segíteni?

  • 5991 megtekintés

Attol fugg,

Az eddigiekbol nem derul ki, hogyan lesz az adatstruktura hasznalva.
Ha cimezni akarja: struktura 5.dik, 17.dik stb eleme, akkor jobb a tomb. Ha a vegere
akar pakolni elemeket meg onnan kiszedni jobb a lancolt lista.

==
`Have some wine,' the March Hare said in an encouraging tone.
Alice looked all round the table, but there was nothing on it but tea.

ilyen kisméretű objektumnál tényleg elég vad dolog listát használni, egyszerűen túl sok plusz memória kell hozzá; az c++-os std::deque viszont elég jó, gyors is, kevés plusz konstruktorhívás van (nem úgy mint a vectornál), ha sok push_backet akarsz, és közben O(1) alatt elérni az N. elemet, akkor a legjobb.

[off]
Nem az objektum meretetol fugg, hogy mit kell hasznalni, hanem attol, hogy milyen muveleteket akarunk rajta vegrehajtani.
[flame]
jah, ha a std::deque kevesebb memoriat eszik mint egy c-ben irt lista (vagy barmi..) ..
[/flame]
[/off]
==
`Have some wine,' the March Hare said in an encouraging tone.
Alice looked all round the table, but there was nothing on it but tea.

( gthomas | 2007. 04. 21., szo – 19:18 )


#include <malloc.h>

int dt[]; //nem lehet static...
dt = (int *)malloc(sizeof(int)*amennyi_kell);

for (i=0; i<amennyi_kell; i++) {
  dt[i] = i;
}

( kalebris | 2007. 04. 21., szo – 19:17 )

A tomb definicional fogva statikus.
De mivel a c-ben a mutato es a tomb atjarhato ezert a a kovetkezo mukodik:

int valami_fgv(){
int *dt= (int*)malloc(16*sizeof(int));
dt[0]=126;
}

Szóval akkor így tudok elemet hozzáadni, hogy: 

*tmp_array=(int*)malloc(16*sizeof(int));
tmp_array=dt;
*dt=(int*)malloc(16*sizeof(int)+1);
dt=tmp_array;
dt[sizeof(df)-1]=uj_elem;

---------
WARNING: Linux requires you to type! After rebooted to Windows, you can safely unplug your keyboard.
szerény blogom

"A gond ott van, hogy még csak megközelítőleg sincs fogalmam, hogy mekkora lehet ez a tömb."

Egyszer kellett ilyet csinálnom. Egy kis matatás volt, aminek
az ötletét leírom. (A kód ez alapján könnyű.)

Egy kis struct-ban van egy mutatóm az aktuális tömbelemekre meg egy
egész, mely az aktuális lefoglalt méretet tárolja, és egy másik
egész, ami a "drabosságot" méri.

Nem közvetlen tömbelemhivatkozásokkal írok-olvasok hanem kis rutinokkal
(ha a sebesség fontos, akkor inline-olni lehet őket).

Az író rutin ellenőrzi, hogy a már legoflalt tartományban vagyok-e.
Ha igen, minden ok, ha nem, realloc-cal megnövelem a lefoglalt
méretet, úgy, hogy az új méret mindenképp a "darabosság" egész számú
többszöröse legyen.

Így pl. ha épp túllépem az eddigi méretet, hívok egy realloc-ot,
de az egyből "darabosság"-nyi elemnek is helyet foglal. Így a
költséges realloc hívásra ritkán kerül sor. Alkalmazástól függően
lehet a "darabosság"-ot hangolgatni.

Nekem ez jól működött. Biztos van valami jobb megoldás is.

Ja, és ha tudod, hogy olyan elemre hivatkozol, ami már benne
van, akkor a gyors direkt tömbhivatkozást is lehet használni!
De ezt biztosra kell tudni, oda kell figyelni. Csak az esetlegesen
túlíró művelekhez kell az ellenőrizgetős rutint hívni.

hat legjobb esetben is
*tmp_array=(int*)malloc(16*sizeof(int));
tmp_array=dt;
*dt=(int*)malloc((16+1)*sizeof(int));
dt=tmp_array;
dt[regi-elemszam-1]=uj_elem;

a siezof(df) az viszadja majd a pointer meretet de nem a tomb meretet (nekem pl. 4)

de leginkabb
*tmp_array=realloc(dt,x+sizeof(int));
if (tmp_array){
dt=tmp_array;
dt[x-1]=uj_elem;
}

*tmp_array=(int*)malloc(16*sizeof(int));
tmp_array=dt;
*dt=(int*)malloc((16+1)*sizeof(int));
dt=tmp_array;
dt[regi-elemszam-1]=uj_elem;

Lefoglalod a tmp_array-nak a memória egy részét
következőnek már a dt által mutatott területre hivatkozol a tmp_array változóval,
majd lefoglalsz a dt-nek is +1 int-nyi helyet,
aztán a dt-nek értéklül adod a tmp_array értékét, vagyis a dt ugyanarra fog hivatkozni, amelyre a tmp_array

Összességében azt követted el, hogy kétszer lefoglaltál memóriat (16, ill. 17 int-nyi területet), majd pedig a dt visszakapta az eredeti értékét. A lefoglalt memóriára nem tudsz hivatkozni, sem felszabadítani: memory leak.

WTf????

az elso pedaban a
*dt=(int*)malloc((16+1)*sizeof(int)); vs *dt=(int*)malloc((16*sizeof(int)+1);
-re szerettem volna ramutatni.

A veget viszont tenyleg elneztem, bocsanat. Nem gondolkoztam csak masoltam. Ez elmeletben segfault lesz.

A masodik pelda viszont jo kellene, hogy legyen. Kerlek javits ki ha tevedek.

*tmp_array=realloc(dt,x+sizeof(int));
if (tmp_array){
dt=tmp_array;
dt[x-1]=uj_elem;
}

ez is hibás, de csak apró elírás:
dt[x] = uj_elem, mert a végére kell hozzáfűzni. Eredetileg nem volt x. elem, most van.

A koncepció viszont nagyon rossz (eredeti is): ezt úgy szokták csinálni, hogy mindig 2x olyan hosszú lesz a lefoglalt terület, mint eredetileg, és így nem kell minden beszúrásnál újra lefoglalni a memóriaterületet. Az STL pl. ezt a megoldást követi...

*tmp_array=realloc(dt,x+sizeof(int));

sorbol egy szo hianyzik es van benne egy eliras is. Helyesen:

int *tmp_array=realloc(dt,x*sizeof(int));

lenne. Tehat x a mar megnovelt elemszamot akarta jelenteni es nem az elozo tomb meretet. Tehat tmp_array[x-1] utolso eleme a tombnek.

Apropo, hogy lehet megnezni, hogy eppen aktualisan mennyi memoriaterulet van lefoglalva mondjuk a tmp_array szamara?

( bocs | 2007. 04. 21., szo – 20:27 )

milyen egyszerű lenne az életed, ha c++ -t használnál: 


#include <vector>

int fgv(vector<int> * tomb)
{
  if( feltetel ) 
  {
     tomb->push_back(szam);
     return 1;
  }

  return 0;
}

És mennzivel egyszerűbb, ha Javát...

List myList=new ArrayList();
myList.add(1);
myList.add(2);
...
myList.add(20000);

Akármeddig simán működik. És ordó nem foglal több helyet, mintha előre tudnád, hogy mennyit. Ordó nem is dolgozik többet.
Kár, hogy csak ordó :-). De ez egy másik történet...

A java jó lenne (meg a C++ is), csak matematikai számítások esetén fele olyan lassú, mint a C.
Morzeltől kaptam segítséget MSN-en a malloc()-hoz. Írok néhány tesztprogramot, majd megvalósítom, amit kitaláltam. Köszi a segítséget!

---------
WARNING: Linux requires you to type! After rebooted to Windows, you can safely unplug your keyboard.
szerény blogom

Prímszámok számolása. A java és a C++ programok _jóval_ lassabbak voltak (fele lassú nem, de ha jól emlékszem, ~20% körül volt a differencia sebességben; régen csináltam, de arra emlékszem, hogy jóval lassabb volt), mint a C-ben írt példaprogram.

---------
WARNING: Linux requires you to type! After rebooted to Windows, you can safely unplug your keyboard.
szerény blogom

A program sebessége kis mértékben függ a programozási nyelvtől. Nagyobb mértékben a programozó tudásától. Az tény, hogy C-ben könnyű gyors programot írni, hiszen egyszerű nyelv. Én láttam már java-ban ugyanarra a problémára megoldáskeresőt úgy, hogy előszőr 45 mp-ig futott, utána meg 0.3 mp-ig és csak két sor különbség volt a kettő között, nomeg az, hogy aki mutatta, ért a java nyelvhez, és tudja, hogy milyen lehetőségek vannak benne. Általában az ember minnél jobban ismeri az általa használt nyelvet, illetve minnél jobban ért a kód, ill. az algoritmus optimalizálásához, annál gyorsabb programot tud írni.

Morzel

Ha ennyire fontos a sebesség, és gcc-t használsz, talán
érdemes megemlíteni, hogy a "-fprefetch-loop-arrays"
fordítási opció sokat tud gyorsítani, ha a program
sokszor nyálaz végig tömböket és ha p4-es vagy athlon-xp
procid van. (Persze, be kell kapcsolani az adott proci
utasításkészletének használatát.)

No meg az "-finline-functions" is jól dolgozik bizonyos
esetekben.

Bocs, ha ismerted volna ezeket. (A -fprefecth-loop-arrays
számomra sokáig ismeretlen volt. Pedig csak ennek a használata
az én kódjaimban 10-20%-os gyorsulásra vezetett.)

Azért itt is érdemes megbecsülni, hogy mennyi elemre kell számítani, mivel az ArrayList egy egyszerű tömbbel megvalósított lista implementáció; ami, ha betelik új nagyobb méretű tömböt hoz létre, majd átmásolja a meglévő elemeket. Konstruktorában lehet becslést adni.

Ha ennyire nem tudni a várható méretet, akkor szerintem inkább LinkedList, viszont annak az elérési sebessége lassabb.

Szerk.: Mellesleg szerintem is az alkalmazott algoritmus sebessége számít legjobban, nem az adott nyelv.

Az alkalmazott algoritmus pedig az alkalmazott adatszerkezeteknél kezdődik. Tehát hogy tömb vagy láncolt lista az komoly tervezői döntés.
Amúgy mire kell a nagy sebesség? Vegyél kétmagos processzort és párhuzamosíts, vagy csak hajtsd ki a processzort kicsit. Imho nem érdemes optimalizálni, amig ott tartunk, hogy hogy tudunk dinamikus méretű tömböt csinálni.

( pts | 2007. 04. 23., h – 10:02 )

A hozzászólásokban elhangzott, realloc-ot használó megoldások mindig 1-gyel növelik a lefoglalt terület méretét, ami lassúúúúúúúú, mivel ha 1024 elemet kell lefoglalni, akkor 1024 db realloc lesz, és ha nincs szerencsénk, akkor minden realloc lemásolja az egész tömböt. Az alábbi megoldás 1024 hozzáfűzés esetén csak 10 db reallocot hív (O(log n)), és egy beszúrás amortizált költsége is csak O(1).

Az alábbiakat jegyezzük fel: p (kezdőcím), len (hány elem van a tömbben), alloced (hány elem számára foglaltunk helyet a tömbben).

A beszúrás:

if (len==alloced) p=realloc(p, (alloced<<=1)*sizeof p[0]);
p[len++]=uj_ertek;