от
Предположим, у меня есть список
Int
, в котором элементы, как известно, ограничены, и список, как известно, не длиннее своего диапазона, поэтому вполне возможно, что он не будет содержать дубликаты. Как я могу проверить наиболее быстро, так ли это? Я знаю о
nubOrd
. Это довольно быстро. Мы можем пройти наш список и посмотреть, станет ли он короче. Но эффективность
nubOrd
все еще не линейна. Моя идея состоит в том, что мы можем обменять пространство на эффективность времени. Обязательно, мы должны выделить битовое поле, столь же широкое как наш диапазон, и затем пройти по списку, отмечая записи, соответствующие значениям элементов списка. Как только мы пытаемся перевернуть бит, который уже равен 1, мы возвращаем False. Требуется только (чтение сравнение запись) * длина списка. Нет бинарных деревьев поиска, нет ничего. Разумно ли попробовать подобную конструкцию в Хаскеле?              

Ваш ответ

Отображаемое имя (по желанию):
Конфиденциальность: Ваш электронный адрес будет использоваться только для отправки уведомлений.
Анти-спам проверка:
Чтобы избежать проверки в будущем, пожалуйста войдите или зарегистрируйтесь.
Добро пожаловать на сайт ByNets, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...