Προγραμματιστική απορία πάνω σε αλγόριθμο

[παπι]

εχεις δικιο. Αλλα τοτε θα επρεπε απλα να εφαρμοσω τον τυπο της αποστασης manhattan.

 

Βασικα, κακως χωρισες τα σημεια σε δυο πινακες.

 

Εαν θες τα πιο κοντινα σημεια, δες ποσο ευκολα βγαινει με abstraction και vectors

struct vec2
{
	float x,y;
	vec2(){}
	vec2(const float& x,const float& y):
		x(x),y(y){}
	float len() const
	{
		return std::sqrt(x*x+y*y);
	}
	vec2 operator-(const vec2& other) const
	{
		return vec2(x-other.x,y-other.y);
	}
};

int main()
{
	//init random vecs
	vec2 vecs[]=
	{
		vec2(1,1),
		vec2(1,2),
		vec2(-2,3),
		vec2(1,0.9),
		vec2(3,10)
	};

	vec2 v1,v2;
	float minDist = std::numeric_limits<float>::max();

	//mia forfor gia test ola me ola
	for(int i = 0; i < _countof(vecs); i++)
		for(int j = i; j < _countof(vecs); j++)
		{
			//alla oxi gia idia
			if(i == j)
				continue;


			float dist = ( vecs[i] - vecs[j]).len();

			if(dist < minDist)
			{
				minDist = dist;
				v1 = vecs[i];// ayto
				v2 = vecs[j];// kai ayto exoyn thn mikroterh apostash
			}

		}

	
	return 0;
}

[defacer]

Σορταρω γιατι ειναι ευκολοτερο να υπολογισω τα αθροισματα με γραμμικη πολυπλοκοτητα.

 

Nice (αν και από τη στιγμή που σορτάρεις είσαι ήδη NlogN αλλά χαλάλι). Τεσπα για το θέμα μας, προφανώς θα χρειαστείς είτε κάποιο tree ή hashtable -- για να μη χαλάσεις το NlogN σου δε μπορεί να είναι κάτι άλλο -- με το οποίο αντιστοιχίζεις θέσεις πριν το sort και μετά το sort, οπότε το θέμα είναι πώς θα γίνει το sort να ενημερώσει αυτό το data structure κατάλληλα, είτε θα βάλεις ένα index μέσα στους πίνακες που σορτάρεις (οι οποίοι θα γίνουν πινακες από οχι primitives) για να μπορείς να βγάλεις άκρη μετά.

 

Δείξε λίγο κώδικα όμως, δεν ξέρουμε καν για τι γλώσσα μιλάμε.

[παπι]

να και το αποτελεσμα που ειναι σωστο (το 1,1 με το 1, 0.9 εχουν την μικροτερη αποσταση.

[defacer]

Ναι οκ αλλα για να το κανεις αυτο χρειαζεσαι Ν^2 πραξεις

 

Τσούκου. Αν σορτάρει όπως λέει τότε μπορεί να κάνει το εξής:

 

1  => (2 - 1) + (3 - 1) + (5 - 1) = 7, προφανές

2  => 7 - 2 * 1 = 5, όπου 7 το από πάνω, 2 τα στοιχεία που ακολουθούν και 1 η απόσταση από το προηγούμενο

3  => 5 + 1 * 1 - 1 * 1 = 5, όπου στο + ο ένας άσσος είναι το (i - 1) και ο άλλος η απόσταση από το προηγούμενο¹

5  => 5 + 2 * 2 = 9 όπως παραπάνω

 

Αυτό είναι O(N).

 

¹ i = zero-based index της γραμμής. Ο όρος + υπήρχε και στο απο πάνω βήμα, αλλά εκεί i - 1 = 0 οπότε απαλείφεται

[Anubis13]

Nice (αν και από τη στιγμή που σορτάρεις είσαι ήδη NlogN αλλά χαλάλι). Τεσπα για το θέμα μας, προφανώς θα χρειαστείς είτε κάποιο tree ή hashtable -- για να μη χαλάσεις το NlogN σου δε μπορεί να είναι κάτι άλλο -- με το οποίο αντιστοιχίζεις θέσεις πριν το sort και μετά το sort, οπότε το θέμα είναι πώς θα γίνει το sort να ενημερώσει αυτό το data structure κατάλληλα, είτε θα βάλεις ένα index μέσα στους πίνακες που σορτάρεις (οι οποίοι θα γίνουν πινακες από οχι primitives) για να μπορείς να βγάλεις άκρη μετά.

 

Δείξε λίγο κώδικα όμως, δεν ξέρουμε καν για τι γλώσσα μιλάμε.

Θα σορταρω με radixsort και παραμενω στην γραμμικη πολυπλοκοτητα.

 

Τσούκου. Αν σορτάρει όπως λέει τότε μπορεί να κάνει το εξής:

 

1  => (2 - 1) + (3 - 1) + (5 - 1) = 7, προφανές

2  => 7 - 2 * 1 = 5, όπου 7 το από πάνω, 2 τα στοιχεία που ακολουθούν και 1 η απόσταση από το προηγούμενο

3  => 5 + 1 * 1 - 1 * 1 = 5, όπου στο + ο ένας άσσος είναι το (i - 1) και ο άλλος η απόσταση από το προηγούμενο¹

5  => 5 + 2 * 2 = 9 όπως παραπάνω

 

Αυτό είναι O(N).

 

¹ ο όρος + υπήρχε και στο απο πάνω βήμα, αλλά εκεί i - 1 = 0 οπότε απαλείφεται

 

Νόμιζα ότι έλεγε χωρίς να τα σορτάρει. Αλλα η ιδεα ειναι πολυ καλη και χωρις εξτρα memory space. very nice!

 

Kώδικα προς το βράδυ.

[defacer]

Νόμιζα ότι έλεγε χωρίς να τα σορτάρει. Αλλα η ιδεα ειναι πολυ καλη και χωρις εξτρα memory space. very nice!

 

Καλά, εγώ νόμιζα ότι απαντάω σε άλλον, ας μη το κάνουμε θέμα. Αυτός που θα σορτάρει ήσουν εσύ... οπότε λύσε μου και την απορία: αφού απ' οτι καταλαβαίνω ήδη είχες O(n) μετά το sort, ποιά ακριβώς ήταν η προσέγγιση; Κάτι για extra space λες...

 

 

 

Η πλάκα είναι ότι ο παραπάνω αλγόριθμος προέκυψε μόνο και μόνο επειδή εσύ έγραψες ότι το κάνεις σε O(n) οπότε αναρωτήθηκα πώς να το κάνει άραγε.

 

 

[Anubis13]

Καλά, εγώ νόμιζα ότι απαντάω σε άλλον, ας μη το κάνουμε θέμα. Αυτός που θα σορτάρει ήσουν εσύ... οπότε λύσε μου και την απορία: αφού απ' οτι καταλαβαίνω ήδη είχες O(n) μετά το sort, ποιά ακριβώς ήταν η προσέγγιση; Κάτι για extra space λες...

 

 

 

Η πλάκα είναι ότι ο παραπάνω αλγόριθμος προέκυψε μόνο και μόνο επειδή εσύ έγραψες ότι το κάνεις σε O(n) οπότε αναρωτήθηκα πώς να το κάνει άραγε.

 

 

 

Ίσως να είναι παρόμοια ιδέα, όπως είπα έχω κρατήσει σε 2 πίνακες μονοδιάστατους τα σημεία του Χ άξονα και μετά τα σημεία του Υ άξονα. Σε μία κόπια αυτών, τους σορτάρω και ξεκινάω να βρω τα partial sums(απο αριστερα προς τα δεξια και το αναποδο) δηλαδη για το παραδειγμα S ={7, 12, 17, 26} και L= {26, 19, 14, 9}

 

Μετα χρησιμοποιω τον τυπο S(n)-S(i) -(Ν-1-ι)*A + L(ι)-L(1)+(i)*A

όπου Α[ι] ειναι ο σορταρισμενος μου πινακας με τα σημεια,

S ο πινακας με τα partial sums απο αριστερα προς τα δεξια

L ο πινακας με τα partial sums απο δεξια προς τα αριστερα

 

Πχ

1 2 3 5,

S(4)-S(2)-(2-1)*A[2]+L(4-2)-L(1)+(1-1)*A[2] = 26-12-1*2+19-26+0*2= 12+(-7)= 5

 

Eτσι δουλευω για ολα. Αυτα τα κραταω και μετα ηθελα να γυρισω στους αρχικους πινακες προσθετοντας τα "κοστη" μονο για καθε συντεταγμενη που εχω και να βρω την minimum.

Επεξ/σία 12 Δεκεμβρίου 2013 από Anubis13

[παπι]

Και τι ακριβως ψαχνεις;

[Anubis13]

Oτι απο ολες τις συντεταγμενες το καλυτερο σημειο συναντησης πχ ειναι το (2,5) σε 10 βηματα. Απλα πρεπει να αντιστοιχισω τα βηματα με τις αρχικες συντεταγμενες.

[παπι]

Δηλαδη ψαχνεις αυτο; http://sketchtoy.com/57101743

[Anubis13]

Αυτο που μου δειχνεις λυνεται και με manhattan. Οποτε οχι. Ψαχνω ποιο ειναι το σημειο με την μικροτερη αποσταση για συναντηση απο ενα συνολο σημειων οταν μπορεις να κινηθεις μονο οριζοντια και καθετα.

 

Αλλα εγω δεν ζηταω λυση στο προβλημα. Την λυση την ξερω. Την εχω τσεκαρει και με το χερι.

[παπι]

1) Δεν μπορω να καταλαβω γιατι εχεις χωρισει τα σημεια σε χ και ψ. Οκ, δεν το θες με υποτεινουσα, αλλα μπορεις ευκολα να φτιαξεις μια συναρτηση η οποια σου δινει την "οριζοντια/καθετη" αποσταση ετσι οπως την θες.  

2) Αυτο με το οριζοντια καθετη vs υποτεινουσας, επισης δεν μπορω να το καταλαβω. Υπαρχει περιπτωση οπου η αποσταση (πραγματικη, υποτεινουσα) αναμεσα σε δυο σημεια να διαφερει απο την αποσταση οριζονιτα/καθετη;

 

οταν λεω διαφερει, εννοω πχ εχουμε v1,v2,v3

με υποτεινουσα να ειναι v1,v2 τα πιο κοντινα, ενω με οριζονια/καθετη να ειναι πιο κοντα το v1 με το v3; Δεν νομιζω, δε βαγαζει νοημα.

[Anubis13]

1) Πώς θα το κάνες? Θα μπορουσες να εχεις ενα struct με 2 rows και να σορταρεις τα 2 rows. Dεν βλεπω την διαφορα. Για πες μου πως θα το εκανες?

2) Αν εχω ενα σημειο και παω 1 βημα οριζοντιο και 1 καθετο τοτε εχω κοστος 2. Αν παω με την υποτεινουσα ειναι sqrt(2).

[albNik]

Εγώ πιστευω ειναι πιο δυσκολο να βαλεις τα σημεια σε "αυξουσα" σειρα ώστε να εφαρμόσεις τον Ο(n) αλγοριθμο.

Ενω με x, y χωριστά ειναι πιο απλο : εφαρμοζεις δυο φορες τον αλγοριθμο.

[παπι]

2) τωρα το καταλαβα.

1) Θα κανω 2-3 τεστ, και θα σου απαντησω. (ψωρις υλοποιηση)