Pikkuse kasvu võimaldava adresseeritava massiivi realiseerimine

Question

Võib olla rumal küsimus, aga et hingerahu saada, küsin sellegipoolest. Tegu siis C keelega.

Vaja on töödelda andmemassiivi, mille elemendid on neljabitised ja mida peab olema võimalik lõpust kasvatada. Samuti peab massiiv olema suvalise, lineaarselt adresseeritud (nii absoluutaadressiga kui "jooksva fookuse" suhtes suhtelise aadressiga) elemendi, asukohas kirjutatav ja loetav. üsna palju on vaja puhvris andmelõike ühest asukohast teise tõsta. Teostus peaks olema enam-vähem ühilduv erinevate levinud OS'de jaoks.

Väga mugavalt saaks seda teha failipuhvrit kasutades, aga kas see on ka ressursside kasutamise suhtes otstarbekas?

Teise võimalusena mõtlesin välja viitade massiivi, mille viidad osutavad konstantse pikkusega, dünaamiliselt eraldatud, sümbolimassiividele. Kui massiivi pikkus on kahe aste, siis on elemendi asukoha leidmine arvutuslikult odav. Vaja ainult optimaalne osapuhvri ja viitade massiivi pikkus välja mõelda.

Kumb lähenemisviis võiks õigem olla? Failipuhvri hingeelu eri OS'de all väga ette ei kujuta :(

Answer 1

Kui palju andmeid on? Kui tihti massiiv kasvab? Kas kasvamise käigus peavad olemasolevad väliste osapoolte käes olevad viited massiivi elementidele alles jääma?

Kui vastused on "mitte väga", "mitte eriti", "ei", siis tasuks kaaluda ka kõige standardsemat võimalikku: standardteegi funktsioone malloc() ja realloc().

Kui teine vastus on "mitte eriti tihti" asemel "üsna tihti" või "väga tihti", siis võib mälu juurdevõtmisel teha seda varuga (tavaline strateegia on puhvri suurust iga kord kahekordistada, siis on "raiskamine" alati alla 50%; aga võib ka iga kord näiteks 50% juurde panna, siis on "raiskamine" alati alla 33%).

Kui kolmas vastus on "ei" asemel "jah", siis võib (sõltuvalt väliste osapoolte koostöövalmidusest) kaaluda otse elemente adresseerivate C sisseehitatud viitade asemel paaride (puhvri päise viit + elemendi indeks) kasutamist ja arvutada tegelik elemendi mäluaadress igal pöördumisel päises kirjas oleva puhvri algusaadressi (võib realloc() kasutamisega muutuda) ja elemendi indeksi põhjal.

Umbes midagi sellist (hoiatus: otse brauseris kirjutatud totaalselt testimata kood):

typedef struct {
    unsigned char *base; /* mälu algus */
    size_t size; /* mälu suurus */
    size_t used; /* kasutatud elementide arv */
} dynamic_buffer;

dynamic_buffer *dynamic_buffer_init(size_t init_size) {
    dynamic_buffer *buf = malloc(sizeof(dynamic_buffer));
    buf->base = malloc(init_size);
    buf->size = init_size;
    buf->used = 0;
    return buf;
}

void dynamic_buffer_done(dynamic_buffer *buf) {
    free(buf->base);
    free(buf);
}

void dynamic_buffer_add(dyamic_buffer *buf, unsigned char value) {
    if (buf->used == 2 * buf->size) {
        buf->size *= 2;
        buf->base = realloc(buf->base, buf->size);
    }
    dynamic_buffer_set(buf, buf->used, value);
    ++buf->used;
}

void dynamic_buffer_set(dynamic_buffer *buf, size_t pos, unsigned char value) {
    unsigned char mask = 0x0f;
    value &= mask;
    if (pos & 1 == 0) {
        /* paarisindeksiga elementi hoiame baidi ülemises pooles */
        value <<= 4;
        mask <<= 4;
    }
    pos >>= 1;
    buf->base[pos] &= ~mask; /* kustutame vana väärtuse */
    buf->base[pos] |= value; /* salvestame uue väärtuse */
}

unsigned char dynamic_buffer_get(dynamic_buffer *buf, size_t pos) {
    unsigned char mask = 0x0f;
    unsigned char value = buf->base[pos >> 1];
    if (pos & 1 == 0) {
        /* paarisindeksiga elementi hoiame baidi ülemises pooles */
        value >>= 4;
    }
    return (value & mask);
}

Answer 2

Faili kasutamine on võrdlemisi standardne ja seega lihtne lahendus. Tänapäevased operatsioonisüsteemid (ja ka vanad Unixid) puhverdavad faili sisu üldiselt väga kenasti mälus, kui vaba mälu on. (Ja käituvad mõistlikult ka siis, kui vaba mälu ei ole.)

Kokkuvõttes, proovi kõigepealt lihtsalt lahendada ja kui seejärel tungivat vajadust teisiti lahendada ei ole, siis jätagi nii.

Answer 3

Enamlevinud opsysteemid ei võta malloc(suurarv) peale mitte kogu küsitud mälu reaalselt kasutusele. Reaalset mälu eraldatakse jooksvalt vastaval vajadusele - kirjutamisel allokeeritakse virtuaalmälu vahendusel vastav lehekülg.

Sa jätad täpsustamata kui suur see massiiv sul olla võib ja kas lahendus peab ka 32bitise opsysteemiga töötama. Yle 2 (3) giga ei ole siis massiivi kaudu põhimõtteliselt võimalik.

JUhul kui kõigi nimetatud massiivide maksimaalsete eksemplaride korraga aadressruumi mahtumisega probleemi pole soovitan allokeerida kohe niipalju kui vaja ja lasta opsysteemil teha oma tööd.

Pikkuse kasvu võimaldava adresseeritava massiivi realiseerimine

Jälgi seda küsimust

Pinu tööpakkumised

Sarnased küsimused