В этой статье мы по-новому взглянем на решение проблемы внешней сортировки, применяя технику, основанную на ответственности. Каждая ответственность в этой конкретной проблеме инкапсулируется таким образом, чтобы упростить разработку, основанную на тестировании, и оставить нам код, который является гибким и поддерживаемым.
Надеемся, что к концу этой статьи вы узнаете радикальный подход к решению захватывающих проблем.
Внешняя сортировка
Внешняя сортировка — увлекательная проблема, поскольку вы ограничены объемом памяти, доступной для сортировки входного файла.
В этой статье Википедии говорится о сути проблемы:
Внешняя сортировка — это термин для класса алгоритмов сортировки, которые могут обрабатывать большие объемы данных. Внешняя сортировка требуется, когда сортируемые данные не помещаются в основную память вычислительного устройства (обычно ОЗУ) и вместо этого они должны находиться в более медленной внешней памяти (обычно на жестком диске).
Я ограничиваю задачу случайно сгенерированным входным файлом размером M и размером массива N в котором N * N = M чтобы все было просто. Также необходимо проверить нашу работу, поэтому мы напишем утилиту проверки, чтобы убедиться, что сортировка прошла успешно.
Ответственность за дизайн
Основной подход в этом шаблоне проектирования состоит в том, чтобы разбить проблему на контракты, которые затем станут нашими публичными API. Каждый контракт будет включать отдельную роль в решении. Главное здесь — сосредоточиться на том, что делает каждая инкапсуляция, а не на том, как она это делает.
В этой статье с описанием Ruby подробно описывается суть этого подхода:
В дизайне, ориентированном на ответственность, системы делятся на наборы поведения, которые они должны реализовать. Цель этого раздела — сформулировать описание поведения системы в терминах множества взаимодействующих процессов, причем каждый процесс играет отдельную роль.
Я разбил проблему на писателя, читателя и очередь. Writer и Reader предоставят мне общий API для чтения или записи в постоянное хранилище. Поскольку мне приходится разбивать большой основной входной файл на меньший кэш, Queuer будет служить точкой доступа для каждого отдельного файла для внешней сортировки. Интересное наблюдение здесь заключается в том, что роли обычно называют в честь глаголов, поскольку они предназначены для того, чтобы выходить и что-то делать. В это время обратите внимание, как каждая инкапсуляция не связана с тем, как это делается.
Итак, давайте разберемся с этим:
module FIO class Writer def open(file) end def append(n) end def close end end class Reader def open(file) end def read end def close end end class Queuer def open(file) end def [](index) end def close end end end
Тестовая разработка
Теперь, когда у нас есть готовые контракты, мы можем начать думать о написании тестов. Что касается разработки через тестирование, я бы хотел сосредоточить ваше внимание на том, как мы могли бы концептуально решить эту проблему. Ключевым моментом здесь является сосредоточение внимания на каждом контракте и на том, каким должно быть правильное поведение. К счастью, Ruby, будучи динамическим языком, делает это очень легко, поэтому нам не нужно тратить время на насмешки над классами и написание кода интерфейса.
Итак, давайте поговорим о том, что нам нужно.
Чтобы сгенерировать основной случайно сгенерированный входной файл, нам нужна какая-то утилита Export . Например:
class Export def initialize(writer) @writer = writer end def out(max, file_name) end end
Для внешней сортировки нам понадобится утилита Sort :
class Sort def initialize(reader, writer, queuer) @reader = reader @writer = writer @queuer = queuer end def external(max, chache_size, file_in, file_out) end end
Наконец, чтобы выполнить проверку в конце, нам нужна утилита Check :
class Check def initialize(reader) end def is_sorted(max, file_out) end end
Это должно сделать это.
Отношения между этими служебными объектами и нашими контрактами напоминают отношения модели клиент / сервер. Здесь сервер вводится как зависимость. Затем клиентский код вызывает публичный API или контракт для выполнения запросов.
По аналогии, данные, которые вытекают из наших контрактов, похожи на водоснабжение, которое мы получаем в нашем доме. Утилиты похожи на необходимую сантехнику в нашем доме, которая выполняет услуги. Следует иметь в виду, что при подходе, основанном на ответственности, потоки данных проходят через систему, а не помещаются в одно монолитное место.
Обратите внимание, что на данном этапе процесса разработки нас не интересуют какие-либо детали реализации. Наши юнит-тесты будут разработаны для руководства творческим процессом.
Модульные тесты
Для целей этой статьи я использую mocha чтобы помочь мне написать тесты.
В тестах мы определим M = 9 и N = 3, ,. Наконец, следует выполнить тестовое имя файла, например, для ввода и out для вывода.
Давайте концептуализируем нашу экспортную утилиту:
class ExportTest < Test::Unit::TestCase def test_export_out # Mock dependency and add expectations writer = mock() writer.expects(:open).with('in').at_least_once writer.expects(:append).with(anything).times(9) writer.expects(:close).at_least_once # Call utility Export.new(writer).out(9, 'in') end end;class ExportTest < Test::Unit::TestCase def test_export_out # Mock dependency and add expectations writer = mock() writer.expects(:open).with('in').at_least_once writer.expects(:append).with(anything).times(9) writer.expects(:close).at_least_once # Call utility Export.new(writer).out(9, 'in') end end
Чтобы успешно пройти этот тест, мы можем сделать:
def out(max, file_name) @writer.open(file_name) max.times { @writer.append(Random.rand(10)) } @writer.close end
Тот же шаблон можно применить к утилите проверки:
class CheckTest < Test::Unit::TestCase def test_check_is_sorted reader = mock() reader.expects(:open).with('out').at_least_once reader.expects(:read).times(9).returns(0) reader.expects(:close).at_least_once target = Check.new(reader).is_sorted(9, 'out') assert target end;class CheckTest < Test::Unit::TestCase def test_check_is_sorted reader = mock() reader.expects(:open).with('out').at_least_once reader.expects(:read).times(9).returns(0) reader.expects(:close).at_least_once target = Check.new(reader).is_sorted(9, 'out') assert target end
Чтобы успешно пройти этот тест, мы можем сделать:
def is_sorted(max, file_out) return true if max <= 1 sorted = true @reader.open(file_out) a = @reader.read (max - 1).times do b = @reader.read sorted = false if a > b a = b end @reader.close sorted end
Для нашего финального теста нам нужно реализовать внешнюю сортировку. Первым делом нужно разбить входной файл на отсортированные куски. Это означает, что мы читаем из нашего входного файла 9 раз. Мы также будем писать в отдельные файлы чанка в общей сложности 9 раз. Наконец, мы запишем окончательный результат в выходной файл в общей сложности 9 раз, что дает нам всего 18.
У нашего Queuer есть нюансы, которые учитываются в этом тесте. Каждый индекс объекта очереди даст мне доступ к отдельному чанку. Я использую очередь, чтобы предоставить данные для сортировки, пока они не заканчиваются. В тестовом случае это будет 9 плюс 3, так как он должен сказать мне, когда у него больше ничего нет.
Итак, вот тест:
class SortTest < Test::Unit::TestCase def test_sort_external writer = mock() reader = mock() queuer = mock() reader.expects(:open).with('in').at_least_once reader.expects(:read).times(9) reader.expects(:close).at_least_once writer.expects(:open).with('out').at_least_once writer.expects(:open).with('in1').at_least_once writer.expects(:open).with('in2').at_least_once writer.expects(:open).with('in3').at_least_once writer.expects(:append).with(anything).times(18) writer.expects(:close).at_least_once queuer.expects(:open).with(3, 'in').at_least_once queuer.expects(:[]).with(anything).times(12).returns(0) queuer.expects(:close).at_least_once Sort.new(reader, writer, queuer).external(9, 3, 'in', 'out') end end;class SortTest < Test::Unit::TestCase def test_sort_external writer = mock() reader = mock() queuer = mock() reader.expects(:open).with('in').at_least_once reader.expects(:read).times(9) reader.expects(:close).at_least_once writer.expects(:open).with('out').at_least_once writer.expects(:open).with('in1').at_least_once writer.expects(:open).with('in2').at_least_once writer.expects(:open).with('in3').at_least_once writer.expects(:append).with(anything).times(18) writer.expects(:close).at_least_once queuer.expects(:open).with(3, 'in').at_least_once queuer.expects(:[]).with(anything).times(12).returns(0) queuer.expects(:close).at_least_once Sort.new(reader, writer, queuer).external(9, 3, 'in', 'out') end end;class SortTest < Test::Unit::TestCase def test_sort_external writer = mock() reader = mock() queuer = mock() reader.expects(:open).with('in').at_least_once reader.expects(:read).times(9) reader.expects(:close).at_least_once writer.expects(:open).with('out').at_least_once writer.expects(:open).with('in1').at_least_once writer.expects(:open).with('in2').at_least_once writer.expects(:open).with('in3').at_least_once writer.expects(:append).with(anything).times(18) writer.expects(:close).at_least_once queuer.expects(:open).with(3, 'in').at_least_once queuer.expects(:[]).with(anything).times(12).returns(0) queuer.expects(:close).at_least_once Sort.new(reader, writer, queuer).external(9, 3, 'in', 'out') end end;class SortTest < Test::Unit::TestCase def test_sort_external writer = mock() reader = mock() queuer = mock() reader.expects(:open).with('in').at_least_once reader.expects(:read).times(9) reader.expects(:close).at_least_once writer.expects(:open).with('out').at_least_once writer.expects(:open).with('in1').at_least_once writer.expects(:open).with('in2').at_least_once writer.expects(:open).with('in3').at_least_once writer.expects(:append).with(anything).times(18) writer.expects(:close).at_least_once queuer.expects(:open).with(3, 'in').at_least_once queuer.expects(:[]).with(anything).times(12).returns(0) queuer.expects(:close).at_least_once Sort.new(reader, writer, queuer).external(9, 3, 'in', 'out') end end
Чтобы пройти тест, мы можем сделать:
def external(max, cache_size, file_in, file_out) capacity = Array.new(cache_size) # Break file_in into chunks @reader.open(file_in) max.times do |index| capacity[index % cache_size] = @reader.read if is_end_of_chunk(index, max, cache_size) capacity.sort! # Use naming convention, eg, file_in1 @writer.open(file_in + ((index + 1) / cache_size).to_s) cache_size.times { |i| @writer.append(capacity[i]) } @writer.close end end @reader.close # Merge chunks onto file_out @writer.open(file_out) @queuer.open(cache_size, file_in) cache_size.times { |i| capacity[i] = @queuer[i] } max.times do lowest = min_index(capacity) @writer.append(capacity[lowest]) capacity[lowest] = @queuer[lowest] end @queuer.close @writer.close end private def is_end_of_chunk(index, max, size) (!index.zero? && ((index + 1) % size).zero?) || max == 1 end def min_index(arr) index = 0 (1..arr.length - 1).each do |i| next if arr[i].nil? index = i if arr[index].nil? || arr[index] > arr[i] end index end
Когда мы запускаем эти тесты, в вашу файловую систему ничего не записывается. Опять же, смысл в том, чтобы концептуально протестировать наш код, чтобы убедиться в правильном поведении. Модульное тестирование — это искусство тестирования изолированного кода без пересечения функциональных границ, например, записи в файл или отправки сетевого запроса.
Вывод
Разработка, основанная на тестировании, приносит много проблем в размышлениях о решениях с очень абстрактной точки зрения. Тем не менее, решения, основанные на ответственности, выигрывают от того, что уже выполняют для вас много тяжелой работы, разделяя проблемы и обеспечивая хорошо продуманные уровни абстракции.
Я опустил детали реализации в качестве упражнения для читателя. Если вы заинтересованы, я разместил остальную часть кода на GitHub .
Счастливого взлома!