Igła w stogu siana w informatyce

Wolna droga: obejrzeć wszystko

Jeśli nic nie wiesz o tym, gdzie jest igła, jedynym wyborem jest sprawdzanie każdego kawałka siana, aż ją znajdziesz. W informatyce nazywa się to wyszukiwaniem liniowym. Średnio sprawdzasz połowę wszystkiego, zanim ci się uda, a w najgorszym razie wszystko. Zawsze działa, ale czas rośnie proporcjonalnie do wielkości sterty.

Sortowanie zmienia wszystko

Wyobraź sobie teraz, że siano jest ułożone po kolei, jak słowa w słowniku. Sprytniejsza metoda, wyszukiwanie binarne, otwiera w środku, decyduje, w której połowie jest odpowiedź, i odrzuca drugą. Powtórz to, a milion elementów przeszukasz w około 20 krokach. Haczyk w tym, że sterta musi być najpierw uporządkowana, a stóg siana nigdy taki nie jest.

Indeksy: oszukiwanie przez przygotowanie

Bazy danych i wyszukiwarki omijają problem, wykonując ciężką pracę wcześniej. Budują indeks, jak spis na końcu książki, który mówi, na której stronie jest dane słowo. Szukanie staje się szybkie, bo czas został wydany wcześniej. Dla prawdziwego stogu siana nie ma indeksu i właśnie dlatego istnieje to powiedzenie.

Podążanie za sygnałem

Wykrywacz metali jest inny. Nie mówi ci, gdzie jest igła, ale czy się zbliżasz. Wyobraź sobie liczbę, która rośnie, gdy podchodzisz bliżej. Możesz wtedy użyć prostej reguły: zrób krok, sprawdź, czy sygnał się wzmocnił, i idź dalej w kierunku, który go poprawia. Programiści nazywają odmianę tego wspinaczką po wzgórzu (hill climbing) i stoi za nią wiele praktycznych optymalizacji.

W grze sygnał jest obliczany na podstawie twojej odległości od najbliższego kawałka metalu w porównaniu z zasięgiem wykrywacza. Piski przyspieszają, gdy ta liczba zbliża się do 1, więc twoje ucho wykonuje wspinaczkę za ciebie. Więcej w Jak działa wykrywacz metali.

Gdy sygnały zawodzą

Wspinaczka może utknąć. Jeśli blisko igły jest dużo metalowego złomu, najsilniejszy sygnał może zaprowadzić cię do gwoździa. Gra rozwiązuje to, dając wykrywaczom wyższego poziomu zdolność odróżniania igły. Prawdziwe poszukiwania napotykają ten sam problem i używają lepszych czujników albo dodatkowych filtrów.

Stóg jako dane

Stóg w grze sam jest strukturą danych: siatką 88 na 40 na 88 komórek, z których każda ma liczbę oznaczającą gęstość siana. Kopanie to zmienianie liczb, a chunki po 16 komórek utrzymują pracę na małą skalę. Jak to działa, wyjaśnia Jak działa stóg siana.