Доктор Джон Харроп, с которым я связался по электронной почте, объяснил, что происходит:
Проблема заключается в том, что программа была оптимизирована для Python.Конечно, это часто встречается, когда программист лучше знаком с одним языком, чем с другим.Вам просто нужно выучить другой набор правил, определяющих, как следует оптимизировать программы на F # ... Несколько вещей бросились в глаза, например, использование цикла «for i in 1..n do» вместо «for» для i= 1 до n do "цикл (который в целом быстрее, но не имеет существенного значения), многократное выполнение List.mapi для списка, чтобы имитировать индекс массива (который без необходимости распределял промежуточные списки) и использование вами F # TryGetValue для Dictionary, который выделяетизлишне (.NET TryGetValue, который принимает ссылку, в общем быстрее, но не так много здесь)
... но настоящей проблемой-убийцей оказалось использование хеш-таблицы для реализации плотной 2D-матрицы,Использование хеш-таблицы является идеальным в Python, потому что его реализация хеш-таблицы была чрезвычайно хорошо оптимизирована (о чем свидетельствует тот факт, что ваш код Python работает так же быстро, как F #, скомпилированный с нативным кодом!), Но массивы являются гораздо лучшим способом представления плотныхматрицы, особенно если вам нужно значение по умолчанию, равное нулю.
Самое смешное, что когда я впервые кодировал этот алгоритм, я DID использовал таблицу - я изменил реализациюдля ясности в словарь (избегание проверок границ массива сделало код проще - и намного легче рассуждать).
Джон преобразовал мой код (обратно :-)) в его версию массива , и он работает со скоростью 100x.
Мораль истории:
- F # Словарь нуждается в работе ... при использовании кортежей в качестве ключей скомпилированный F # медленнее, чем интерпретируемый Pythonхеш-таблицы!
- Очевидно, но повторение не повредит: более чистый код иногда означает ... намного более медленный код.
Спасибо,Джон - высоко ценится.
РЕДАКТИРОВАТЬ : тот факт, что замена Dictionary на Array делает F #, наконец, работающим на скоростях, ожидаемых для запуска скомпилированного языка, не отменяет необходимостиисправить в скорости словаря (я надеюсь, что F # люди из MS читают это).Другие алгоритмы зависят от словарей / хэшей и не могут быть легко переключены на использование массивов;заставлять программы страдать от «скоростей интерпретатора» всякий раз, когда кто-то использует словарь, возможно, является ошибкой.Если, как некоторые говорили в комментариях, проблема не в F #, а в словаре .NET, я бы сказал, что это ... ошибка в .NET!
EDIT2 : Самое ясное решение, которое не требует алгоритма переключения на массивы (некоторые алгоритмы просто не поддаются этому), состоит в том, чтобы изменить это:
let optimalResults = new Dictionary<_,_>()
на следующее:
let optimalResults = new Dictionary<_,_>(HashIdentity.Structural)
Это изменение заставляет код F # работать в 2,7 раза быстрее, что в итоге превосходит Python (в 1,6 раза быстрее).Странно то, что кортежи по умолчанию используют структурное сравнение, поэтому в принципе сравнения, выполняемые словарем по ключам, одинаковы (со структурой или без нее).Доктор Харроп теоретизирует, что разница в скорости может быть связана с виртуальной диспетчеризацией: «AFAIK, .NET мало что делает для оптимизации виртуальной диспетчеризации, а стоимость виртуальной диспетчеризации чрезвычайно высока на современном оборудовании, потому что это« вычисляемый переход », которыйпереводит счетчик программы в непредсказуемое место и, следовательно, подрывает логику прогнозирования ветвлений и почти наверняка приведет к сбросу и перезагрузке всего конвейера ЦП ".
Простыми словами, как предложено ДономSyme ( посмотрите на 3 нижних ответа ), «будьте недвусмысленны в отношении использования структурного хеширования при использовании ссылочных ключей в сочетании с коллекциями .NET».(Доктор Харроп в комментариях ниже также говорит, что мы должны всегда использовать структурные сравнения при использовании коллекций .NET).
Уважаемая команда F # в MS, если есть способ автоматически исправитьэто, пожалуйста, сделайте.