Sleepsort – bzdura czy geniusz? JAVA8

Cześć! Cieszę się, że mnie odwiedziłeś/aś. Zanim przejdziesz do artykułu chciałbym zwrocić Ci uwagę na to, że ten artykuł był pisany kilka lat temu (2015-01-02) miej więc proszę na uwadzę że rozwiązania i przemyślenia które tu znajdziesz nie muszą być aktualne. Niemniej jednak zachęcam do przeczytania.

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;
  }
 
 
}
Dzięki za wizytę,
Mateusz Mazurek
Mateusz M.

Ostatnie wpisy

Podsumowanie: luty i marzec 2024

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

2 tygodnie ago

Podsumowanie: styczeń 2024

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

3 miesiące ago

Podsumowanie roku 2023

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

4 miesiące ago

Podsumowanie: grudzień 2023

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

4 miesiące ago

Praca zdalna – co z nią dalej?

Cześć, ostatnio w Internecie pojawiło się dużo artykułów, które nie były przychylne pracy zdalnej. Z drugiej strony większość komentarzy pod… Read More

4 miesiące ago

Podsumowanie: listopad 2023

Zapraszam na krótkie podsumowanie miesiąca. Książki W listopadzie dokończyłem cykl "Z mgły zrodzony" Sandersona. Tylko "Stop prawa" mi nie do… Read More

5 miesięcy ago