Какова стандартная структура данных OCaml с самым быстрым повторением?
Я ищу контейнер, который обеспечивает самые быстрые незаказанные повторения через инкапсулированные элементы. Другими словами, "добавьте однажды, выполняйте итерации много раз".
Есть ли один среди стандартных модулей OCAML, который достаточно быстр (таким образом, что дальнейшая оптимизация его была бы бесполезна)? Или некоторые сторонние GPL-готовые?
AFAIK там является всего одним компилятором OCaml, таким образом, понятие того, чтобы быть быстрым более или менее ясно...
... Но после того, как я видел несколько ответов, это появляется, это не. Конечно, существует много структур данных, которые позволяют O (n) повторение через контейнер размера n. Но задачей, которую я решаю, является один из тех, где различие между O (n) и O (2n) имеет значение ;-).
Я также вижу, что Массивы и Списки предоставляют ненужную информацию о порядке добавленных элементов, в котором я не нуждаюсь. Возможно, в "функциональном мире" там существует структуры данных, таким образом, который может торговать этой информацией некоторое время итеративной скорости.
В C я напрямую выбрал бы простой массив. Вопрос, что я должен выбрать в OCaml?
5 ответов
]Вы вряд ли будете делать лучше, чем встроенные массивы и списки, так как они вручную закодированы на C, если только вы не привязаны к своей собственной родной реализации итератора. Массив будет вести себя почти точно так же, как массив в C (смежный блок памяти, содержащий последовательность значений элементов), возможно, с некоторыми дополнительными указателями из-за бокса. Список реализован точно так же, как и следовало ожидать: как ячейки со значением и указателем "следующий". Массивы дадут вам лучшее местоположение для небоксовых типов (особенно []float[]s, которые имеют суперспециальную реализацию небоксовых элементов).[
]Информацию о реализации массивов и списков смотрите в []Раздел 18. 3 руководства OCaml[] и файлы []byterun/mlvalues.h[], []byterun/array.c[], и []byterun/alloc.c[] в исходном коде OCaml.[
][]Из вопросара[]: действительно, []Array[] оказался самым быстрым решением. Однако он только на 7% превзошел []List[]. Возможно, это было связано с тем, что тип элемента массива был недостаточно простым: это был алгебраический тип. []Hashtbl[], как и ожидалось, выполнил в 4 раза хуже.[
]Итак, я выберу []Array[] и принимаю этот. Хорошо.[
Все общие структуры данных являются итерабельными во времени O(n), поэтому различия между структурами данных будут только постоянными (и, весьма вероятно, не значительными).
По крайней мере, списки и массивы позволяют проводить итерации без значительных накладных расходов. Не могу представить себе ситуацию, когда это было бы недостаточно быстро
.Чтобы знать наверняка, нужно измерить . На основании машинных инструкций компилятор, скорее всего, сгенерирует, я бы попробовал массив, затем список.
Доступ к элементу массива требует проверки границ, адресной арифметики, а доступ к загрузке
Доступ к заголовку списка требует загрузки, проверки на пустой список, и загрузки при известном смещении времени компиляции.
Детали которого быстрее, вероятно, зависят от вашего приложения и того, что еще происходит на вашей машине. Они также зависят от типа элементов; например, если это числа с плавающей точкой, ocamlopt может быть достаточно умён, чтобы создать массив без ящиков, что сохранит вам уровень индирекции.
Другие распространённые структуры данных, такие как хэш-таблицы или сбалансированные деревья, обычно требуют, чтобы вы выделили какой-нибудь контекст где-то, чтобы отслеживать, где вы находитесь. В массиве отслеживание требует только целочисленного индекса; в списке отслеживание требует одного указателя. Я думаю, что это будет трудно сделать в другой структуре данных.
Наконец, обратите внимание, что может быть только один OCaml компилятор, но он имеет два обратных конца: байткод и нативный код. Естественно, если Вас волнует такой уровень производительности, то Вы используете версию компилятора native-code ocamlopt. Верно?
Пожалуйста, сделайте измерения и отредактируйте результаты в своем вопросе.
.Массив - линейная часть памяти с элементами, посещаемыми в последовательном порядке - лучше всего использует кэш данных L1 процессора.
]Не забывайте о []Bigarray[]s, они наиболее близки к массивам C (просто плоская часть памяти), но не могут содержать произвольных OCaml-значений. Также рассмотрим возможность отключения проверки границ (unsafe_set/get). И, конечно же, сначала нужно составить профиль.[