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; } } |
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
Cześć! Zapraszam na krótkie podsumowanie kwietnia. Wyjazd do Niemiec A dokładniej pod granicę z Francją. Chrześnica miała pierwszą komunię. Po… Read More
Ostatnio tygodnie były tak bardzo wypełnione, że nie udało mi się napisać nawet krótkiego podsumowanie. Więc dziś zbiorczo podsumuję luty… Read More
Zapraszam na krótkie podsumowanie miesiąca. Książki W styczniu przeczytałem "Homo Deus: Historia jutra". Książka łudząco podoba do wcześniejszej książki tego… Read More
Cześć! Zapraszam na podsumowanie roku 2023. Książki Zacznijmy od książek. W tym roku cel 35 książek nie został osiągnięty. Niemniej… Read More
Zapraszam na krótkie podsumowanie miesiąca. Książki W grudniu skończyłem czytać Mein Kampf. Nudna książka. Ciekawsze fragmenty można by było streścić… Read More