Αλγόριθμοι Ταξινόμησης

[vag_ka]

Καλησπέρα μήπως μπορεί να με βοηθήσει κανείς με το εξής πρόβλημα:

Έστω ότι πρέπει να βρω τα κ=1000 πιο ακριβά προιόντα μιας μη ταξινομημένης λίστας με ν=10^7 διαφορετικά προϊόντα. Προτίνονται οι 2 αλγόριθμοι :

1ος: επανέλαβε 1000 φορές σειριακή αναζήτηση

2ος: ταξινόμησε τη λίστα με τον καλύτερο γνωστό αλγόριθμο αναζήτησης και επέλεξε τα 1000 πρώτα προιόντα.

Ποιος είναι ο καλύτερος αλγόριθμος αν για την αναζήτηση ενός προϊόντος σε μη ταξινομημένη λίστα απαιτείται στην χειρότερη περίπτωση περίπτωση 0,1msec ενώ η ταξινόμηση 100 προϊόντων απαιτεί 1 msec. (ο χρόνος ανάκτησης των τιμών των προϊόντων θεωρείται αμελητέος)

 

Ευχαριστώ πολύ

[bokarinho]

Καλησπέρα μήπως μπορεί να με βοηθήσει κανείς με το εξής πρόβλημα:

Έστω ότι πρέπει να βρω τα κ=1000 πιο ακριβά προιόντα μιας μη ταξινομημένης λίστας με ν=10^7 διαφορετικά προϊόντα. Προτίνονται οι 2 αλγόριθμοι :

1ος: επανέλαβε 1000 φορές σειριακή αναζήτηση

2ος: ταξινόμησε τη λίστα με τον καλύτερο γνωστό αλγόριθμο αναζήτησης και επέλεξε τα 1000 πρώτα προιόντα.

Ποιος είναι ο καλύτερος αλγόριθμος αν για την αναζήτηση ενός προϊόντος σε μη ταξινομημένη λίστα απαιτείται στην χειρότερη περίπτωση περίπτωση 0,1msec ενώ η ταξινόμηση 100 προϊόντων απαιτεί 1 msec. (ο χρόνος ανάκτησης των τιμών των προϊόντων θεωρείται αμελητέος)

 

Ευχαριστώ πολύ

 

Ας παίξουμε λοιπόν λίγο, μάλλον το πρόβλημα είναι μαθηματικό γιατί με βάση τα δεδομένα αν η μία αναζήτηση για ένα προιόν σε μία μη ταξινομημένη λίστα κοστίζει 0.1 msec τότε αν επαναλάβουμε την αναζήτηση n φορές θα χρειαστούμε n * Iterations χρόνο, δηλαδή το κόστος της σειριακής αναζήτησης θα είναι:

SQ = n * Iters = 1 * 10^-4 * 10^3 = 0.1 second.

 

Από την άλλη ο χρόνος που θέλουμε για να ταξινομήσουμε 100 προιόντα είναι 1 msec. Οπότε για τα 10^7 προιόντα θα θέλουμε 10^5 * 10^-3 = 10^2 = 100 sec = 1,67 min στο περίπου. Οπότε μάλλον συμφέρει η σειριακή αναζήτηση.

Πάντως για να αποδείξουμε την περιγραφή του forum μας ως προγραμματισμός έκανα και ένα προγραμματάκι που sortάρει μία λίστα από ακεραίους με μέγεθος 10^7 και τυπώνει το πόσο χρόνο κάνει.

>
//---------------------------------------------------------------------------

#include <iostream>
#include <ctime>
#include <list>
#include <vector>
#include <algorithm>

//---------------------------------------------------------------------------

/* Use Namespace. */
using namespace std;

int CreateRandomValue(int vStart, int vFinish)
{
return (rand() / (double)RAND_MAX)* abs(vFinish - vStart) + vStart;
}
template <typename T>
list<T> CreateListFromVector(vector<T> nVec)
{
list<T> nL(nVec.begin(), nVec.end());
return nL;
}
template <typename T>
void PrintList(list<T> nList)
{
list<T>::const_iterator nIter(nList.begin());
for(; nIter != nList.end(); nIter++)
	cout << *nIter << " ";
}

/* Main Code. */
int main(int argc, char* argv[])
{
/* Index. */
static int i;
/* Max Items in the list. */
const int MAX_ITEMS = 10000000;
/* Create A List. */
list <int> nList;
/* Create A Vector. */
vector <int> nVector;
/* Time. */
srand(time(NULL));

for(i = 0; i < MAX_ITEMS; i++)
	nVector.insert(nVector.end(), CreateRandomValue(0, MAX_ITEMS));
/* Shuffle the items in the vector. */
random_shuffle(nVector.begin(), nVector.end());
/* Create The list. */
nList = CreateListFromVector<int>(nVector);
/* Print the List. */
//PrintList<int>(nList);
/* Clock it. */
clock_t start, finish;
/* Start clock(). */
start = clock();
/* Sort the list. */
nList.sort();
/* Stop Clock. */
finish = clock();
cout << "Time for sort(seconds):" << ((double)(finish-start)) / CLOCKS_PER_SEC << endl;
cout << "Press Enter to Continue...." << endl;
cin.get();
return 0;
}
//---------------------------------------------------------------------------

 

Εκτυπωμένα αποτελέσματα:

 

Time for sort(seconds):46.672

Press Enter to Continue....

στο δικό μου pc.

Bokarinho.

[myle]

Εγκυκλοπαιδικά μόνο πάντως, θα μπορούσες να τρέξεις ένα αλγόριθμο που βρίσκει τον median (το 1000 στοιχείο) και στην συνέχεια με ένα scanning σε linear time να επέστρεφες όλες τις τιμές που είναι μεγαλύτερες από αυτή. Αν τυπώνοντας τες όλες σου λείπουν κ στοιχεία, τότε τύπωσε κ φορές το στοιχείο που έχεις βρει ως median.

Συνολικά αν θυμάμαι καλά, κάτι τέτοιο θα σου πάρει linear time μιας και το median selection τρέχει σε O(n).

Αν κάνω λάθος παρακαλώ κάποιος να με διορθώσει.

[panosrap]

Η αναζήτητηση 1 (ενός) προιόντος σε μια μη ταξινομημένη λίστα 100 προιόντων είναι

10^-4 δευτερόλεπτα.

Οπότε η αναζήτηση 1 (ενός) προιόντος σε μια μη ταξινομημένη λίστα 10^7 προιόντων είναι:

 

100 -> 0,0001 δευτ

10000000 -> 10 δευτ

 

Συνεπώς για τα 1000 προιόντα σε μια λίστα 10^7 προιόντων θέλουμε 10000 δευτερόλεπτα!!! (2,5 - 3 ωρες περίπου)

 

 

Σκεφτομαι κατι λάθος???

[panosrap]

Η αναζήτητηση 1 (ενός) προιόντος σε μια μη ταξινομημένη λίστα 100 προιόντων είναι

10^-4 δευτερόλεπτα.

Οπότε η αναζήτηση 1 (ενός) προιόντος σε μια μη ταξινομημένη λίστα 10^7 προιόντων είναι:

 

100 -> 0,0001 δευτ

10000000 -> 10 δευτ

 

Συνεπώς για τα 1000 προιόντα σε μια λίστα 10^7 προιόντων θέλουμε 10000 δευτερόλεπτα!!! (2,5 - 3 ωρες περίπου)

 

 

Σκεφτομαι κατι λάθος???

 

νννννννννννννννννν

[alkisg]

Τι χάλι εκφώνηση είναι αυτή;

"Η ταξινόμηση 100 προϊόντων απαιτεί 1 msec"

 

Ε, και; Τι τάξης είναι ο αλγόριθμος; Δεν μπορούμε να υπολογίσουμε τι γίνεται με τα 10^7 προϊόντα, αν δεν ξέρουμε τι είναι... O(n^2)? O(nlogn)?

Δεν μπορεί να γίνει απλή μέθοδος των τριών όταν ανακατεύονται τετράγωνα και λογάριθμοι.

 

Η μόνη περίπτωση που θα μπορούσε να χρησιμεύσει μια τέτοια πληροφορία θα ήταν αν τα ταξινομούσες ανά εκατοντάδες και μετά έκανες merge sort, αλλά πάλι θα χρειαζόσουν κι άλλα δεδομένα.

 

Και το άλλο επίσης είναι χάλι,

"αν για την αναζήτηση ενός προϊόντος σε μη ταξινομημένη λίστα απαιτείται στην χειρότερη περίπτωση περίπτωση 0,1msec"

Σε μη ταξινομημένη λίστα πόσων στοιχείων; !!!

[alkisg]

Να το κάνω λίγο πιο σαφές.

Έστω ότι χρησιμοποιείται αλγόριθμος με Ο(n^2).

100 στοιχεία => 10.000 επαναλήψεις => 1 msec.

10^7 στοιχεία => 10^14 επαναλήψεις => 10.000.000.000 msec.

Η απλή μέθοδος των τριών δηλαδή μπορεί να εφαρμοστεί μόνο ανάμεσα στις επαναλήψεις και στα msec, όχι στα στοιχεία.

 

Από την άλλη, αν χρησιμοποιείται αλγόριθμος με Ο(nlogn) =>

100 στοιχεία => 664 επαναλήψεις => 1 msec.

10^7 στοιχεία => 232534967 επαναλήψεις => 350.000 msec.

 

Τεράστια διαφορά δηλαδή ανάλογα με την τάξη του αλγορίθμου.

 

edit: Βέβαια μπορεί να γίνει ο εξής υπολογισμός:

Αναζήτηση 1000 στοιχείων => 1000*10^7 = 10.000.000.000 επαναλήψεις.

Ταξινόμηση 10^7 στοιχείων με O(nlogn) => 10^7*23 = 232.534.967 επαναλήψεις.

 

Δηλαδή η ταξινόμηση είναι 43 φορές πιο γρήγορη, αν θεωρήσουμε ότι η επανάληψη της αναζήτησης είναι το ίδιο χρονοβόρα με την επανάληψη της ταξινόμησης (αυτό δηλαδή που λέει ότι ο χρόνος ανάκτησης είναι αμελητέος).

[panoramix222000]

Παιδία παίζει κανένας αλγόριθμος ταξινόμησης πίνακα με Vector που έχει μέσα αντικείμενα με Strings μέσα να και ο κώδικας:

>
import java.util.Vector;
public class AnimalVector
{
public static void main(String[] args)
{
	int x,y,z,v,t,r;
	String a,b,c,d,e,f,temp,max;
    Vector animalVector = new Vector();
    Dog firstDog = new Dog("Jena", "Chihuahua");
    animalVector.add(firstDog);
    a=firstDog.getName();
    Dog secondDog = new Dog("Gas", "Seter");
    animalVector.add(secondDog);
    b=secondDog.getName();
    Cat firstCat = new Cat ("Lisa" , "koprogata");
    animalVector.add(firstCat);
    c=firstCat.getName();
    Cat secondCat = new Cat ("Sissie");
    animalVector.add(secondCat);
    d=secondCat.getName();
    Mouse firstMouse = new Mouse ("Mickey" , "Disney");
    animalVector.add(firstMouse);
    e=firstMouse.getName();
    Mouse secondMouse = new Mouse ("Speedy");
    animalVector.add(secondMouse);
    f=secondMouse.getName();
    {
        System.out.println(animalVector.elementAt(i));
    }
 }
}