Ευρεση αριθμού σε πινάκα

[albNik]

Έχουμε ένα πινάκα με Ν αριθμούς όπου όλοι οι αριθμοί υπάρχουν 2 φορές εκτός από έναν.

πχ. { 1, 2, 100, 1, 3, 2, 3}

 

Βρείτε τον μοναδικό αριθμό με τον ποιο γρήγορο τρόπο.

 

*Δεν είναι εργασία.

[Apoll]

Εσύ λύση δεν έχεις να προτείνεις; Εμείς θα σου λύσουμε το πρόβλημα;;;;;;

[albNik]

Την ξέρω τη λύση. Θα την πω αν δεν τη βρείτε. 

[defacer]

Obvious no? Αλλά έπρεπε να πεις ρητά πως είναι ακέραιοι.

 

 

 

xor

 

 

[orestis1996]

Έχουμε ένα πινάκα με Ν αριθμούς όπου όλοι οι αριθμοί υπάρχουν 2 φορές εκτός από έναν.

πχ. { 1, 2, 100, 1, 3, 2, 3}

 

Βρείτε τον μοναδικό αριθμό με τον ποιο γρήγορο τρόπο.

 

*Δεν είναι εργασία.

αμα βαλεις  μετρητη το βρισκεις αλλα σιγουρα θα υπαρχει καλυτερη λυση ποιο εξυπνος τροπος

[imitheos]

4 τρόποι μου ήρθαν στο μυαλό. Βάζω απλό κώδικα σε C για όσους διαβάσουν το νήμα.

 

1) Brute-force. Η πιο μπακάλικη και αργή λύση. Δύο nested βρόχοι που ελέγχουν το iοστό στοιχείο με όλα τα παρακάτω.

for (i = 0; i < 7; i++) {
	found = i;
	for (j = i + 1; j < 7; j++) {
		if (arr[i] == arr[j]) {
			found = 0;
			break;
		}
	}
	if (found) break;
}

Χρόνος: O(N^2) ?

 

Ποτέ δεν τα πήγα καλά με το big oh. Μια και υπάρχει το break που θα σταματήσει όταν το βρει θεωρείται n^2 αυτό ?

 

2) Sort και μετά έλεγχος.

qsort(arr, 7, sizeof(int), compar);
for (i = 0; i < 7; i++) {
	if (arr[i] == arr[i + 1]) {
		i++;
	} else {
		found = i;
		break;
	}
}

Εφόσον ο πίνακας είναι ταξινομημένος τότε οι κοινές τιμές θα πρέπει να είναι δίπλα-δίπλα οπότε χρειαζόμαστε ένα απλό βρόχο που ελέγχει διπλανά στοιχεία.

 

Χρόνος: Αν χρησιμοποιήσουμε bubble sort, τότε νομίζω πως η μέση τιμή είναι πάλι O(N^2). Με την qsort νομίζω έχουμε O(NlogN) οπότε πιο γρήγορη μέθοδος από την προηγούμενη.

 

3) Ιστόγραμμα

/* statikos pinakas me tin megaluteri timi logo baremaras */
int hist[101] = { 0 };

for (i = 0; i < 7; i++) {
	hist[arr[i]]++;
}
for (i = 0 ; i < 101; i++) {
	if (hist[i] == 1) {
		printf ("%d\n", i);
		break;
	}
}

Εκτός ότι είναι overkill για την παρούσα άσκηση, έχουμε το πρόβλημα ότι ενώ έχουμε μόλις 7 στοιχεία χρειαζόμαστε να δεσμεύσουμε μνήμη και να προσπελάσουμε 100 στοιχεία λόγω της μεγάλης τιμής. Δεν έχω ιδέα τι Big-Oh πολυπλοκότητα έχουμε

 

4) Xor που είπε και ο defacer.

for (i = 0; i < 7; i++) {
	xor ^= arr[i];
}
printf ("%d\n", xor);

Γνωρίζουμε ότι ένας αριθμός XOR-ed με τον εαυτό του δίνει αποτέλεσμα μηδέν. Έτσι μπορούμε να χρησιμοποιήσουμε αυτό το γεγονός για να εξαλείψουμε τις τιμές που υπάρχουν πολλαπλές φορές.

 

Οπότε έχουμε ένα πάρα πολύ απλό κώδικα με μόνο μία μεταβλητή στην οποία κάνουμε xor το κάθε στοιχείο του πίνακα. Τα διπλά στοιχεία θα αλληλο-αφαιρεθούν και θα μας μείνει το μοναδικό στοιχείο. Εννοείται πως ο κώδικας είναι τόσο απλός επειδή η εκφώνηση μας λέει ότι τα στοιχεία εμφανίζονται 2 και μόνο 2 φορές. Αν δεν ίσχυε αυτό θα είχαμε πιο πολύπλοκο κώδικα με πολλά XOR.

 

Χρόνος: O(N)

[gon1332]

Για το 1:

To break δε μας πειράζει. Υπάρχει περίπτωση να υπάρξει μοναδικός αριθμός στο τέλος, άρα είναι O(N^2). Σε αυτή την περίπτωση πιο μεγάλη σημασία έχει η μέση περίπτωση.

 

Για το 3:

Το 3 έχω την εντύπωση πως εκτελείται σε χρόνο T(N) = 2*Ν, αν ο μοναδικός αριθμός είναι στο τέλος του ιστογράμματος, άρα O(N).

Απροσεξία μου. Δεν είδα πως έχεις 101 το μέγεθος του ιστογράμματος. Τ(Ν) = Ν + value_of_largest_number. Αν θεωρήσουμε σταθερά το value_of_largest_number, τότε O(N) θα έλεγα.

Επεξ/σία 2 Νοεμβρίου 2015 από gon1332

[Aztec]

XOR with threads ? O(n) αλλα καλύτερο execution... δεν ξέρω για μικρά arrays

[gon1332]

XOR with threads ? O(n) αλλα καλύτερο execution... δεν ξέρω για μικρά arrays

XOR με threads αλά prefix sum [1];

[defacer]

1) Brute-force. Η πιο μπακάλικη και αργή λύση. Δύο nested βρόχοι που ελέγχουν το iοστό στοιχείο με όλα τα παρακάτω.

for (i = 0; i < 7; i++) {
	found = i;
	for (j = i + 1; j < 7; j++) {
		if (arr[i] == arr[j]) {
			found = 0;
			break;
		}
	}
	if (found) break;
}

Χρόνος: O(N^2) ?

 

Ποτέ δεν τα πήγα καλά με το big oh. Μια και υπάρχει το break που θα σταματήσει όταν το βρει θεωρείται n^2 αυτό ?

 

Ναι είναι N^2 αλλά θέλει προσοχή όχι για το break (έτσι κι αλλιώς θα πάρεις worst case scenario) αλλά επειδή το inner loop δεν κάνει Ν επαναλήψεις, οπότε αν δεν το μυρίζεσαι από εμπειρία τι γίνεται θέλει μαθηματικά.

 

Εδώ έχεις Ν επαναλήψεις του inner για την πρώτη του outer, Ν-1 για τη δεύτερη κλπ. Συνολικά N + N-1 + ... + 1 το οποίο είναι αριθμητική πρόοδος με άθροισμα Ν(Ν+1)/2 οπότε όντως N^2. Νομίζω κιόλας το έχουμε ξαναδεί αυτό σε άλλο θέμα.

[imitheos]

Edit:

Εδώ έχεις Ν επαναλήψεις του inner για την πρώτη του outer, Ν-1 για τη δεύτερη κλπ. Συνολικά N + N-1 + ... + 1 το οποίο είναι αριθμητική πρόοδος με άθροισμα Ν(Ν+1)/2 οπότε όντως N^2. Νομίζω κιόλας το έχουμε ξαναδεί αυτό σε άλλο θέμα.

Όντως ήταν να το αναφέρω και αυτό ότι ξεκινά από i+1 εκτός από το break αλλά κλασικά το ξέχασα.

 

Μια και δεν γράφτηκε άλλη λύση, παίρνω το θάρρος να γράψω την

 

[άχρηστη (και offtopic) πληροφορία της ημέρας]

 

 

Η μέθοδος "μηδενισμού" με την XOR ήταν μια από τις πιο γνωστές τακτικές βελτιστοποίησης.

 

Προ αμνημονεύτων χρόνων σε DOS δεν υπήρχε python και ruby οπότε μαζί με c και pascal πολύς κόσμος ασχολούταν με assembly ειδικά αν ήθελες να κάνεις κάτι περίεργο ή να τρέχει όσο το δυνατόν πιο γρήγορα.

 

Πολλές φορές λοιπόν στα προγράμματα χρειαζόσουν να μηδενίσεις κάποιο καταχωρητή με πιο συχνή περίπτωση αυτήν του καταχωρητή A (είτε AX δηλαδή ολόκληρο τον 16bitο καταχωρητή είτε AH, AL που ήταν τα high, low bytes αντίστοιχα).

 

Σήμερα θα μιλούσαμε για premature optimization (και ίσως και τότε να ήταν) αλλά τότε ήταν συχνή πρακτική να χρησιμοποιούμε κατά κόρον την xor αντί για ανάθεση τιμής με την mov (και η sub για αφαίρεση χρησιμοποιούταν πιο σπάνια). Αν θυμάμαι καλά, το "mov ax" είναι το opcode B8 οπότε το "θέσε τιμή 0 στον καταχωρητή AX" (mov ax,0) ισοδυναμούσε με "B80000" ενώ το "xor ax,ax" ισοδυναμούσε με "κάτι C0".

 

Εκτός λοιπόν ότι έτσι κέρδιζες ένα byte, η xor ήταν πιο γρήγορη κατά 1-2 κύκλους ρολογιού από την mov οπότε το πρόγραμμα σου έτρεχε πιο γρήγορα. Ήταν φυσικά και λίγο ποζεριά ότι το έκανες με "έξυπνο" τρόπο αλλά είχε και πρακτικό αποτέλεσμα γιατί μιλάμε για 286/386 (νομίζω ο πιο γρήγορος 386 ήταν στα 40MHz και ο 486 το ανέβασε στα 100MHz ) οπότε και λίγοι κύκλοι ακόμη έκαναν διαφορά αν η συνάρτηση εκτελούταν πολλές φορές.

 

 

[/άχρηστη (και offtopic) πληροφορία της ημέρας]

[παπι]

Αν μιλαμε για στατικο πινακα. Τοτε, οτι και να γραψεις (που δουλευει) θα πρεπει να εχει ακριβως το ιδιο αποτελεσμα σε χρονο.

 

Btw απο κανα αφιερωμα στα 200 χρονια του μπουλ το βρηκες;

[Pseudonymo1212]

Αυτό είναι Izi.

 

Αφού σε ενδιαφέρει η αναζήτηση και δεν βάζεις Limits, μου δίνεις τη δυνατότητα να κάνω ότι θέλω με την "προσθήκη".

 

Θα φτιάξω ένα δέντρο με Duplicates (δηλαδή δεν θα έχει μια τιμή int Πχ, αλλά δυναμικό πίνακα) και πολύ απλά, θα τσεκάρω ποιο Node έχει == 1 item.

 

Προσοχή! δεν θα προσπελάσω κανέναν πίνακα στα Nodes. Απλά το Length τους θα πάρω.

 

ΥΓ: Και για να μην καθυστερώ στο να βρίσκω δυναμικά το Length, θα έχω μεταβλητή που θα το κουβαλάει. Η μεταβλητή (TotalItems) θα αρχικοποιηθεί στο Create.

typedef struct MyNodeTag
{
  int *array;
  int totalitems;
}MyNode;

// opote, to dedro mas tha exei 4 nodes. [11,2] [22,2] [33,2] [100,1]
// opote, to dedreo mas tha exei 4 nodes:
// [array(1,1), 2], [array(2,2), 2], [array(3,3), 2], [array(100), 1]
// An to kanoume btree, kai epilexoume san root to [33,2] tote:
//                   [33,2]
//             [11,2]       [100,1]
//                  [22,2]
// Izi Search.

int main()
{
   // Build Tree from { 1, 2, 100, 1, 3, 2, 3 }
   
   // _startTime;
   // Search process (foreach node, check node.totalitems == 1, and not array)
   // _endTime
 
}

ΥΓ: Εφόσον μετράμε μόνο την αναζήτηση και όχι το χτίσιμο αυτού του δέντρου!. Αν θες να μετράμε τα πάντα. Τη **σα.

ΥΓ: 'Η πολύ απλά θα πάω σε Matlab

[defacer]

Ε.... βλέπεις λίγο το δέντρο (pun intended) και χάνεις το δάσος... 

 

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

 

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

 

Γενικά μου φαίνεται φάση "κάθε φορά που οι φοιτητές ιατρικής μαθαίνουν καινούρια πάθηση, ό,τι σύμπτωμα και να δουν βγάζουν διάγνωση την πάθηση που μόλις έμαθαν".

[albNik]

Η ουσια ειναι η ιδιότητες που έχει η πράξη xor

μεταθετική: a^b=b^a

προσεταιριστική: a^b^c=a^(b^c)

επίσης: a^a=0, a^0=a.  

 

1^2^100^1^3^2^3=1^1^2^2^3^3^100=(1^1)^(2^2)^(3^3)^100=0^0^0^100=0^100=100