Что касается правильного присвоения имени, merge не должен удалять дубликаты, так как его имя предполагает, что он является частью mergesort, который должен их сохранять. Union является лучшим именем для такой операции, которая видит множества, представленные (здесь) путем увеличения списков уникальных чисел, ограничение, которое следует сохранить, удаляя дубликаты, которые могут быть получены только из обоих ее аргументов .
Возвращаясь к самой проблеме, давайте напишем ее символически как
S<sub>235</sub> = {1} ∪ 2*S<sub>235</sub> ∪ 3*S<sub>235</sub> ∪ 5*S<sub>235</sub>
Преждевременная реализация - мать всего зла! (подождите, что?) Мы даже не будем пытаться установить, как именно эти 1013 * выполняют свою работу, даже в каком порядке. Или даже сколько терминов есть:
S<sub>23</sub> = {1} ∪ 2*S<sub>23</sub> ∪ 3*S<sub>23</sub>
или даже
S<sub>2</sub> = {1} ∪ 2*S<sub>2</sub>
Теперь это выглядит достаточно просто. Мы можем даже искусственно реализовать объединение A и B здесь просто, сначала взяв все элементы A, а затем - B. И здесь все будет работать нормально, потому что в этом левом входе ∪ есть только один элемент:
{1} ----∪-->--->--S₂--.--->S₂
/ \
\______*2_______/
---<----<---
Как это работает? 1 входит в ∪ сумматор , выходит из него первым, безоговорочно (Обратите внимание, это обнаруженное требование важно, поскольку если ∪ пришлось проверить оба из его аргументов сразу же мы получим бесконечный цикл, черная дыра в Арскоте Хаскелла), разделенный на две части с помощью . сплиттера , а затем первой копии 1 продолжается до выходной точки, в то время как вторая копия 1 возвращается назад через множитель *2, результирующий 2 вводит обратно ∪ на этот раз справа, без сопротивления с помощью чего-либо слева (которое в настоящее время уже пусто) и продолжается таким же образом, поэтому 2 переходит к выходной точке, затем 4, затем 8 и т. д. и т. д.
Другими словами, S₂ содержит все элементы {1}; плюс все элементы {1}, которые один раз прошли через множитель *2; и дважды; и три раза; и так далее и тому подобное - все полномочия 2 в порядке возрастания:
S<sub>2</sub> = {1} ∪ 2*{1} ∪ 2*2*{1} ;; == {1, 2, 4, 8, 16, 32, ...}
∪ 2*2*2*{1}
∪ 2*2*2*2*{1}
∪ ..........
Два S₂ на диаграмме одинаковы, потому что то, что мы выкачиваем из него в точке разделения, не влияет на это.
Разве это не было весело?
Так как же нам добавить к нему кратные 3? Один из способов сделать это -
S<sub>23</sub> = S<sub>2</sub> ∪ 3*S<sub>23</sub>
{1} ----∪-->--->--S₂--.---S₂----∪-->--->--S₂₃--.--->S₂₃
/ \ / \
\______*2_______/ \______*3________/
---<----<--- ---<----<---
Здесь 1 из S₂ входит во второй ∪ сумматор и переходит к выходной точке S₂₃, а также обратно через множитель *3, превращаясь в 3. Теперь второй ∪ имеет 2,4,8,... и 3,... в качестве входов; 2 проходит и превращается в 6. Далее ∪ имеет 4,8,16,... и 3,6,...; 3 проходит. Далее 4; и т. д. и т. д. и т. д. и т. п.
Таким образом, все элементы S₂ являются частью S₂₃, но также и все элементы S₂, которые прошли через множитель *3 один раз, дважды и т. Д., - все полномочия 2 и 3 , умноженные вместе в порядке возрастания:
S<sub>23</sub> = S<sub>2</sub> ∪ 3*S<sub>2</sub> ∪ 3*3*S<sub>2</sub> ;; = S<sub>2</sub> ∪ 3*( S<sub>2</sub> ∪ 3*S<sub>2</sub>
∪ 3*3*3*S<sub>2</sub> ;; ∪ 3*3*S<sub>2</sub>
∪ 3*3*3*3*S<sub>2</sub> ;; ∪ 3*3*3*S<sub>2</sub>
∪ .......... ;; ∪ ........ ) !!
Почему увеличивается порядок? Как? Да ведь это ответственность ∪! Здравствуйте, еще одно обнаруженное требование. Что бы ни поступало в него с обеих сторон, оно должно производить меньший элемент перед большим.
А что делать, если оба равны? Нужно ли нам заниматься этим вопросом в этой схеме здесь? Может ли это когда-нибудь случиться здесь?
Не может. И поэтому мы можем реализовать ∪ здесь как merge, а не как union (но помните первое обнаруженное требование! - оно все еще действует? Необходимо?) С помощью добавление новых случаев ). Merge должно быть более эффективным, чем union, поскольку оно не касается случая равных.
А для кратных 5 тоже? Мы продолжаем, как
S<sub>235</sub> = S<sub>23</sub> ∪ 5*S<sub>235</sub>
{1} ----∪-->--->--S₂--.---S₂----∪-->--->--S₂₃--.---S₂₃----∪-->--->--S₂₃₅--.--->S₂₃₅
/ \ / \ / \
\______*2_______/ \______*3________/ \_______*5________/
---<----<--- ---<----<--- ---<----<---
- Описывает ли это код из книги? _______
- Описывает ли это код, который примерно в два раза быстрее кода из книги?_______
- Почему это примерно в два раза быстрее, чем код из книги?_______
- Этот ответ ваш вопрос?_______
- Помогает ли это вам ответить на ваш вопрос?_______
(заполните пробелы).
См. Также:
И блок-схема обработки сигналов для кода книги:
1 --->---\
cons-stream ->-- S ---.---> S
/----->---->--- *2 --->---\ / |
/ union ->--/ /
.-->-- *3 -->--\ / /
| union ->--/ /
.-->-- *5 -->--/ /
\ /
\__________<__________<__________<_________<_______________/
, где "объединение" удаления дубликатов называется merge вкнига.