Z doby do kilku minut, czyli sortowanie i szukanie binarne

Utworzono: 10 kwietnia 2001 Zaktualizowano: 1 października 2026

Dobór respondentów liczył się całą noc i jeszcze kawałek dnia, a wystarczyły dwa algorytmy ze studiów.

Jak przyszedłem, rządził Pascal i skrypty do doboru prób do badań. Skrypty były napisane na pascalowych kolekcjach i przeszukiwane liniowo, czyli jak coś miało się znaleźć w czymś, to dla każdego elementu leciało się po całej drugiej liście, O(n²).

Przy małych próbach nikt tego nie zauważał, przy dużych mój szef przychodził rano do pracy z laptopem jak z pizzą, bo dobór respondentów nadal się kręcił od poprzedniego dnia.

Byłem świeżo po algorytmach i znałem dwie rzeczy, które tu pasowały idealnie: sortowanie i przeszukiwanie binarne. Listę sortuję raz, a potem zamiast przechodzić ją za każdym razem od początku, szukam w niej, dzieląc na pół, więc przy każdym wyszukiwaniu zamiast n porównań jest log n.

pascal

{ było: dla każdego respondenta cała lista od początku }
for i := 1 to RespCount do
  for j := 1 to UsedCount do
    if Resp[i].Id = Used[j] then
      Skip(i);

{ jest: sortuję raz, potem szukam binarnie }
SortIds(Used, UsedCount);
for i := 1 to RespCount do
  if BinarySearch(Used, UsedCount, Resp[i].Id) then
    Skip(i);

Coś, co liczyło się dobę, liczy się teraz kilka minut, szef przestał nosić laptopa jak pizzę, a ja zdobyłem u niego uznanie.

#pascal #algorytmy #wydajnosc