Kth Smallest in Subsequence.

[TSMGeorge]

Έστω ότι έχουμε Ν αριθμούς.

 

- Να φτιάξουμε Μ Subsequences

- Να βρούμε τον Kth-Smallest In each Subsequence

- Να βρούμε τον Smallest from all KthSmallests

 

Παράδειγμα:

 

 

5 3 2

1 5 3 4 2

1 5 3 (2nd smallest is 3)

5 3 4 -> 4

3 4 2 -> 3

4 2 1 -> 2

2 1 5 -> 2

Result is : 2

 

Το προγραμμάτισα.

 

Ποιο το πρόβλημα όμως; Αν κάνεις όλα τα Subsequence για 100.000 αριθμούς θα σου-μου πάρει κοντά 2-3 λεπτά και το time limit είναι 2seconds. (Μέχρι 10.000 εγγραφές είναι ΟΚ ο κώδικας).

 

Τι σκέφτηκα?

 

 

- Δεν χρειάζεται να κάνουμε όλα τα Subsequence. 

- Να κάνουμε μόνο CEIL(N/M) Subsequences και να βρούμε αυτά που πρέπει να βρούμε

Παράδειγμα:

5 3 2
1 5 3 4 2

CEIL(N/M) = 2;
Subsequence 1:   1 5 3     2nd-Smallest: 3
Subsequence 2:    4 2 1    2nd-Smallest:  2

Result: 2

 

Η παραπάνω λογική λύνει το θέμα με το Timeout. (0.7~ sec(Javafail) για 100.000 records) αλλά δεν βγάζει πάντα σωστά αποτελέσματα.

 

- Θα πρέπει η αρχική λίστα με τους αριθμούς να μην έχει διπλότυπα ή αφού σπάσω την αρχική λίστα σε υπολίστες (CEIL(N/M)) να βγάλω τα διπλότυπα;

 

Ίσως και ο τρόπος που σκέφτηκα να μην είναι σωστός... αλλά ότι παραδείγματα έκανα στο χαρτί μου βγαίναν (και έκανα πολλά & διαφορετικά από αυτό που σας δείχνω)

 

PS: Έγραψα πολλά... απλά ζητάω αν αυτό που σκέφτηκα είναι σωστό και σε περίπτωση που η αρχική λίστα έχει διπλότυπα, τα βγάζουμε απο εκεί ή ύστερα στις sub λιστες?

[albNik]

Εχεις τα subsequences ή πρεπει να τα φτιαξεις απο τους 100.000?

Ποσα subsequences και τι size θα εχουν?

[TSMGeorge]

Έχεις Ν αριθμούς.

Βγάζεις όλα τα Subsequences μήκους M.

Βρίσκεις τον Kth Smallest σε όλα τα Subsequences.

Από όλα Kth Smallests βρίσκεις το μικρότερο.

 

Έστω ότι έχεις 5 αριθμούς, με Μ = 3 & Κ =2

1 5 3 4 2

 

Οι ακολουθίες που προκύπτουν είναι:

1 5 3

5 3 4

3 4 2

4 2 1

2 1 5

 

Από αυτές τις υπο-ακολουθίες βρίσκεις τον μικρότερο, οπότε : 

3

4

3

2

2

 

Παίρνεις το μικρότερο που είναι το 2

 

Αυτό αν το κάνεις με 100.000 αριθμούς με Μ=50.000 & Κ=5.000 Πχ. Θέλει κοντά 2 λεπτά να τελειώσει ΚΑΙ ΕΧΕΙΣ ΜΟΝΟ 2sec στη διάθεση σου.

 

Οπότε, σίγουρα (με καμία παναγία) δεν παίρνεις υπο-ακολουθίες όπως περιέγραψα πάνω... (απλά το έχει στην εκφώνηση για να καταλάβουμε).

Ένας τρόπος είναι:

Αντί να πάρεις

1 5 3

5 3 4

.....κλπ (δηλαδή κατά 1 να προχωράς τον 1ο βρόχο)

να πάρεις κατευθείαν

153 421 (δηλαδή: παίρνεις μια ομάδα με Μ-αριθμούς, μετά προχωράς Μ θέσεις και παίρνεις την επόμενη ομάδα. 

 

Αλλά! κατά πόσο είναι σωστός? 

- Με αυτόν τον τρόπο, περνάω 2/6 τεστ που τρωω Timeout και στα υπόλοιπα απλά "Wrong Answer" (δεν έχω θέμα χ΄ρονου).

- Μου χαλάει τα αρχικά μικρά τεστ που τα πιάνω.

 

Κοιτάξτε, αν τον κάνω όπως γράφω πάνω πάνω ο αλγόριθμος βγάζει 100% σωστά αποτελέσματα αλλά θέλει χ100 φορές χρόνο.

Οπότε ψάχνω άλλον τρόπο για να γλιτώσω το-τα:

Ν * Μ * search_in_M_Subsequence_for_Kth_smallest.

[albNik]

Θα εχεις ενα παραθυρο μηκους Μ θα το μετακινείς κατα μια θεση και θα ανανεωνεις πάντα τον Kth Smallest ελεγχοντας μονο το νεο αριθμο που προσθετεις και αυτο που αφήνεις

 

 

Εχεις N=10 και M=8

 

Το Μ αρχικα θα δειχνει στο διαστημα [0 7], μετα [1 8], [2 9], [3, 0], [4 1], [5 2], [6 3], [7 4], [8 5]  και [9 6]

[defacer]

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

 

Μια προφανής λύση είναι να έχεις ένα window (array) μήκους Μ από το οποίο κάθε φορά θα μπορείς να βρεις το kth smallest στοιχείο φτιάχνοντας ένα ταξινομημένο αντίγραφο με κόστος O(MlogM) και παίρνοντας το kth στοιχείο του με κόστος Ο(1). Αυτό θα πρέπει να επαναληφθεί Ν φορές οπότε καταλήγεις σε αλγόριθμο O(N * MlogM). Το να θυμάσαι ποιό είναι το μικρότερο από τα kth smallest που έχεις δει είναι πολύ απλό, δεν το αναφέρω καν.

 

Γρήγορη δοκιμή σε C# με Ν = 1000000, Μ = 3, Κ = 2 (που δεν παίζει ρόλο) τρέχει εδώ σε ~420 msec.

 

Το καλύτερο που μπορείς να κάνεις είναι O(N * logM), για παράδειγμα χρησιμοποιώντας κάποιου είδους BST ή αντίστοιχο data structure (skip list, διάφορα heaps). Αν πρόκειται το Μ να έχει καμπόσα μηδενικά από πίσω μόνο τέτοια λύση θα σε καλύψει, για μικρά Μ κάνει και η παραπάνω.

[albNik]

N*MlogM ειναι αργό για Ν=100000 Μ=50000.

Μονο την πρώτη φορα χρειαζεται να ταξινομισει το παραθυρο (MlogM) μετα θα αφαιρει εναν (logM) και θα εισαγει τον επομενο  αριθμο στον ηδη (logM) ταξινομιμενο array Ν φορες. Δλδ  συνολο (Μ+2Ν)logM

[defacer]

Ναι, γι' αυτό λέω αν το Μ έχει μηδενικά από πίσω δε γίνεται έτσι. Όμως αυτό που περιγράφεις δε γίνεται με array για πολλούς λόγους, π.χ. εισαγωγή σε ήδη ταξινομημένο array δε γίνεται σε logM αλλά σε Μ.

 

Για το window θέλεις κάτι του στυλ ένα BST (insert και k-th smallest σε logM) και ταυτόχρονα μια queue με pointers σε tree nodes (insert/delete σε 1 οπότε δε μετράει) για να ξέρεις επίσης σε 1 ποιό είναι το επόμενο στοιχείο που θα πρέπει να αφαιρέσεις από το tree (πάλι logM) όπως προχωράει το window. Οπότε συνολικά έχεις σε κάθε iteration κάτι του στυλ 3logM + C, σύνολο για όλη τη δουλειά NlogM.

[TSMGeorge]

Παιδιά, όπως και να το κάνουμε,  δεν γίνεται να τα καταφέρεις σε 2Sec αν το πάμε σειριακά (Μ=50.000 δηλαδή : 0-50.000 , 1-50.001, 2-50.002.... 100.000-49.999)

 

Ο μόνος τρόπος είναι να πηδάμε θέσεις. Αυτό που σας είπα (να πηδάμε κατά Μ θέσεις: 0-50.000, 50.001-1 (i+j%N) Αλλά θέλει ίσως κάποιες αλλαγές.

 

Παράδειγμα:

100.000 90.000 5.000 (Συνολικά στοιχεία, μήκος ομάδας, Kth στοιχείο σε κάθε subsequence). 

- Θα έχουμε 2 subsequences [ 0-90.000 & 90.001 - 80.000 (shift)]

- Σε κάθε subsequence θα πάρουμε τον Kth smallest. 

- To Τελικό αποτέλεσμα θα είναι ο μικρότερος από τα 2 Κth-smallests που θα έχουμε πάρει από τις 2 υπο-ακολουθίες.

 

Αυτό έκανα και έλυσα το πρόβλημα του χρόνου, πέρασα 2(ή 3;) τεστς/10 που δεν μπορούσα πριν λόγω χρόνου αλλά αυτό μου χάλασε και τα μικρά τεστ (με 10-100 στοιχεία), που σημαίνει ότι δεν είναι σωστός τρόπος ή απλά κάτι πρέπει να υπολογίσω ακόμα.

 

Μήπως από τα 2 Subsequence, να πάρω το άθροισμα και όποιο έχει το μικρότερο άθροισμα, να πάω να ψάξω εκεί? ναι αλλά όταν τα Inputs είναι 9ψήφια και πρέπει να πάρεις το άθροισμα από 90.000 στοιχεία δεν γίνεται!. Αν διαιρέσεις με το 1κκκ (για να το * μετά) χάνεις ακρίβεια και πάλι θα βγάζεις λάθος συμπεράσματα.

 

Πραγματικά δεν ξέρω....

[defacer]

Θα έπρεπε να είναι φανερό ότι ο τρόπος που σίγουρα δεν λύνει το πρόβλημα είναι να πηδάμε θέσεις. Για παράδειγμα, στο (100Κ 90Κ 2), αν τα στοιχεία 1 και 90000 είναι ας πούμε 10 και τα υπόλοιπα 99998 στοιχεία είναι όλα 20, τότε η σωστή τελική απάντηση είναι 10 ενώ αυτό που λες θα δώσει 20. Γενικά είναι ασύγκριτα πιο εύκολο να αποδείξεις  ότι κάποια προσέγγιση δε δουλέυει από το να βρεις αυτή που δουλεύει.

 

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

[TSMGeorge]

Πες ότι το παίρνουμε κανονικά. 

 

Παράδειγμα:

5 4 2

1 5 2 1 3

1 5 2 1        Kth-smallest = 1 ή 2; αν 2, τότε το 4ο μικρότερο πιο είναι; αφού έχουμε μόνο 1 2 5 (μοναδικά)
5 2 1 3        (2)
2 1 3 1        (1 ή 2;)
.....

 

 

Τι θέλω να σου πω... ότι αν επιτρέπονται ίδιοι αριθμοί, τότε σίγουρα στο παράδειγμά σου είναι το 10.

 

Αυτό που σου λέω για ίδιους αριθμούς δεν το λέει κάπου... εγώ το λέω! 

 

---------

 

Αν το πάρουμε σειριακά όπως είπα, σίγουρα δεν φτάνουν 2Sec.

 

Δοκίμασα άδειο βρόχο που απλά αντέγραφα-δημιουργούσα τις υπο-ακολουθίες (χωρίς να κάνω Search για Kth ή άλλες πράξεις) και έκανε περισσότερη ώρα. Που να γινόταν και κάποια δουλειά ε;

[albNik]

2-3 δευτερολεπτα εχοντας μια sorted list και μετακινώντας κατα 1 το παραθυρο.

		static void Test()
		{
			int N = 100000;
			int M = 50000;
			int K = 5000;
			int[] numbers = new int[N];
			Random r = new Random();
			for(int i = 0; i < N; i++)
				numbers[i] = r.Next();

			List<int> sortedList = new List<int>(numbers.Take(M));
			sortedList.Sort();
			int min = sortedList[K];
			for(int i = 0; i < N; i++)
			{
				AddInSorted(sortedList, numbers[(i + M) % N]);
				RemoveFromSorted(sortedList, numbers[i]);
				min = Math.Min(sortedList[K], min);
			}

			Console.WriteLine(min);
		}

		static void AddInSorted(List<int> sortedList, int value)
		{
			if(sortedList.Count == 0)
				sortedList.Add(value);
			else if(sortedList[sortedList.Count - 1] < value)
				sortedList.Add(value);
			else
			{
				int index = sortedList.BinarySearch(value);
				if(index < 0)
					sortedList.Insert(~index, value);
				else
					sortedList.Insert(index, value);
			}
		}

		static void RemoveFromSorted(List<int> sortedList, int value)
		{
			int ind = sortedList.BinarySearch(value);
			if(ind >= 0)
				sortedList.RemoveAt(ind);
		}

[defacer]

Έτρεξα το παραπάνω για Ν = 1Μ και Κ = 20 παίζοντας με την τιμή του Μ. Τα αποτελέσματα ήταν
 
Μ=50        270ms
Μ=500      520ms
Μ=5000    2060ms
Μ=50000  17800ms
 
Είναι φανερό πως η συμμετοχή του Μ στο runtime δεν είναι λογαριθμική, συγκεκριμένα είναι γραμμική επειδή όπως είπα το add/remove σε sorted array είναι O(N). Εξάλλου το λέει και στο MSDN:

 

The SortedList<TKey, TValue> generic class is an array of key/value pairs with O(log n) retrieval, where n is the number of elements in the dictionary. In this, it is similar to the SortedDictionary<TKey, TValue> generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

• SortedList<TKey, TValue> uses less memory than SortedDictionary<TKey, TValue>.
• SortedDictionary<TKey, TValue> has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList<TKey, TValue>.
• If the list is populated all at once from sorted data, SortedList<TKey, TValue> is faster than SortedDictionary<TKey, TValue>.

 
Αυτό επειδή η SortedList υλοποιείται με arrays ενώ το SortedDictionary είναι tree. Το θέμα είναι πως ούτε SortedDictionary σου κάνει εδώ γιατί το public interface της δεν υποστηρίζει όλες τις λειτουργίες που μας χρειάζονται (παρόλο που το ίδιο το data structure τις υποστηρίζει).
 
Για να το δεις στην πράξη, παρατήρησε πρώτα ότι για τα νούμερά σου Ν = 100Κ, Μ = 50Κ η ταχύτητα εκτέλεσης δεν αλλάζει (σε μένα κάνει 1780ms) για Κ = 1 ή για Κ = 5000.
 
Στη συνέχεια δες αυτό, όπου προσπαθώ να κάνω το dictionary να δουλέψει:
 

int N = 100000;
int M = 50000;
int K = 5000;
int[] numbers = new int[N];
Random r = new Random();
for(int i = 0; i < N; i++)
    numbers[i] = r.Next();
 
var seed = numbers.Take(M);
var window = seed.GroupBy(i => i).ToDictionary(g => g.Key, g => g.Count());
int min = int.MaxValue;
for(int i = 0; i < N; i++)
{
    var incoming = numbers[(i + M) % N];
    var outgoing = numbers[i];
    min = Math.Min(min, window.Keys.Skip(K).First()); // SAD PANDA!
    if (window.ContainsKey(incoming)) {
        window[incoming]++;
    }
    else {
        window[incoming] = 1;
    }
    if (window[outgoing] == 1) {
        window.Remove(outgoing);
    }
    else {
        window[outgoing]--;
    }
}
 
Console.WriteLine(min);

[αφήνω κατα μέρος ότι ο υπολογισμός του min εδώ εκτός από αργός είναι και τελείως λάθος, δεν παίζει ρόλο σ' αυτό που αναλύω]

 

Το πρόβλημα εδώ είναι ότι ενώ σε BST (που το SortedDictionary είναι τέτοιο) μπορείς να έχεις kth smallest σε logΝ, το SortedDictionary δεν παρέχει τέτοια δυνατότητα οπότε αναγκάζομαι να το κάνω σε N. Αν έγραφα δικό μου tree και είχα πρόσβαση στα εσωτερικά του (και αυτός είναι ο λόγος που βάφτισα το πρόβλημα πολύ δύσκολο) θα μπορούσα να το έχω σε logN. Τι διαφορά θα έκανε αυτό;
 
Η δική σου version δεν αλλάζει χρόνο εκτέλεσης αλλάζοντας το K. H version με το tree με Ν, Μ απείραχτα αλλά Κ = 1 τρέχει εδώ σε 80ms αντί για 1780.
 
Είναι νομίζω προφανές ότι αν ήταν έτοιμο το kth smallest σε logN θα μπορούσαμε να έχουμε πράγματα του στυλ N = 1M, M = 100K, K = 50K σε λιγότερο από 1sec, που είναι και η ιδανική λύση του προβλήματος.
 

Τι θέλω να σου πω... ότι αν επιτρέπονται ίδιοι αριθμοί, τότε σίγουρα στο παράδειγμά σου είναι το 10.
 
Αυτό που σου λέω για ίδιους αριθμούς δεν το λέει κάπου... εγώ το λέω!

Οι ίδιοι αριθμοί επιτρέπονται εξ' ορισμού γιατί πουθενά δεν λέει ότι απαγορεύονται. Από τους 1 1 1 2 ο τρίτος μικρότερος είναι προφανώς το 1.
 

Αν το πάρουμε σειριακά όπως είπα, σίγουρα δεν φτάνουν 2Sec.
 
Δοκίμασα άδειο βρόχο που απλά αντέγραφα-δημιουργούσα τις υπο-ακολουθίες (χωρίς να κάνω Search για Kth ή άλλες πράξεις) και έκανε περισσότερη ώρα. Που να γινόταν και κάποια δουλειά ε;

Σου είπα ήδη τι πρέπει να σταματήσεις να κάνεις (δοκιμές στην τύχη) και τι να κάνεις αντί γι' αυτό (πάρε βιβλίο και ξεκίνα, εγώ έμαθα από αυτό και το συστήνω αλλά αν ρωτήσεις ή ψάξεις εδώ στο forum θα πάρεις και εναλλακτικές προτάσεις).

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

[albNik]

Επισης εχω την αισθηση οτι μπορείς να "πηδας" νουμερα (το πόσα εξαρταται από τα Μ, Κ), αντι να πηγαίνεις ενα-ενα, 

[defacer]

Επισης εχω την αισθηση οτι μπορείς να "πηδας" νουμερα (το πόσα εξαρταται από τα Μ, Κ), αντι να πηγαίνεις ενα-ενα, 

 

Δεν μπορείς.

[TSMGeorge]

@albNik @defacer

 

Και οι δύο κώδικες βγάζουν λάθος αποτελέσματα.

 

@defacer

Αυτό το βιβλίο το ξέρω, μου το πρότεινε και άλλος. Πρέπει να είναι καλό ε; μόνο που συχαίνομαι την Java. Τέσπα! πως μπορώ να κατεβάσω τους κώδικες μαζικά; γιατί κατεβάζω πχ το Dijkstra.java και έχει άλλα 4-5 αρχεία import που πρέπει να τα βρω-κατεβάσω 1-1. Δεν τα έχει σε .rar?