Эффективная сортировка из ядра
MFC все еще используется для некоторых новых разработок, а также для развития технического обслуживания (в том числе внутри Microsoft).
Хотя это может быть на минутку медленнее, чем использование Win32 API напрямую, потеря производительности на самом деле незначительна - редко достигает целого процента. При использовании .NET потеря производительности значительно больше (в моем тестировании редко бывает меньше 10%, причем типично 20-30%, и еще выше для тяжелых вычислений. Например, у меня есть программа это делает вычисления Eigenvector / Eigenvalue на довольно больших массивах. Моя оригинальная версия с использованием C ++ и MFC запускает один тестовый случай в всего за минуту на нашей стандартной тестовой машине. Некоторые из моих коллег решили, что было бы здорово - реализовать его в C #. Их версия занимает почти три минуты на одной и той же машине (четырехъядерный процессор, 16 гигабайт оперативной памяти, так что нет, не «устаревшее» оборудование). Я признаю, что я не слишком внимательно смотрел на их код , поэтому может быть его можно улучшить, но они достойные кодеры, поэтому улучшение 3: 1 кажется мне маловероятным.
С MFC также легко обойти среду и использовать Win32 API напрямую, когда / если вы хотите. С .NET вы можете использовать P / Invoke для этого, но это довольно болезненно для сравнения.
7 ответов
Простой ответ заключается в том, что на этот вопрос нет простого ответа. Есть много ответов, большинство из них довольно сложные - в третьем томе Кнута (например) ему уделяется много места.
Одна вещь, которая становится очевидной при просмотре того, что было сделано, - это то, что вы действительно хотят минимизировать количество запусков, которые вы создаете во время начальной сортировки, и максимизировать длину каждого из них. Для этого обычно требуется прочитать столько данных, сколько поместится в памяти, но вместо того, чтобы просто отсортировать и записать их, вы хотите поместить их в кучу. Затем, когда вы записываете каждую запись, вы читаете В другую запись.
Затем вы проверяете, будет ли эта запись отсортирована до или после записи, которую вы только что выписали. Если вы сортируете после него, вы вставляете его в свою кучу и продолжаете. Если он сортируется раньше, вы вставляете его во вторую кучу.
Вы прекращаете добавлять записи к текущему запуску, когда первая куча полностью пуста, а вторая куча занимает всю вашу память. В этот момент вы повторяете процесс, записывая новый прогон в новый файл.
Это обычно дает значительно более длительные промежуточные прогоны на начальном этапе, поэтому их объединение требует значительно меньших усилий. Предполагая, что входные записи расположены в случайном порядке, вы можете ожидать, что это примерно удвоит длину каждого прогона, но если входные данные даже частично отсортированы, это может использовать преимущества существующего порядка для увеличения длины прогона еще больше.
Кстати, я определенно не изобретал это - я, вероятно, впервые прочитал об этом в Knuth, но, возможно, в Алгоритмы + Структуры данных = Программы (Никлаус Вирт) - оба обсуждают это.
Почему бы не взглянуть на проблему с другой точки зрения. Например, если вы сортируете имена, выполните проход, отсортировав все, что начинается с AF , второй проход строки сортировки, которые начинаются с GM и т. Д. Тогда результаты могут просто добавляйте по порядку. Недостатком является то, что данные должны быть прочитаны с диска C раз.
Почему вы не используете алгоритмы из http://www.amazon.com/Art-Computer-Programming-Sorting-Searching/dp/0201896850 ?
Они довольно хороши и подробно объяснены.
Ник прав, воспользуйтесь внешней сортировкой. Между прочим, ваше C-образное слияние не подразумевает O (N ^ 2). Используйте приоритетную очередь для слияния, и она по-прежнему O (N lg N).
Вы также можете посмотреть алгоритмы игнорирования кеша для сортировки.
Хорошим решением является внешняя сортировка . В частности, обратите внимание на алгоритм внешней сортировки слиянием .
Внешняя сортировка - это термин для класса алгоритмов сортировки, которые могут обрабатывать огромные объемы данных. Внешний сортировка требуется, когда данные сортируемые не укладываются в основную память вычислительного устройства (обычно RAM), а вместо этого они должны находиться в более медленная внешняя память (обычно жесткий диск). Типичный внешний алгоритм сортировки использует сортировку-слияние стратегия, которая начинается с сортировки небольшие подфайлы. Базовый алгоритм состоит из двух этапов: сортировка фаза и фаза слияния. в фаза сортировки, подфайлы могут поместиться в доступное буферное пространство читается в основную память, отсортированную с помощью внутренний алгоритм сортировки, и записывается обратно на диск как временный sorted subfiles. In the merging phase, the sorted subfiles are merged during one or more passes.
Забавно, ведь я слышал этот же вопрос не больше месяца назад ... и ответ, который дал наш местный гуру.
«Используйте сортировку unix command "
Хотя мы с восхищением думали, что это была шутка в ущерб спрашивающему ... оказалось, что это не так. Причина в том, что эти умные ребята уже много думали о том, как решить проблему очень больших файлов, и придумали очень впечатляющую реализацию, которая эффективно использует доступные ресурсы.
Следовательно, если вы не планируете заново изобрести колесо: то есть у вас есть время, и это критично для бизнеса, тогда простое использование сортировки unix , вероятно, будет отличной идеей.
Единственным недостатком является его загадочный синтаксис. Эта страница посвящена командам и различным объяснениям.
Мой личный совет:
Вы выполняете сортировку на месте или создаете новую копию? Если вы выполняете сортировку на месте, то обычно хорошим вариантом будет ввод-вывод с отображением в память. Просто сопоставьте свой файл целиком и выполните сортировку слиянием. ОС будет хранить в памяти такую же часть файла и, в зависимости от набора данных, обычно минимизирует ваш ввод-вывод.
Если вы напишете свой собственный алгоритм сортировки, один трюк состоит в том, чтобы менять направление на обратное после каждого прохода. Итак, если это ваш первый проход, вы начинаете от начала до конца, а затем идете от конца к началу на втором проходе. Если разделить ваши файлы на части A, B, C и D, то после сортировки C и D вы должны объединить C и D, а не возвращаться к A и B. Причина, конечно, в том, что ваша ОС будет перелистывать части файла файлы в память, и вы хотите максимально использовать кэш.