Эффективная обработка редко пропущенных данных в Haskell - PullRequest
Новая
       16

Эффективная обработка редко пропущенных данных в Haskell

11 голосов
/ 13 ноября 2011

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

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

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

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

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

Edit:

  • Было отмечено, что ответ потенциально зависит от того, какие операции я намереваюсь выполнить с данными. В настоящее время кажется более удобным хранить каждое наблюдение в одном векторе, а не в каждой переменной. Поскольку записи в векторе, таким образом, будут ссылаться на разные переменные, «сложенные» операции маловероятны.
  • Я предполагаю, 2. будет ли внутри автоматически сохраняться вектор «действительного бита», как 3. автоматически, если это необходимо, поэтому 3. может быть отброшено?

1 Ответ

6 голосов
/ 13 ноября 2011

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

...