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:
- Czas wykonywania się algorytmu jest czasem liczonym w ms i odpowiada wartości odpowiednio pomnożonej, największej liczby oraz czasu przeznaczonego na przetwarzanie wątków.
- Algorytm nie jest wrażliwy na stopień posortowania danych wejściowych
- Algorytm w żaden sposób nie porównuje liczb
- Algorytm jest bardzo wrażliwy na różnice między wielkością liczb
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; } } |
Mateusz Mazurek
