4. Insert Methode für Array

Insert Methode für Array

  • L

    Hallo Community,

    Ich bin neu. Jetzt nicht nur hier im Forum, sondern auch an C. Ich habe Erfahrung mit Java (ca. 6 Jahre), Ruby ( 1/2 Jahr), JS (1/2 Jahr) und bin jetzt eben ein wenig an C geraten.
    Meine Aufgabe/Idee:
    Im Moment setzte ich bei mir Postgres als Datenbank-Server ein. In Ruby habe ich mir ein wenig Code gebastelt, der ein bewertetes Interval in bereits vorhandene Intervalle einordnet und evtl. betroffene Intervalle neu bewertet.
    Beispiel:

    # 3 Intervalle: [1,3],[3,7],[7,8]
intervals = [1,3,7,8]
# Gewichte der Intervalle
# d.h. w([1,3]) = 2,  w([1,3]) = 0,  w([1,3]) = 3
weights = [2,0,3]
# neues interval
new_interval = [1,6]
# neues gewicht
new_weight = 2
# neues interval einfügen
# Ergebnis: intervals = [1,3,6,7,8], weights = [4,2,0,3]; 
intervals,weights = insert_interval(intervals,weights, new_interval, new_weight)

    Dieser Teil ist nicht rechen intensiv und dürfte in O(log n) laufen (Nagelt mich nicht fest, bins jetzt nicht ganz durchgegangen). Allerdings gibt es nach diesem Teil auch noch eine weitere Berechnung die mit der exponential funktion herumspielt und DIE ist rechenintenseiv. Kurzum, ich habe meinen Code in die Datenbank verlagert. Zuerst mit der integrierten Skriptsprache plpgsql (http://www.postgresql.org/docs/8.4/static/plpgsql.html). Das war leider nicht so schnell wie erhofft. Nun probiere ich den Code in C zu übersetzen und in postgres entsprechende Funktionen aufzurufen.

    Tja... in Ruby gibt es die Methode

    Array.insert(pos,element)

    die das übergebene Element vor dem index pos einfügt. In C gibt es die nicht. Also dachte ich mir: Die bastle ich mir. So lange nach einer Lösung habe ich schon lange nicht mehr gesucht. Ich habe ein wenig Testcode geschrieben, denn Ihr euch gerne ansehen und auch mal kompilieren könnt.

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>

#ifdef __cplusplus
#error No C-Compiler
#endif

typedef struct {
    // Size of the underlying borders array
    int borders_size;
    // The borders array
    double *interval_borders;
} result_type;

/*
 * Helper
 */
void print_res_type(result_type *t, char when[]) {
    int size = t->borders_size;
    int i;
    printf(when);
    printf("borders_size: %d \n", size); //t->borders_size);
    for (i = 0; i < size; i++) {
        printf("interval_border: %e \n", t->interval_borders[i]);
    }
}

void insert(result_type *res, int pos, double val) {
    // Range check
    if (pos > res->borders_size - 1) return;
    // Rellocate interval_borders; no NULL-Check
    res->interval_borders = (double *) realloc(res->interval_borders, ((++res->borders_size) * sizeof (double)));
    // Shift every entry after pos one to the right and set pos entry to val
    memmove(res->interval_borders + 1 + pos, res->interval_borders + pos, (res->borders_size - pos) * sizeof (double));
    *(res->interval_borders + pos) = val;
}

/*
 * Main
 */
int main(void) {
    result_type *t;
    int i;
    // init arrays
    double arr_b[3] = {10, 20, 30};
    // Allocate corresponding memory
    double *interval_b = (double *) malloc(sizeof (arr_b));
    // Copy arrs into memory
    interval_b = memmove(interval_b, arr_b, sizeof (arr_b));
    if (interval_b == NULL) {
        return EXIT_FAILURE;
    }
    // Alloc memory for struct
    t = (result_type *) malloc(sizeof (result_type));
    t->borders_size = sizeof (arr_b) / sizeof (double);
    t->interval_borders = interval_b;
    printf("Adress of t: %d \n", &t);
    print_res_type(t, "before insert \n");
    // First call is fine
    insert(t, 2, 2);
    // Failure ?
    insert(t, 0, 2);
    print_res_type(t, "after insert \n");

    return EXIT_SUCCESS;
}

    Ich nutze MinGW GNU gcc 4.5.1 als Compiler und habe Windows 7 x64. Das Ganze soll später auf ner Ubuntu-Kiste (Server 10.10 x64) laufen. Als IDE nutze ich NetBeans. Als Debugger nutze ich gdb.

    Mein Fehler:
    * gdb spuckt mir ein SIGTRAP während dem zweiten Schleifendurchlauf aus. Ich konnte den Fehler bis zum realloc in der Funktion insert nachvollziehen.

    Was habe ich bis jetzt getan:
    * In einer ersten Version habe ich wohl die C-Kuh geschlachtet und einfach den Pointer weiter nach rechts verschoben um an eine neue "freie" Speicherstelle zu gelangen. Tja, das war ein Griff ins Klo.
    * In meiner zweiten Version habe ich im insert mit malloc 3 Speicherblöcke reserviert: first_part, second_part und result. first_part hatte die Größe bis eins vor der gewünschten Position +1 und second_part die Restgröße. An first_part habe ich den neuen Wert angehängt und dann alles in result vereinigt. Ebenfalls SIGTRAP während der Speicherallokierung.
    * Herausgefunden, dass automatisch allokierter Speicher nicht "gefreet" werden kann.
    * Auf Pointer umgeschrieben
    * Verzweifelt

    Was habe ich bei Google gefunden:
    * http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_3.html#SEC18
    * Wiki / StackOverflow etc.

    Ich bin für jede Antwort dankbar.

    Gruß,
    Listener

    0

  • Tja, C ist halt kein Ruby. Hat aber auch nicht dessen Anspruch. Verlangt mehr Mitdenken vom Programmierer/Entwickler. Belohnt mit schlankem, portablen Code und Performanz.
    Stelle erstmal sicher, dass du überhaupt C benutzt und nicht C++:

    #ifdef __cplusplus
#error ich mache was falsch und benutzt einen C++ Compiler zum compilieren von C Code
#endif

    Arrays in C sind 0 basiert, d.h. dein "pos" sollte entsprechend vorgegeben werden.
    malloc Casts sind Schrott, Variablendefinitionen gehören an den Beginn eines Codeblocks '{}' sonst verzichtest du unnötig auf Portabilität, Arrays kann man nicht "resizen", verwende memmove statt memcpy, verwende ein typedef für dein struct (es sei denn, du bist masochistisch veranlagt), ... u.v.a.

    0
  • L

    Habe deine Änderungsvorschläge in den Code eingefügt. Wieso sind malloc casts Schrott ? Verlangt ANSI-C nicht sogar danach ? Habe den Fehler etwas besser hervorgehoben. Beim zweiten Aufruf der Funktion insert geht es nicht weiter.

    Mir ist klar, dass man die Größe des Arrays nicht ändern kann. Deswegen schreibe ich doch gerade diese Funktion um eine ähnliche Funktionalität zu haben.

    Es muss doch an Bedingungen liegen die sich zwischen dem 1. Aufruf und 2. Aufruf der Funktion ändern. Oder ?

    0
  • C
    Mod

    listener schrieb:

    Verlangt ANSI-C nicht sogar danach ?

    Casts sind notwendig in C++, weil dort void* nicht implizit in andere Objektzeiger konvertiert werden kann.
    Nebenbei:

    sizeof (arr_b)

    ist schön,

    sizeof (double)

    ist es nicht. Du kannst und solltest auch an dieser Stelle einen Ausdruck setzen. z.B.

    t = malloc(sizeof (*t));
t->borders_size = sizeof (arr_b) / sizeof (*arr_b);

    Das macht die Sache erheblich wartungsfreundlicher.

    void insert(result_type *res, int pos, double val) {
    // Range check
    if (pos > res->borders_size - 1) return;
    // Rellocate interval_borders; no NULL-Check
    res->interval_borders = (double *) realloc(res->interval_borders, ((++res->borders_size) * sizeof (double)));
    // Shift every entry after pos one to the right and set pos entry to val
    memmove(res->interval_borders + 1 + pos, res->interval_borders + pos, (res->borders_size - pos) * sizeof (double));
    *(res->interval_borders + pos) = val;
}

    pos soll hier offenbar auf das Element zeigen, vor dem eingefügt werden soll. Nun gibt für ein Array mit N Elementen aber N+1 Einfügestellen. Denn auch nach dem letzten Element könnt man einfügen wollen (d.h. vor dem Element, das dem letzten folgt). Mithin wäre pos == res->borders_size eigentlich noch ein zulässiger Wert.
    Das memmove kopiert ein Element zuviel, weil du borders_size zu früh inkrementierst. Das führt dann möglicherweise zum Absturz.

    void insert(result_type *res, int pos, double val) {
    if (pos > res->borders_size)
        return;
    result_type new_res = {
        .borders_size = res->borders_size,
        .interval_borders = realloc(res->interval_borders, (res->borders_size + 1) * sizeof *res->interval_borders)
    };
    if ( new_res.interval_borders == NULL )
        return;
    if ( pos < new_res.borders_size ) // könnte man auch weglassen, da new_res.borders_size - pos == 0
        memmove(new_res.borders_size + pos + 1, new_res.borders_size + pos, (new_res.borders_size - pos) * sizeof *new_res.interval_borders);
    new_res.interval_borders[pos] = val;
    ++new_res.borders_size;
// fertig
    *res = new_res;
}

    So geschrieben können Typ und Reihenfolge der Elemente von result_type geändert werden, ohne das die Funktion angepasst werden müsste.

    0
  • L

    Danke, der Inkrement kam wirklich eins zu früh. Und auch Danke für Tipps zum schön schreiben ;).

    0
Anmelden zum Antworten