Κώδικας C για ταξινόμηση απλά συνδεδεμένης λίστας με αλλαγή των pointers

[Evgenios1]

Λάθος κάνεις.

Όχι μόνον η διαγραφή αλλά και η προσθήκη κόμβου σε ένα ballanced tree είναι σχεδόν το ίδιο δύσκολη, δυο σκαλιά πιο κάτω.

Λίγοι ξέρουν να τις κάνουν.

 

Μπααα, το πιο δυσκολο ειναι ο allocator. Κατι που δεν κανει κανενας, με αποτελεσμα ενα δυναμικο array να ειναι καλυτερη λυση παρα ενα δεντρο. Τρελο overhead στη μνημη ρε παιδι μου, βαλε τα 4-8 byte για το "next" βαλε και καμια 20-100 byte απο τη malloc... για ενα struct 20byte μπορει να θες 100%-500% περισσοτερο μνημη...

[thanos713]

Χάθηκα... Το allocation γιατί να είναι δύσκολο; Να σας δείξω λίγο κώδικα γιατί τα έχω μπερδέψει, έχουμε αυτό το declaration:

 

>
struct node
{
   char leksi[20];
   struct node *left;
   struct node *right;
} *root, *neos;

 

και αυτή την συνάρτηση:

 

>
struct node *add_node(struct node *myroot, char data[])
{

    if (myroot == NULL)
    {
        neos = (struct node*) malloc (sizeof(struct node));
        strcpy (neos->leksi, data);
        neos->left = NULL;
        neos->right = NULL;
        myroot = neos;

    }
    else
    {
        if (strcmp (data, myroot->leksi) < 0)
           myroot->left = add_node(myroot->left, data);
        else
           myroot->right = add_node (myroot->right, data);

    }
    return myroot;
}

 

Πού είναι το δύσκολο; Έχω καταλάβει κάτι λάθος;

[V.I.Smirnov]

@thanos713

 

Το δύσκολο και η ουσία σε ένα ballanced tree είναι η προσθήκη και η διαγραφή κόμβου ώστε να παραμένει ballanced.

Όσοι ξέρουν δομές δεδομένων μπορούν να με επιβεβαιώσουν.

Η μνήμη δεν επιβαρύνεται πέραν του φυσιολογικού - δεσμεύεται η απαραίτητη και τίποτε περισσότερο.

Να, όπως βλέπεις κι εσύ δεν είναι πρόβλημα ο allocator, επ' αυτού δεν έχεις καταλάβει λάθος.

Tα υπόλοιπα είναι λόγια ημιμαθών.

 

Σε ότι αφορά την STL, αυτή έχει μια μικρή επιβάρυνση στην ταχύτητα και στην μνήμη διότι είναι γραμμένη γενικά και για να

έχει ασυμπτωτική απόδοση. Το έχουμε ξανασυζητήσει στο παρελθόν αυτό.

Πέραν της STL, εδώ μιλάμε για ιδιοκατασκευές και ειδικά σε αυτές η δέσμευση μνήμης δεν εισάγει σχεδόν καμιά επιβάρυνση

διότι είναι προσαρμοσμένη στο εκάστοτε πρόβλημα αφού γράφουμε την ρουτίνα εμείς.

 

(Το δέντρο σου thano ΔΕΝ είναι ballanced. Να εξηγούμαστε.)

 

-

[MitsakosGR]

Πού είναι το δύσκολο; Έχω καταλάβει κάτι λάθος;

 

Μιλάτε για διαφορετικά πράγματα για αυτό μπερδεύεστε.

Ο V.I.Smirnov μιλάει για Balanced δυαδικά δέντρα που παραμένουν balanced σε ολή την διάρκεια. Ο thanos713 μιλάει για απλά δυαδικά δέντρα που προσθέτεις στοιχεία δεξιά ή αριστερά με βάση την ταξινόμηση αλλά μπορεί (και κατά πάσα πιθανότητα) να μην είναι πλέον balanced.

 

Σε απλό δέντρο είναι σχετικά εύκολο. Σε Balanced (AVL trees) είναι σχετικά πολύπλοκλο (το σχετικά λόγω γνώσεων του καθενός, εγώ μόνο απλά ξέρω )

[Evgenios1]

@thanos713

 

 

Όσοι ξέρουν δομές δεδομένων μπορούν να με επιβεβαιώσουν.

Η μνήμη δεν επιβαρύνεται πέραν του φυσιολογικού - δεσμεύεται η απαραίτητη και τίποτε περισσότερο.

Να, όπως βλέπεις κι εσύ δεν είναι πρόβλημα ο allocator, επ' αυτού δεν έχεις καταλάβει λάθος.

-

Επειδη ειμαι του πειραματος.

elements =100000

element size =30

 

Malloc

>Virtual memory usage:   2929KB
Real memory usage:      9412KB
Memory overhead:        6483KB

vector

>Virtual memory usage:   2929KB
Real memory usage:      4136KB
Memory overhead:        1207KB

 

 

application

 

>#include <string>
#include <iostream>
#include <vector>
//#include <functional>
#include <Windows.h>

#include <Psapi.h>
#pragma comment(lib,"psapi.lib")

using namespace std;

#define MALLOC 1

struct _30{char data[30];};

__inline int GetRealTimeKb(HANDLE proc)
{
PROCESS_MEMORY_COUNTERS meminfo;
GetProcessMemoryInfo(proc,&meminfo,sizeof(meminfo));
return (meminfo.WorkingSetSize/1024);
}

int main(void)
{
HANDLE proc = GetCurrentProcess();
vector<_30> v;
_30 obj;
int applicationMem = GetRealTimeKb(proc);

int szStruct = 30;
int countStruct= 100000;
for(int i=0;i<countStruct;i++)
#if MALLOC
	malloc(szStruct);
#else
    v.push_back(obj);
#endif
int afterMalloc = GetRealTimeKb(proc);
cout<<"Virtual memory usage:\t"<<(szStruct*countStruct)/1024<<"KB"<<endl;
cout<<"Real memory usage:\t"<<(afterMalloc-applicationMem)<<"KB"<<endl;
cout<<"Memory overhead:\t"<<(afterMalloc-applicationMem) - ((szStruct*countStruct)/1024)<<"KB"<<endl;
   return 0;
}

 

[V.I.Smirnov]

Μιλάτε για διαφορετικά πράγματα για αυτό μπερδεύεστε.

Ο V.I.Smirnov μιλάει για Balanced δυαδικά δέντρα που παραμένουν balanced σε ολή την διάρκεια.

Ο thanos713 μιλάει για απλά δυαδικά δέντρα που προσθέτεις στοιχεία δεξιά ή αριστερά με βάση την ταξινόμηση αλλά μπορεί (και κατά πάσα πιθανότητα) να μην είναι πλέον balanced.

 

Σε απλό δέντρο είναι σχετικά εύκολο.

Σε Ballanced (AVL trees) είναι σχετικά πολύπλοκο

(το σχετικά λόγω γνώσεων του καθενός, εγώ μόνο απλά ξέρω )

 

Aκριβώς !! Αν το δέντρο δεν είναι ballanced, εκφυλλίζεται σε λίστα και δεν προσφέρει και πολλά.

 

Ο thanos δεν έχει λόγο να μπερδεύεται και αυτό που έγραψε είναι σωστό.

Ο Evgenios τον μπέρδεψε (προφανώς δεν έχει δοκιμάσει να φτιάξει ballanced tree).

 

Τα ballanced trees είναι ΠΟΛΥ δύσκολο να φτιαχτούν σωστά.

Είχα μελετήσει πριν καιρό red-black trees και splay trees και ξέρω τι εστί.

Επίσης είχα κάνει και μια πλήρη υλοποίηση σε AVL tree (με προσθήκη και διαγραφή κόμβου).

Δεδομένου ότι δεν έχω σπουδάσει πληροφορική μου είναι αρκετά.

Κανένα πρόβλημα μνήμης με το allocation δεν υπάρχει.

Η προσθήκη/διαγραφή κόμβου είναι η δυσκολία και τα σχετικά τους (rotations).

 

 

@Εvgenios

 

Αυτό το διάβασες ή όχι ;

 

Σε ότι αφορά την STL, αυτή έχει μια μικρή επιβάρυνση στην ταχύτητα και στην μνήμη διότι είναι γραμμένη γενικά και για να

έχει ασυμπτωτική απόδοση. Το έχουμε ξανασυζητήσει στο παρελθόν αυτό.

Πέραν της STL, εδώ μιλάμε για ιδιοκατασκευές και ειδικά σε αυτές η δέσμευση μνήμης δεν εισάγει σχεδόν καμιά επιβάρυνση

διότι είναι προσαρμοσμένη στο εκάστοτε πρόβλημα αφού γράφουμε την ρουτίνα εμείς.

 

Προφανώς όχι. Περαιτέρω σχόλια δεν χρειάζονται.

 

-

[Evgenios1]

To vector το εβαλα μονο και μονο επειδη εχει αλλον allocator. Btw αυτο ειναι μονο το overhead της malloc, εαν βαλουμε τα next, prev,id και αλλα τετοια μπερμπιτσιολια... τοτε το overhead παει στο θεο..

 

@nikolaos_ Φτιαξε μια βιβλιοθηκη σε c++ με vector απο πισω, και βγαλε ενα api του στυλ CreateNode, FindNode, DeleteNode,Sort, etc... και δουλεψε το με τη C

[V.I.Smirnov]

 

Ζητώ κώδικα. Ό,τι κώδικα έχω βρει, είναι είτε σε arrays, είτε κάνοντας αλλαγή των τιμών.

Επειδή έχω πολύπλοκα nodes, αυτό δε μπορώ να το εφαρμόσω, πρέπει να ανταλλάξω με ασφάλεια τους pointers.

 

Πάρε το βιβλίο που σου σύστησα και μην παιδεύεσαι άσκοπα. Έχει έτοιμο κώδικα σε αυτό που θέλεις.

Tα μόνα που θα αλλάξεις είναι τα περιεχόμενα των κόμβων και πιθανόν η συνάρτηση που συγκρίνει.

 

Aλλιώς γυρνάς σε C++ και χρησιμοποιείς κάτι έτοιμο από την STL.

 

Kαι εν πάση περιπτώση δεν καταλαβαίνω γιατί ο κόσμος χρησιμοποιεί την C για δομές δεδομένων (και όχι μόνον)

όταν η C++ προσφέρει τόσο πιο πολλές ευκολίες σε όλα.

[thanos713]

Kαι εν πάση περιπτώση δεν καταλαβαίνω γιατί ο κόσμος χρησιμοποιεί την C για δομές δεδομένων (και όχι μόνον)

όταν η C++ προσφέρει τόσο πιο πολλές ευκολίες σε όλα.

Είναι σαν να λες να χρησιμοποιούμε το software του lego mindstorms για ρομποτική... Άμα δεν καταλάβεις τι κρύβετε από πίσω ποιο το νόημα;

[Evgenios1]

Kαι εν πάση περιπτώση δεν καταλαβαίνω γιατί ο κόσμος χρησιμοποιεί την C για δομές δεδομένων (και όχι μόνον)

όταν η C++ προσφέρει τόσο πιο πολλές ευκολίες σε όλα.

 

Ασκηση ειναι... Εγω δε καταλαβαινω γιατι οι ασκησεις στηριζονται στην πολυπλοκοτητα και οχι στη πρακτηκη τις καθε γλωσσας.

[V.I.Smirnov]

Είναι σαν να λες να χρησιμοποιούμε το software του lego mindstorms για ρομποτική... Άμα δεν καταλάβεις τι κρύβετε από πίσω ποιο το νόημα;

 

Δεν είναι το ίδιο φίλε μου.

 

Επί προσωπικού, εγώ μπορεί να χρησιμοποιήσω, αν μου χρειαστούν, έτοιμες λίστες ή δέντρα ή...

αλλά ξέρω πώς δουλεύουν εγγενώς και τι ιδιότητες έχουν.

Από εκεί και πέρα, όταν δεν υπάρχει διδακτικός λόγος ή όταν οι ανάγκες σου καλύπτονται με τα έτοιμα

το να ξαναεφευρίσκεις τον τροχό είναι ανώφελο και άσκοπο.

 

Η C πέραν της χρησιμότητας που έχει σε λίγους συγκεκριμένους τομείς όπου η C++ δεν υποστηρίζεται, είναι εντελώς παρωχημένη.

Για μένα όποιος μαθαίνει C ενώ μπορεί να μάθει C++ κατευθείαν απλώς ξοδεύει άσκοπα τον χρόνο του.

Εξάλλου στις περισσότερες περιπτώσεις αυτό που ενδιαφέρει είναι τελικά γίνει η δουλειά όσο το δυνατόν πιο γρήγορα, εύκολα και καλά.

Εδώ π.χ. η STL παρέχει έτοιμα ένα σωρό μέσα. Η C τι παρέχει ; τίποτε, όλα πρέπει να γίνουν από το μηδέν...

 

offtopic : το παράδειγμα που έφερες με την ρομποτική, είναι εντελώς ατυχές. Ο κόσμος δεν ενδιαφέρεται να μάθει το "από πίσω"

αλλά να δει εύκολα αποτέλεσμα. Αν π.χ. επιχειρήσεις να διαβάσεις πώς λύνεται το κινηματικό πρόβλημα ενός ρομποτικού βαχίονα με δύο μέρη

(το πιο απλό δηλαδή !) μάλλον θα ζοριστείς πολύ. Αντίθετα, παίζουν όλοι με το έτοιμο λογισμικό και νομίζουν ότι αυτό είναι ρομποτική....

 

 

@Εvgenios

 

Για άσκηση δεν διαφωνώ. Είπα "όταν δεν υπάρχει διδακτικός λόγος".

Αλλά και στα πλαίσια κάποιας πρακτικής χρησιμότητας όμως.

 

Και μια που το έφερε η κουβέντα, ξέρει κανείς σας που υπάρχει μια πηγή που να γράφει τις συντακτικές διαφορές μεταξύ C/C++ ;

Έχω βρει κατά καιρούς αλλά τίποτε ολοκληρωμένο. Και είναι κάτι που χρειάζεται, ειδικά αν ξέρεις μόνον C++.

[thanos713]

Δεν είναι το ίδιο φίλε μου.

 

Επί προσωπικού, εγώ μπορεί να χρησιμοποιήσω, αν μου χρειαστούν, έτοιμες λίστες ή δέντρα ή...

αλλά ξέρω πώς δουλεύουν εγγενώς και τι ιδιότητες έχουν.

Μόνος σου το είπες, πώς θα κατανοήσεις πώς δουλεύουν και τι ιδιότητες έχουν άμα δεν ξεκινήσεις από πιο χαμηλό επίπεδο; Όλοι μπορούν να χρησιμοποιούν έτοιμες συναρτήσεις (ότι έχει η STL τέλος πάντων, δεν ξέρω C++) αλλά λίγοι ξέρουν άψογα πώς δουλεύουν και πώς θα αντιμετωπίσουν τυχόντα σφάλματα...

[V.I.Smirnov]

Μόνος σου το είπες, πώς θα κατανοήσεις πώς δουλεύουν και τι ιδιότητες έχουν άμα δεν ξεκινήσεις από πιο χαμηλό επίπεδο; Όλοι μπορούν να χρησιμοποιούν έτοιμες συναρτήσεις (ότι έχει η STL τέλος πάντων, δεν ξέρω C++) αλλά λίγοι ξέρουν άψογα πώς δουλεύουν και πώς θα αντιμετωπίσουν τυχόντα σφάλματα...

 

Είναι σα να μου λες να μάθω παρωχημένα και απαρχαιωμένα πράγματα για να κατανοήσω τα πιο προχωρημένα.

Λάθος. Το χαμηλό επίπεδο υπάρχει και στα σύγχρονα και μάλιστα σε πλαίσια πρακτικής χρησιμότητας.

 

Η C++ αρκεί με το παραπάνω.

Εγώ όταν διάβαζα τις λίστες και τα δέντρα, σε C++ τα διάβαζα.

Πολύ καλύτερα μελετώνται στην C++ παρά στην C, είναι εύλογο γιατί.

Όταν έβλεπα C έφευγα τρέχοντας.

 

Η φιλική μου συμβουλή είναι να μάθεις C++ κατευθείαν. Ούτε καν να ασχοληθείς με την C (πέραν από τις συντακτικές τους διαφορές που ακόμα τις ψάχνω...)

[nikolaos_]

Ανήκει όντως σε μια άσκηση και η μέχρι τώρα υλοποίηση σε C++ (στην πράξη C) έχει γίνει με απλά συνδεδεμένες λίστες. Το να αλλάξω τη δομή σε balanced δέντρα δεν με εξυπηρετεί, άσε που προσθέτει pointers. Γιατί να μην την έκανα τότε διπλά συνδεδεμένη λίστα που έχω βρει σχετικά εύκολα κώδικα;

 

Η ιδέα είναι να ταξινομείς τη μικρή λίστα (3-4 στοιχείων) και να εισέρχεται στη μεγάλη λίστα (των 10000 στοιχείων), στην αρχή της. Τα 10000 nodes προκύπτουν από πολλές συναθροίσεις των 3-4 nodes της μικρής λίστας που αναδημιουργείται συνέχεια.

Αλλά υπάρχουν και περιπτώσεις να αφαιρούνται για λίγο μερικά στοιχεία από τη μεγάλη και να προστίθενται στη μικρή, να γίνεται η ταξινόμησή της και να "κολλάει" ολόκληρη πλέον πίσω.

Υπήρχε και ενδεχόμενο να γίνει ταξινόμηση όλης της λίστας των 10000 (με άλλη διάταξη), αλλά μπορώ να το αποφύγω.

 

Εκεί που έχω κολλήσει είναι ότι δε μπορώ να βρω ούτε ένα insertion sort για μια απλά συνδεδεμένη λίστα και το ψάχνω από το πρωί μόνος.

[dop]

Αν είναι άσκηση ή έρευνα, κάνεις ότι σου ζητάνε (και ακόμα περισσότερα άμα σου αρέσει).

 

Αν είναι επειδή σου κατέβηκε χθες πως θες να το κάνεις, κάνεις ότι νομίζεις.

 

Αν από την άλλη είναι ένα πρόβλημα που χρειάζεται λύση για να συνεχίσεις να κάνεις την δουλειά σου, τότε:

1) ψάχνεις να βρεις αν το έχει το σύστημά σου έτοιμο.

2) ψάχνεις να βρεις αν υπάρχει διαθέσιμο με κατάλληλη άδεια χρήσης.

3) το κάνεις μόνος σου.

 

Αν το κάνεις μόνος σου, πάλι δύο επιλογές:

1) αν δεν είναι στο critical path, τα 2ms που θα κερδίσεις σήμερα με μια εξαιρετικά βελτιστοποιημένη λύση για το πρόβλημά σου θα εξαφανιστούν αύριο.

2) αν είναι στο critical path, προσπαθείς να δώσεις μια όσο το δυνατόν γενική λύση, γράφεις τα τεστ σου και εύχεσαι να μη χρειάζεται να την κάνεις maintain συχνά.

 

Για τον OP, γιατί δεν αποθηκεύεις τους pointers σε ένα απλό array και να καλέσεις την qsort (που είναι στη βιβλιοθήκη της C) με την κατάλληλη function;