Spis treściKliknij link, aby przejść do wybranego miejsca
Ta treść została automatycznie przetłumaczona z ukraińskiego.
Eksplozja kombinatoryczna to zjawisko, gdy liczba możliwych wariantów gwałtownie rośnie wraz ze wzrostem liczby elementów. Wszystko wydaje się niewinne, dopóki nie zaczynasz liczyć.
Na przykład:
- Mamy 3 rodzaje pizzy i chcemy wybrać 2 — to tylko 3 warianty.
- Ale jeśli mamy 20 dodatków i chcemy wybrać dowolną kombinację? Już ponad milion wariantów!
W matematyce jest to związane z kombinatoryką - działem, który bada sposoby wyboru i porządkowania obiektów.
W programowaniu, sztucznej inteligencji czy teorii gier eksplozja kombinatoryczna to prawdziwy wróg. Na przykład, w szachach liczba możliwych pozycji po 5 ruchach to ponad 69 miliardów. Przeszukiwanie wszystkich wariantów jest po prostu niemożliwe — potrzebne są optymalizacje, heurystyki i strategie omijające.
Eksplozja kombinatoryczna to sytuacja, w której "wszystko policzyć" staje się niemożliwe, ponieważ wariantów jest zbyt wiele.
Termin brzmi nieco dramatycznie - i nie bez powodu. Dobrze ilustruje, jak szybko z prostego zadania może wyrosnąć prawdziwa matematyczna burza.
Eksplozja kombinatoryczna przy tworzeniu nowej klasy w Ruby
W Ruby (jak i w innych językach OOP) eksplozja kombinatoryczna może wystąpić, gdy próbujesz przewidzieć wszystkie możliwe kombinacje zachowań obiektów lub zależności między parametrami klasy.
Przykład nieudanego projektowania klasy Notification:
class Notification
def initialize(user:, type:, channel:, urgency:)
@user = user
@type = type # :comment, :like, :mention, :follow
@channel = channel # :email, :sms, :push
@urgency = urgency # :low, :medium, :high
end
def deliver
# logic based on all combinations
end
end
Teraz mamy:
- 4 typy zdarzeń (:comment, :like, :mention, :follow)
- 3 kanały wysyłania (:email, :sms, :push)
- 3 poziomy pilności (:low, :medium, :high)
To już 4 × 3 × 3 = 36 kombinacji, z których każda potencjalnie wymaga osobnej logiki dostarczania (deliver). Dodaj jeszcze 2 parametry — i już setki wariantów, które trudno przetestować i utrzymać.
Jak uniknąć eksplozji kombinatorycznej?
1. Obiekty-strategie:
class EmailNotificationStrategy; def deliver; ...; end; end class PushNotificationStrategy; def deliver; ...; end; end
2. Podziel odpowiedzialność (SOLID):
- Notification nie powinien wiedzieć wszystkiego o wszystkich kanałach.
- Każdy kanał sam realizuje swoje zachowanie.
3. Metaprogramowanie (trzeba robić z głową):
rubyCopyEditdefine_method("deliver_#{channel}_#{type}_#{urgency}") do
# ...
end
Jednak jeśli metod jest 100+, to tylko pogorszy sytuację. Eksplozja kombinatoryczna w klasie występuje, gdy próbujesz "wszyć" do klasy zbyt wiele wariantów logiki związanych z kombinacją parametrów. Z czasem prowadzi to do nieczytelnego kodu, błędów i bólu.
