карта основных алгоритмов сортировки
Сравнение алгоритмов сортировки с хабра:
Посетитель (Visitor)
Поведенческий паттерн проектирвоания, который описывает операцию, выполняемую с каждым объектом из некоторой структуры.
Паттерн посетитель позволяет определить новую операцию, не изменяя классы этих объектов.
Посетитель — это Команда
Реализация паттерна проектирования Посетитель на python
# coding: utf-8 class FruitVisitor(object): """Посетитель""" def draw(self, fruit): methods = { Apple: self.draw_apple, Pear: self.draw_pear, } draw = methods.get(type(fruit), self.draw_unknown) draw(fruit) def draw_apple(self, fruit): print 'Яблоко' def draw_pear(self, fruit): print 'Груша' def draw_unknown(self, fruit): print 'Фрукт' class Fruit(object): """Фрукты""" def draw(self, visitor): visitor.draw(self) class Apple(Fruit): """Яблоко""" class Pear(Fruit): """Груша""" class Banana(Fruit): """Банан""" visitor = FruitVisitor() apple = Apple() apple.draw(visitor) # Яблоко pear = Pear() pear.draw(visitor) # Груша banana = Banana() banana.draw(visitor) # Фрукт
Шаблонный метод (Template Method)
Поведенческий паттерн проектирования, который позволяет подклассам расширять шаги алгоритма, не меняя при этом структуру, объявленную в базовом классе.
Также можно рассматривать как частный случай паттерна Фабричный метод
реализация паттерна проектирвоания Шаблонный метод на python
# coding: utf-8 class ExampleBase(object): def template_method(self): self.step_one() self.step_two() self.step_three() def step_one(self): raise NotImplementedError() def step_two(self): raise NotImplementedError() def step_three(self): raise NotImplementedError() class Example(ExampleBase): def step_one(self): print 'Первый шаг алгоритма' def step_two(self): print 'Второй шаг алгоритма' def step_three(self): print 'Третий шаг алгоритма' example = Example() example.template_method() # Первый шаг алгоритма # Второй шаг алгоритма # Третий шаг алгоритма
Стратегия (Strategy)
Поведенческий паттерн, который позволяет определить семейство алгоритмов и вынести их в собственные классы, которые называются — стратегии.
Реализация паттерна проектирования Стратегия на python
# coding: utf-8 class ImageDecoder(object): @staticmethod def decode(filename): raise NotImplementedError() class PNGImageDecoder(ImageDecoder): @staticmethod def decode(filename): print 'PNG decode' class JPEGImageDecoder(ImageDecoder): @staticmethod def decode(filename): print 'JPEG decode' class GIFImageDecoder(ImageDecoder): @staticmethod def decode(filename): print 'GIF decode' class Image(object): @classmethod def open(cls, filename): ext = filename.rsplit('.', 1)[-1] if ext == 'png': decoder = PNGImageDecoder elif ext in ('jpg', 'jpeg'): decoder = JPEGImageDecoder elif ext == 'gif': decoder = GIFImageDecoder else: raise RuntimeError('Невозможно декодировать файл %s' % filename) byterange = decoder.decode(filename) return cls(byterange, filename) def __init__(self, byterange, filename): self._byterange = byterange self._filename = filename Image.open('picture.png') # PNG decode Image.open('picture.jpg') # JPEG decode Image.open('picture.gif') # GIF decode
Снимок (Memento)
Поведенческий паттерн, позволяющий получить копию состояния объекта во времени, причем копию делает сам объект.
Реализация паттерна Снимок на python
# coding: utf-8 class Memento(object): """Хранитель""" def __init__(self, state): self._state = state def get_state(self): return self._state class Caretaker(object): """Опекун""" def __init__(self): self._memento = None def get_memento(self): return self._memento def set_memento(self, memento): self._memento = memento class Originator(object): """Создатель""" def __init__(self): self._state = None def set_state(self, state): self._state = state def get_state(self): return self._state def save_state(self): return Memento(self._state) def restore_state(self, memento): self._state = memento.get_state() originator = Originator() caretaker = Caretaker() originator.set_state('on') print 'Originator state:', originator.get_state() # Originator state: on caretaker.set_memento(originator.save_state()) originator.set_state('off') print 'Originator change state:', originator.get_state() # Originator change state: off originator.restore_state(caretaker.get_memento()) print 'Originator restore state:', originator.get_state() # Originator restore state: on
Наблюдатель (Observer)
Поведенческий паттерн проектирования, позволяющий подписчику отслеживать изменения издателя.
Пример реализации паттерна Наблюдатель на python
# coding: utf-8 class Subject(object): """Субъект""" def __init__(self): self._data = None self._observers = set() def attach(self, observer): # подписаться на оповещение if not isinstance(observer, ObserverBase): raise TypeError() self._observers.add(observer) def detach(self, observer): # отписаться от оповещения self._observers.remove(observer) def get_data(self): return self._data def set_data(self, data): self._data = data self.notify(data) def notify(self, data): # уведомить всех наблюдателей о событии for observer in self._observers: observer.update(data) class ObserverBase(object): """Абстрактный наблюдатель""" def update(self, data): raise NotImplementedError() class Observer(ObserverBase): """Наблюдатель""" def __init__(self, name): self._name = name def update(self, data): print '%s: %s' % (self._name, data) subject = Subject() subject.attach(Observer('Наблюдатель 1')) subject.attach(Observer('Наблюдатель 2')) subject.set_data('данные для наблюдателя') # Наблюдатель 2: данные для наблюдателя # Наблюдатель 1: данные для наблюдателя
передаёт запрос последовательно через цепочку потенциальных получателей, ожидая, что какой-то из них обработает запрос.
устанавливает косвенную одностороннюю связь от отправителей к получателям.
убирает прямую связь между отправителями и получателями, заставляя их общаться опосредованно, через себя.
передаёт запрос одновременно всем заинтересованным получателям, но позволяет им динамически подписываться или отписываться от таких оповещений.
Посредник (Controller)
Поведенческий паттерн проектирования позволяет разлепить связи между классами и берет на себя функцию связывания. Классы будут общаться через класс-посредник.
Пример реализации паттерна Посредник на python
# coding: utf-8 class WindowBase(object): def show(self): raise NotImplementedError() def hide(self): raise NotImplementedError() class MainWindow(WindowBase): def show(self): print 'Show MainWindow' def hide(self): print 'Hide MainWindow' class SettingWindow(WindowBase): def show(self): print 'Show SettingWindow' def hide(self): print 'Hide SettingWindow' class HelpWindow(WindowBase): def show(self): print 'Show HelpWindow' def hide(self): print 'Hide HelpWindow' class WindowMediator(object): def __init__(self): self.windows = dict.fromkeys(['main', 'setting', 'help']) def show(self, win): for window in self.windows.itervalues(): if not window is win: window.hide() win.show() def set_main(self, win): self.windows['main'] = win def set_setting(self, win): self.windows['setting'] = win def set_help(self, win): self.windows['help'] = win main_win = MainWindow() setting_win = SettingWindow() help_win = HelpWindow() med = WindowMediator() med.set_main(main_win) med.set_setting(setting_win) med.set_help(help_win) main_win.show() # Show MainWindow med.show(setting_win) # Hide MainWindow # Hide HelpWindow # Show SettingWindow med.show(help_win) # Hide MainWindow # Hide SettingWindow # Show HelpWindow
Состояние (State)
Это поведенческий паттерн, при котором объект в разных своих состояниях ведет себя по-разному. Набор состояний обычно конечен и определен.
Реализация паттерна состоит в введении классов-состояний с общим интерфейсом.
Реализация паттерна проектирования Состояние на python
# coding: utf-8 class LampStateBase(object): """Состояние лампы""" def get_color(self): raise NotImplementedError() class GreenLampState(LampStateBase): def get_color(self): return 'Green' class RedLampState(LampStateBase): def get_color(self): return 'Red' class BlueLampState(LampStateBase): def get_color(self): return 'Blue' class Lamp(object): def __init__(self): self._current_state = None self._states = self.get_states() def get_states(self): return [GreenLampState(), RedLampState(), BlueLampState()] def next_state(self): if self._current_state is None: self._current_state = self._states[0] else: index = self._states.index(self._current_state) if index < len(self._states) - 1: index += 1 else: index = 0 self._current_state = self._states[index] return self._current_state def light(self): state = self.next_state() print state.get_color() lamp = Lamp() [lamp.light() for i in range(3)] # Green # Red # Blue [lamp.light() for i in range(3)] # Green # Red # Blue
Итератор (Iterator)
Это один из поведенческих паттернов проектирования/, созданный для обхода коллекций и упрощения классов хранения данных, вынося реализацию (или разные реализации) обхода в другие классы.
# coding: utf-8 class IteratorBase(object): """Базовый класс итератора""" def first(self): """Возвращает первый элемент коллекции. Если элемента не существует возбуждается исключение IndexError.""" raise NotImplementedError() def last(self): """Возвращает последний элемент коллекции. Если элемента не существует возбуждается исключение IndexError.""" raise NotImplementedError() def next(self): """Возвращает следующий элемент коллекции""" raise NotImplementedError() def prev(self): """Возвращает предыдущий элемент коллекции""" raise NotImplementedError() def current_item(self): """Возвращает текущий элемент коллекции""" raise NotImplementedError() def is_done(self, index): """Возвращает истину если элемент с указанным индексом существует, иначе ложь""" raise NotImplementedError() def get_item(self, index): """Возвращает элемент коллекции с указанным индексом, иначе выбрасывает исключение IndexError""" raise NotImplementedError() class Iterator(IteratorBase): def __init__(self, list_=None): self._list = list_ or [] self._current = 0 def first(self): return self._list[0] def last(self): return self._list[-1] def current_item(self): return self._list[self._current] def is_done(self, index): last_index = len(self._list) - 1 return 0 <= index <= last_index def next(self): self._current += 1 if not self.is_done(self._current): self._current = 0 return self.current_item() def prev(self): self._current -= 1 if not self.is_done(self._current): self._current = len(self._list) - 1 return self.current_item() def get_item(self, index): if not self.is_done(index): raise IndexError('Нет элемента с индексом: %d' % index) return self._list[index] it = Iterator(['one', 'two', 'three', 'four', 'five']) print [it.prev() for i in range(5)] # ['five', 'four', 'three', 'two', 'one'] print [it.next() for i in range(5)] # ['two', 'three', 'four', 'five', 'one']