Подтвердить что ты не робот

Эффективное обращение с незначительно отсутствующими данными в Haskell

Я пытаюсь использовать Haskell для анализа данных. Поскольку мои наборы данных достаточно велики (сотни тысяч и, возможно, миллионы наблюдений), я бы идеально хотел бы использовать структуру распакованных данных для повышения эффективности, скажем, Data.Vector.Unboxed.

Проблема заключается в том, что данные содержат некоторые отсутствующие значения. Я хочу избежать кодирования их как "99" или подобных, потому что это просто уродливый хак и потенциальный источник ошибок. С точки зрения новичков Haskell я могу подумать о следующих вариантах:

  • Коробочный вектор распакованных значений Maybe. Что-то вроде (пожалуйста, исправьте, если не так):
    data myMaybe a = Nothing | Just {-# UNPACK #-} !a
  • Несвободный вектор (unboxable) кортежей, с булевым элементом, указывающим на отсутствие:
    newtype instance Data.Vector.Unboxed.Vector (MyDatum a) = MyDatum (Data.Vector.Unboxed.Vector (Bool,a))
    Это может быть тот же подход, который выбрал OP этот вопрос (по модулю Int для Bool), но единственный ответ, похоже, явно не адресован вопрос о недостающих значениях/разреженности (вместо этого сосредоточиться на том, как представлять весь массив unboxed, а не как вектор с короткими векторами без коробки).
  • Кортеж для распакованных векторов, один со значениями, другой с индексами, в которые должны быть введены отсутствующие значения, или длины прогона не пропущенных значений или некоторая эквивалентная информация. Это может быть предпочтительнее варианта 2. Если пропуски скудны?

Я пытаюсь остаться в векторном представлении, а не что-то вроде этого, потому что это недостающие значения, которые являются разреженными, а не данными.

Приветствуются любые комментарии относительно относительных достоинств/осуществимости/недоступности/доступности/вероятной производительности этих параметров или, действительно, указателей на совершенно разные альтернативы!

Edit:

  • Было указано, что ответ потенциально зависит от того, какие операции я намерен выполнять на данных. На данный момент удобнее хранить каждое наблюдение в одном векторе, а не в каждой переменной. Так как записи в векторе будут ссылаться на разные переменные, "fold" -подобные ops маловероятны.
  • Я предполагаю, что 2. будет внутренне хранить "действительный бит" вектор à la 3. автоматически, если это необходимо, так что 3. можно было бы отбросить?
4b9b3361

Ответ 1

Я бы выбрал вариант 3, но вы не должны использовать вектор для хранения недостающих индексов: это дает вам время поиска O(nMissing), которое необоснованно медленное, если отсутствующие данные не являются крайне разреженными. Data.IntMap должен хорошо выполнять эту работу, тогда вы можете легко использовать функцию member, чтобы проверить, указывает ли индекс на отсутствующее наблюдение. Хэш-таблицы еще лучше, но, вероятно, не нужны.