Предыдущая часть:
Как говорилось ранее, merge sort это алгоритм внешней сортировки с поcледовательным доступом.
Если посмотреть на большинство исходников merge sort, размещённых на ресурсах по программированию, то можно заметить, что ничем внешним и последовательным там не пахнет. Реализуется обычный внутренний алгоритм, часто через рекурсию, и поэтому он становится очень похож на quicksort.
Да
Я сразу делал упор на внешнюю сортировку и последовательный доступ, эмулировав его через массив и текущую позицию в массиве.
Но
Когда данные читаются из файла (или в общем случае потока), то после чтения текущая позиция в файле автоматически сдвигается на количество прочитанных байт.
За текущую позицию отвечала переменная pos, и я делал так: сравнивал a[pos_a] и b[pos_b], и в случае необходимости чтения следующего элемента увеличивал pos_a или pos_b.
Но сравнения в одной и той же позиции могли происходить несколько раз, а с точки зрения эмуляции файла каждое обращение к a[pos_a] означает чтение из файла, и значит позиция pos_a должна увеличиваться каждый раз.
Следовательно, правильнее сделать так: прочитать из файла a (b) число и сохранить в переменной va (vb), сдвинуть позицию pos_a (pos_b), и затем можно сравнивать сколько угодно раз переменные va и vb.
va = a[pos_a]
pos_a += 1
vb = b[pos_b]
pos_b += 1
Вроде бы небольшое изменение, но оно стало для меня путёвкой в ад на целую неделю – именно столько я пытался заставить работать алгоритм в таком варианте.
Да что вообще происходит?
Нет, он не трудный. Просто наличие буферной переменной порождает огромную кучу непредвиденных условий.
Я поначалу просто не верил, что нужно действительно вводить так много условий. Мне казалось, что какие-то циклы тут лишние, а какие-то операции можно сократить. Я переписывал код полностью с нуля, использовал разные подходы, выворачивал его наизнанку, менял концепции, но каждый раз приходил к одному и тому же результату.
Код не работал без большого числа проверок. И тому причиной было всего лишь введение буферных переменных на чтение из файла.
И опять же – всё это можно было абстрагировать и инкапсулировать, скажем, сделать класс Stream с операциями чтения и записи. Но я стремился к максимально простому коду. А он никак не получался.
В конце концов я смирился с тем, что короткого кода не получится. И сосредоточился на других аспектах.
Не выходя из потока
Алгоритму требуется три вложенных цикла: первый отсчитывает размер последовательности от 1 до N. Второй работает, добывая последовательности из файлов. И третий проходит собственно по текущей последовательности.
Неприятные ситуации возникают, когда в конце файла получаются последовательности не полного размера, а также когда одна из последовательностей заканчивается раньше другой. В этом случае неиспользованный остаток последовательности надо дописать в результат. Это обычно делают отдельной операцией, но я хотел сделать один непрерывный цикл следующим образом:
- Читаем (по необходимости) переменные va и vb из потоков A и B, сравниваем, пишем однy из них в результат. Если закончилась одна из последовательностей, то продолжаем делать то же самое, но теперь ситуация меняется так, что из её потока читать прекращаем, сравнивать прекращаем, и в результат пишется только другая последовательность.
- Когда обе последовательности закончились, ситуация меняется так, что чтение обоих последовательностей начинается сначала.
- Всё это сопровождается проверками на нестандартный конец последовательности.
Бинго
В качестве шутки я представил, что потоки A и B играют в бинго. Цель каждого – отдать всю свою последовательность в результат и выкрикнуть "Бинго!", то есть изменить ситуацию.
В начале им выдаётся длина последовательности, каждому своя. Там учитывается, сколько элементов реально осталось в потоке, так что длина, например, может быть и нулевой.
На этот раз я писал на Питоне:
Здесь просто: длина последовательности chunk_size считается от текущей позиции pos, и если конец потока настал раньше, то возвращаем ту доступную длину, которая осталась.
Семафоры
Развивая мысль дальше, я решил применить что-то вроде шаблона producer-consumer:
Потоки A и B выступают как поставщики данных, а выходной поток как потребитель данных.
В каждый момент времени нужно понимать, какой поток готов к чтению данных, и какие данные готовы к записи в выходной поток.
Для этого я решил применить, опять же вольно обращаясь с терминологией, семафоры.
Например, переменная read_a разрешает чтение из потока A, а переменная write_a сигнализирует о готовности переменной va для записи в выходной поток. Аналогичные переменные заводятся для потока B.
Здесь я прокомментирую некоторые куски кода. Что мы имеем в самом начале последовательности, когда нужно прочитать первые элементы из двух потоков:
Далее начинаем читать из потоков, если это разрешено:
Одновременно с чтением семафор записи write_a или write_b устанавливается в True: у нас уже есть данные для записи. Обратите внимание, что чтение честно увеличивает pos_a или pos_b на 1, эмулируя поток. Нельзя войти в ту же реку дважды.
Если данные из обоих потоков доступны, их нужно сравнить и выбрать меньшее число:
Далее поток, у которого оказалось меньшее число, я буду называть ведущим, а другой поток ведомым.
Выбрав меньшее число, я не пишу его в выходной поток, а всего лишь выключаю семафор ведомого потока на запись. Сама запись будет позже. Также текущее значение ведомого семафора записи сохраняется в ведомом семафоре чтения, но здесь нет скрытого смысла – это просто сохранение, и его можно было бы сделать в другую переменную. Просто в данном месте семафоры чтения уже не нужны, а плодить лишние переменные я не хочу.
Ситуация теперь такая: если были доступны два числа, то после сравнения остался включённым только ведущий семафор на запись. А если было доступно только одно число (у другого потока случилось бинго), то здесь и сравнивать ничего не нужно.
Пишем в выходной поток в соответствии с доступными семафорами:
После записи в выходной поток (который неинтуитивно называется input, так как изначально был входным) ведущий семафор записи выключается – число потрачено, писать больше нечего. Также на 1 уменьшается счётчик бинго ведущего потока. Семафор чтения зависит от состояния счётчика бинго – если есть что читать, то он становится активен. Мы готовы читать следующее число вместо потраченного.
А вот семафор записи ведомого потока восстанавливается из ранее сохранённого состояния. Он выключался, чтобы дать доступ к записи только ведущему потоку, а сейчас, когда поток отработал, можно вернуть его назад. Если у ведомого потока было число для записи, то оно остаётся и теперь.
Семафор чтения ведомого потока выключается, так как его число не было потрачено, и на следующем шаге читать ничего не надо.
Собственно, это примерно всё. Данная структура находится в цикле до достижения бинго обоими потоками, и заворачивается в два внешних цикла, которые отсчитывают последовательности и длины последовательностей, но основная логика – вот она.
Полную версию кода можно посмотреть тут:
