Co oznaczają „dane niepatologiczne”?

14

Wziąłem lekcję algorytmów na Coursera. Tak powiedział profesor w filmie o tabelach skrótów

Prawdą jest, że w przypadku danych niepatologicznych dostaniesz operacje o stałym czasie w odpowiednio zaimplementowanej tabeli skrótów.

Co oznaczają „dane niepatologiczne”? Czy możesz podać jakieś przykłady?

Aleksander Myszow
źródło

Odpowiedzi:

15

Dane patologiczne powinny być danymi, które powodują, że coś pójdzie nie tak w zamierzonym obliczeniu. Można go nazwać patologicznym, gdy jest wystarczająco rzadki w rzeczywistych zastosowaniach, dzięki czemu przez większość czasu wszystko działa OK. Czasami można to uczynić matematycznie bardziej precyzyjnym (na przykład z prawdopodobieństwami), ale użycie słowa patologiczny jest często nieformalne.

Na przykład sałatka pomidorowa i keczup to doskonałe jedzenie, z wyjątkiem osób patologicznych, czyli tych, którzy są uczuleni na pomidory. W niektórych przypadkach może faktycznie zabić. Ale osoby uczulone na pomidory są bardzo rzadkie, dlatego dania pomidorowe są uważane za doskonałe, z wyjątkiem przypadków patologicznych.

O(n2))O(nlgn)O(nlgn)O(lgn)O(n) do sortowania po scaleniu.

O(n2)

Babou
źródło
1
Oprócz sortowania, może być również ważne, aby scalanie było stabilne, podczas gdy szybkie sortowanie nie.
wchargin
11

Dane patologiczne to dane, które spowodują złe działanie algorytmu. W przypadku tablic skrótów dane patologiczne to dane, które powodują kolizje. To oczywiście zależy od użytej funkcji skrótu.

Na przykład, jeśli funkcja mieszania dodaje znaki razem: hash("abcd") = 'a' + 'b' + 'c' + 'd'. Dane patologiczne wyglądają następująco:

{"abcd", "dcba", "cbda", ...}. Każda permutacja "abcd"will hash do tej samej pozycji, więc skończysz z połączoną listą, której starałeś się w pierwszej kolejności uniknąć.

Dane niepatologiczne to dane, które nie są patologiczne.

saadtaame
źródło
-1

inny sposób myślenia na ten temat: klucze skrótu są jak osobne „pojemniki” zawierające dane. można się spodziewać / mieć nadzieję, że dane są równomiernie rozłożone na wszystkie pojemniki, „zrównoważone”. w przypadku danych niepatologicznych każdy pojemnik zawiera / zawiera mniej więcej taką samą ilość danych. jeśli dane są patologiczne (algorytm mieszania klucza wrt), wszystko „gromadzi się” w mniejszej liczbie pojemników, a niektóre pojemniki mają znacznie mniej. jest to nieefektywne, ponieważ czas wyszukiwania zwiększa się (a wydajność spada / zbiega się z czasem wyszukiwania nieposortowanej listy), gdy pojemniki są wypełnione większym. należy zauważyć, że sama zmiana kluczowego algorytmu skrótu może zmienić dane z „patologicznego” na „niepatologiczny” lub odwrotnie, stąd znaczenie algorytmu skrótu.

istnieje również wiele innych algorytmów, dla których można zastosować rozróżnienie między „patologicznym a niepatologicznym”, przy czym w zasadzie „dane patologiczne” sprawiają, że algorytm działa w gorszym przypadku (np. koncepcja jest również stosowana w przypadku algorytmów sortujących). jak widać, jest to koncepcja statystyczna. również w przypadku tego samego problemu dane „patologiczne” dla jednego algorytmu mogą nie być „patologiczne” dla innego. itp.

vzn
źródło