Проход по списку до тех пор, пока не будет выполнен определенный критерий

Я хотел бы создать простую 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, поэтому мне было интересно, нужно ли мне использовать другую структуру данных или мне нужно создавать новую функцию, чтобы каждый раз проверять, видел ли я этот элемент раньше (это будет стоить в временная сложность).

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
0
106
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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 lists.

Набор бит

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

Спасибо за ваш ответ, он многое прояснил! Какова временная сложность второго решения?

user11210665 29.03.2019 20:24

@Labyrinthian: я не знаю, что это такое? :)

sshine 01.04.2019 08:18

Другие вопросы по теме