Структура данных с самым быстрым поиском элементов в F #? - PullRequest
Новая
       9

Структура данных с самым быстрым поиском элементов в F #?

2 голосов
/ 03 сентября 2010

Я пытаюсь написать небольшую библиотеку линейной алгебры F # (для приложений с небольшими матрицами, поэтому память не является проблемой), и мне было интересно, какая структура данных имеет лучшие характеристики производительности с точки зрения времени поиска элементов, так как мне нужно это для определения матричных операций?

Ответы [ 3 ]

9 голосов
/ 03 сентября 2010

Мне немного непонятно, о чем меня спрашивают.

Массивы, конечно, O (1), и поэтому я ожидаю, что они правильный ответ.(Эмпирическое правило Брайана: если вы хотите, чтобы что-то было быстрым, то ответ одинаков для всех языков - используйте массив структур.)

Если вам нужно что-то более разреженное, есть .NET Dictionaryи HashSet классы (которые используют хэши) и типы F # Map и Set (которые используют деревья / сравнение).Dictionary, вероятно, следующая лучшая попытка.

Но, конечно, я ожидаю, что это либо во многом зависит от специфики (плотность, местность / структура доступа, ...), либо это не имеет значения вообще (другие факторы подавляют его).

В конце дня, как для каждого вопроса об эффективности: показатель .

9 голосов
/ 03 сентября 2010

Если «маленький» является 2- или 3-мерным, то строит. Для немного большего «малого» используйте ссылочный тип с явными компонентами. Если количество элементов превышает 30, используйте один массив и выполните i + n*j самостоятельно. Избегайте 2D-массивов .NET, потому что они в несколько раз медленнее, чем необходимо. Действительно избегайте тип F # Matrix для поэлементных операций, потому что он делает что-то безумное, как динамическая диспетчеризация (на порядок медленнее). Массивы массивов хороши, но самостоятельная индексация позволяет оптимизировать индексацию JIT.

2 голосов
/ 03 сентября 2010

Наиболее эффективным представлением, вероятно, будет изменяемый массив (двумерный должен работать довольно хорошо). Поиск по индексу - O (1), так что он настолько эффективен, насколько это возможно. Несмотря на то, что массив является изменяемым, вы все равно можете использовать его для разработки неизменяемого (функционального) типа матрицы - все, что вам нужно сделать, это избежать изменения массива. Компилятор не будет проверять это, но структура данных может быть чисто функциональной для пользователя.

Примерно так может быть хорошей отправной точкой: 

// Constructor takes the data of the matrix
type Matrix(data:float[,]) =
  // Expose data only for private purposes (cannot be mutated by the user!)
  member private x.Data = data
  // All operations create new array as the result
  static member (+) (a:Matrix, b:Matrix) = 
    // TODO: Check that arrays have the same size
    let res = Array2D.init (a.Data.GetLength(0)) (a.Data.GetLength(1)) 
      (fun i j -> a.Data.[i, j] + a.Data.[i, j])
    new Matrix<_>(res)
...