Я хотел бы создать простую SML-программу, которая проходит по списку слева направо. Допустим, у меня есть список из N элементов K разных типов. Например, список 1 3 1 3 1 3 3 2 2 1
имеет 10 номеров 3(1,2,3)
типов.
Я хотел бы пройтись по этому списку слева направо и остановиться, когда найду все K разных чисел. В этом случае я бы остановился сразу после того, как наткнулся на первые 2.
Это можно сделать, разделив список на начало и конец на каждом шаге и обработав элемент заголовка. Однако как я могу отслеживать различные числа, которые я нашел?
Это можно сделать в C/C++, просто удерживая счетчик и логический массив с K элементами. Если я наткнусь на элемент с bool[i]=false
, я сделаю это верным и counter=counter+1
.
Однако утверждается, что массивы - не лучший вариант для SML, поэтому мне было интересно, нужно ли мне использовать другую структуру данных или мне нужно создавать новую функцию, чтобы каждый раз проверять, видел ли я этот элемент раньше (это будет стоить в временная сложность).
how could I keep track of the different numbers I have found?
[...] in C/C++ by [...] a boolean array with K elements
Абстрактно я бы назвал структуру данных, которую вы хотите, набор бит.
Я дам вам два ответа: один с использованием разреженного контейнера и один с использованием битового набора.
Я бы использовал список, чтобы отслеживать элементы, которые вы уже видели:
fun curry f x y = f (x, y)
val empty = []
fun add x set = curry op:: x set
fun elem x set = List.exists (curry op= x) set
fun seen k xs =
let fun seen_ 0 _ _ = true
| seen_ _ [] _ = false
| seen_ k (x::xs) set =
if elem x set
then seen_ k xs set
else seen_ (k-1) xs (add x set)
in seen_ k xs empty end
Вы также можете использовать сбалансированное двоичное дерево в качестве типа набора; это уменьшит поиск до О (lg п). Преимущество использования фактического контейнера (списка или дерева), а не битового массива, заключается в том, что разреженные массивы/матрицы. Это работает для ''a list
s.
[...] boolean array with K elements [...]
If i stumble upon an element i[...]
До этого момента вы не говорили, что элементы всегда представляют собой целые числа без знака от 0 до К-1, что было бы требованием, если они должны быть представлены уникальным индексом в массиве длиной К.
SML имеет модуль/тип, называемый Word
/ word
для целых чисел без знака (слова). При добавлении этого ограничения входной список должен иметь тип word list
, а не ''a list
.
Когда вы создаете массив примитивных типов во многих императивных компилируемых языках, вы получаете изменяемый Массивы распакованный. Тип Множество SML также является изменяемым, но каждый bool
в таком массиве будет помещен в коробку.
Простой способ получить массив битов неизменный, распакованный — использовать побитовые операции над IntInf
(SML/NJ; реализации различаются); он будет автоматически увеличиваться, когда бит переворачивается. Это может выглядеть так:
fun bit x = IntInf.<< (1, x)
val empty = IntInf.fromInt 0
fun add x set = IntInf.orb (set, bit x)
fun elem x set = IntInf.> (IntInf.andb (set, bit x), 0)
Функция seen
будет такой же.
Тот факт, что k
рекурсивно уменьшается, а set
растет динамически, означает, что вы не ограничены элементами в диапазоне [0,К-1], как это было бы в случае массива размером К.
Пример использования:
- seen 5 [0w4, 0w2, 0w1, 0w9];
val it = false : bool
- seen 5 [0w1, 0w2, 0w3, 0w4, 0w8];
val it = true : bool
Это решение использует много памяти, если элементы большие:
- seen 1 [0w100000000];
*eats my memory slowly*
val it = true : bool
Дополнительные вещи, которые вы могли бы сделать:
structure BitSet = struct ... end
, который инкапсулирует абстрактный тип с операциями empty
, add
и elem
, скрывая конкретную реализацию (будь то IntInf.int
, bool Array.array
или ''a list
).fun fold_until f e xs = ...
, которая извлекает схему рекурсии seen_
, чтобы избежать ручной рекурсии; обычного foldl
недостаточно, так как он продолжается до тех пор, пока список не станет пустым. Вы можете построить это, используя возвращаемый тип с учетом ошибок или используя исключения.@Labyrinthian: я не знаю, что это такое? :)
Спасибо за ваш ответ, он многое прояснил! Какова временная сложность второго решения?