Cześć,
natknąłem się ostatnio na niesamowicie prosty pomysł rozwiązujący problem sortowania liczb.
Polega on na wykorzystaniu funkcji sleep(). A dokładnie, pokaże to na przykładzie 5 liczb: 4,2,6,9,3
Dla każdej z tych liczb tworzymy osobny wątek i usypiamy go funkcją sleep na czas proporcjonalny do wartości danej liczby. Wiadomo że najszybciej wykonywać się skończy wątek który został uśpiony na najmniejszą ilość czasu a więc ten który miał najmniejszą liczbę. Po funkcji sleep można dodawać te liczby do kolekcji w ten sposób otrzymując efekt sortowania. Słowo „proporcjonalny” jest bardzo ważne, nie można użyć tutaj konkretnej wartość liczby, szczególnie dobrze widać to na przykładzie małych liczb:
Usypiając wątki na Nms wiemy że one obudzą się nie wcześniej niż po uływie Nms, co jednak nie znaczy że nie mogą się obudzić później niż dokładny czas (tutaj rolę odgrywa ilość wątków a więc czas przełączania kontekstu). Bez proporcjonalnego wydłużania czasu uśpienia, mogłoby się zdarzyć że watek, mimo tego że został uśpiony wcześniej, obudzi się milisekundę później niż ten który został uśpiony później. Oczywiście nie wyeliminujemy tego problemu, możemy, dzięki mnożeniu czasu uśpienia, zwiększyć różnicę między liczbami co spowoduje że przesunięcia w czasie nie będą problemem, gdyż różnica między 1 a 2 jest znacznie mniejsza niż między 10 a 20.
Niestety to nie gwarantuje poprawnego działa algorytmu. Co w gruncie rzeczy skreśla go z listy rzetelnych sposobów sortowania.
Kilka ciekawych właściwości:
No i na koniec moja przykładowa implementacja. Warto dodać iż eksperymentowałem chwilkę z tym pomysłem, niestety nie udało mi się go jakoś poprawić.
Jeśli masz jakiś pomysł – pisz w komentarzu ;)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | /** * * @author Matt */ public class SleepSort { public static int howMuchDigits = 10000; public static void main(String[] args) throws InterruptedException, Exception { int count = howMuchDigits; List<Integer> digits = new ArrayList<>(); List<SleepThread> threads = new ArrayList<>(); Random r = new Random(); while(count>=0){ digits.add(r.nextInt(19)+1); count--; } for(int digit : digits){ SleepThread t = new SleepThread(digit); t.start(); threads.add(t); } for(SleepThread thread : threads) thread.join(); System.out.println("Sorting done. Checking order.."); checkOrder(); } public static void checkOrder() throws Exception { Iterator<Integer> iterator = SleepThread.objList.iterator(); while (iterator.hasNext()) { try { int first = iterator.next(); int second = iterator.next(); if (second < first) { throw new Exception("Invalid Order!!!"); } } catch (java.util.NoSuchElementException x) { break; } } System.out.println("Valid Order"); } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | /** * * @author Matt */ public class SleepThread extends Thread{ private final int miliSeconds; private final int probablyValidDuration = SleepSort.howMuchDigits/5; public static List<Integer> objList = Collections.synchronizedList(new ArrayList<Integer>()); public SleepThread(int miliSeconds) { this.miliSeconds = miliSeconds; } @Override public void run() { try { Thread.sleep(miliSeconds*computeDuration()); } catch (InterruptedException ex) { Logger.getLogger(SleepThread.class.getName()).log(Level.SEVERE, null, ex); } objList.add(miliSeconds); } private long computeDuration(){ return SleepSort.howMuchDigits<=100?100:probablyValidDuration; } } |
Cześć. Dziś luźny artykuł, bo dziś pobawimy się jedną z pierwszy wersji Pythona. Skompilujemy go i zobaczymy co tam w… Read More
Nowy rok czas zacząć! Więc lećmy z podsumowaniem. Nowy artykuł Nie uwierzycie, ale pojawił się na blogu nowy artykuł! Piszę… Read More
Cześć! W Pythonie 3.13 dodano JITa! JIT, czyli just-in-time compiler to optymalizacja na która Python naprawdę długo czekał. Na nasze… Read More
Cześć! Zapraszam na podsumowanie roku 2024. Książki W sumie rok 2024 był pod względem ilości książek nieco podobny do roku… Read More
Podtrzymując tradycję, prawie regularnych podsumowań, zapraszam na wpis! Nie mogło obyć się bez Karkonoszy We wrześniu odwiedziłem z kolegą Karkonosze,… Read More
Oj daaawnoo mnie tu nie było. Ale wakacje to był czas dużej liczby intensywnych wyjazdów i tak naprawdę, dopiero jakoś… Read More
