Обход списка до достижения определенного критерия - PullRequest
Новая
       36

Обход списка до достижения определенного критерия

0 голосов
/ 28 марта 2019

Я хотел бы создать простую программу SML, которая пересекает список слева направо. Допустим, у меня есть список из N элементов K различных типов. Например, список 1 3 1 3 1 3 3 2 2 1 имеет 10 чисел 3(1,2,3) типов..

Я хотел бы пройтись по этому списку слева направо и остановиться, когда найду все K разных чисел. В этом случае я остановлюсь сразу же после того, как наткнусь на первые 2.

Это можно сделать, разделив список по заголовку и хвосту на каждом шаге и обработав элемент заголовка. Но как мне отследить найденные мной разные числа?

Это можно сделать в C/ C ++, просто держа счетчик и логический массив с K элементами.Если я натыкаюсь на элемент i с bool[i]=false, то я делаю его истинным и counter=counter+1.

Хотя утверждается, что массивы - не лучший вариант для SML, поэтому мне было интересно, нужно ли мне использовать другие данныеили если мне нужно создать новую функцию, чтобы каждый раз проверять, видел ли я этот элемент раньше (это стоило бы сложности во времени).

1 Ответ

2 голосов
/ 29 марта 2019

как я могу отслеживать разные найденные числа?

[...] в C / C ++ от [...] логический массив с K элементами

Абстрактно я бы назвал структуру данных, которую вы хотите бит установлен .

Я дам вам два ответа,один использует разреженный контейнер, а другой - набор битов.

Разреженный

Я бы использовал список для отслеживания элементов, которые вы уже видели: 

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

Вы также можете использовать сбалансированное двоичное дерево в качестве типа набора;это уменьшит поиск до O (lg n) .Преимущество использования фактического контейнера (списка или дерева), а не битового массива, заключается в том, что разреженных массивов / матриц .Это работает для ''a list с.

Бит установлен

[...] логический массив с K элементами [...]

Если я наткнусь на элемент i [...]

До этого момента вы не сказаличто элементы всегда являются целыми числами без знака от 0 до K-1 , что является обязательным требованием, если они должны быть представлены уникальным индексом в массиве длиной K .

SML имеет модуль / тип, называемый Word / word для целых чисел без знака ( слов ).При добавлении этого ограничения список ввода должен иметь тип word list, а не ''a list.

Когда вы создаете массив примитивных типов во многих императивных, скомпилированных языках, вы получаете изменчивый без коробки массивы .Тип SML Array также является изменяемым, но каждый 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, K-1] , что было бы в случае с массивом размером K .

Пример использования:

- 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 недостаточно, поскольку оно продолжается до тех пор, пока список не станет пустым.Вы могли бы построить это, используя тип возврата с учетом ошибок или используя исключения.
  • Рассмотрите Фильтры Блума .
...