Cортировка файла в C++. Кто как делает?
Google://external sort
Google://external sorthttp://en.wikipedia.org/wiki/External_sorting
Алгоритм я понимаю.
В несколько нитей выполняется блочная сортировка файла на диске.
Но детали реализации почти всегда платформо-зависимы.
Хочется взять что-то типа буста, вызвать функцию и получить результат.
Нет такого?
Пока ссылки уводят на какие-то внешние ресурсы:
http://cis.stvincent.edu/html/tutorials/swd/extsort/extsort....
Можно ли им доверять? Я поэтому и спросил "кто чем пользуется и как делает".
Спасибо.
Хочется взять что-то типа буста, вызвать функцию и получить результат.std::sort же!
В несколько нитей выполняется блочная сортировка файла на диске.>на диске
Обычно это означает, что реализация будет зависеть от платформы.
Ты что, там же на ДИСКЕ, будет от марки и названия производителя зависеть!
Ты что, там же на ДИСКЕ, будет от марки и названия производителя зависеть!Стёб засчитан
По делу: ищу аналог вызову sort через shell.
Чем проще, тем лучше.
Ну и статистику под это дело собрать - кто чем пользуется интересно.
В несколько нитей выполняется блочная сортировка файла на диске. Обычно это означает, что реализация будет зависеть от платформы.Ну ёлки, пусть зависит.
Неужели нет кроссплатформенной либы, умеющей работать с разными файловыми системами?
умеющей работать с разными файловыми системами?что она должна уметь?
Работа со всеми файловыми системами делается через системные вызовы unix, они почти не отличаются в linux и freebsd. Какого рода кроссплатформенность вы ожидаете? Что плохо с sort?
Стеб не над тобой был, а над Sevurra, потому что с диска можно читать хоть через libc (stdio.h и вперед который есть и под виндой и под никсами и где только нет.
Какого рода кроссплатформенность вы ожидаете? Что плохо с sort?Простейшую (чтобы на Linux и FreeBSD всё работало).
Да с sort (в смысле с утилитой) всё замечательно. Просто как использовать её код в моём коде?
Если сортируются большие объёмы данных, можно просто вызвать её и всё. Или это плохо?
Дорогой саркастичный друг!
Наверное, ты знаешь, что даже у fopen из libc по стандарту в параметрах есть флаг b, который работает в винде и игнорируется юникс-системами. Возможно, ты слышал, что ещё у винды в fopen есть, например, куча других интересных флагов, о которых я, например, ни малейшего понятия не имею, как они поведут себя в линуксе. Типа вот этого, да:
Возможно, ты также в курсе, что в винде для обращения к файлу в том же fopen согласно вышеупомянутой документации надо использовать UNC-пути с бэкслэшем в качестве разделителя каталогов, а в юникс-системах для этого используется слэш.
А в остальном, конечно, можно стебаться над неграмотным мной, ведь это всё совершенно не имеет никакого отношения к платформе.
Наверное, ты знаешь, что даже у fopen из libc по стандарту в параметрах есть флаг b, который работает в винде и игнорируется юникс-системами. Возможно, ты слышал, что ещё у винды в fopen есть, например, куча других интересных флагов, о которых я, например, ни малейшего понятия не имею, как они поведут себя в линуксе. Типа вот этого, да:
fopen(&fp, "file.txt", "rt, ccs=UNICODE");
Возможно, ты также в курсе, что в винде для обращения к файлу в том же fopen согласно вышеупомянутой документации надо использовать UNC-пути с бэкслэшем в качестве разделителя каталогов, а в юникс-системах для этого используется слэш.
А в остальном, конечно, можно стебаться над неграмотным мной, ведь это всё совершенно не имеет никакого отношения к платформе.
ну и причем тут пути и сортировка файла? Ты программист или кто? Ты не можешь в своей программе отделить открытие файла от реализации алгоритма сортировки? Тогда вообще не вопи здесь.
А зачем использовать microsoft-specific расширения fopen? Используйте posix.
> Используйте posix.
И оп! Не работает под окнами )
И оп! Не работает под окнами )
Ну так не стой под окнами-то.
Мы, кажется, говорим про внешнюю сортировку, работающую с диском? Так она требует открытия/записи файлов с диска, что требует обращения к упомянутым функциям. И это — платформо-зависимо. Ты можешь написать в своей программе функции-врапперы для работы с диском, умница, но по сути своей они будут частью реализации и поэтому реализация будет платформо-зависимой. Или можешь юзать какую-нибудь стороннюю высокоуровневую либу, которая будет за тебя делать всякие toNativePath и предоставлять единый интерфейс. Только такая либа внезапно не является частью стандартных библиотек.
Поэтому если ты живёшь в реальном мире, а не идеальном — где принцессы какают бабочками, а у программистов есть бесконечность времени, оружияи практика вынести каждую отдельно взятую функцию в независимую библиотеку, сразу включаемую во все ОС — то да, ты не напишешь платформо-независимую реализацию внешней сортировки. Потому что говорить «у ченя реализация платформо-независимая, только она требует вот этого класса, который и работает с платформой, или вот этой либы, которую я же написал и которая работает с платформой» — это как минимум глупо.
Поэтому если ты живёшь в реальном мире, а не идеальном — где принцессы какают бабочками, а у программистов есть бесконечность времени, оружияи практика вынести каждую отдельно взятую функцию в независимую библиотеку, сразу включаемую во все ОС — то да, ты не напишешь платформо-независимую реализацию внешней сортировки. Потому что говорить «у ченя реализация платформо-независимая, только она требует вот этого класса, который и работает с платформой, или вот этой либы, которую я же написал и которая работает с платформой» — это как минимум глупо.
это две-три строчки, которые теоретически зависят от платформы (тем более, что я не вижу причин не сработать программе, в которой используются только fopen("name","rw" fread и fwrite на окнах, линуксе и бзде а сама реализация сортировки если на нее посмотреть от системы зависеть вообще не будет.
используются только fopen("name","rw")Гадить временными файлами ты, очевидно, планируешь прямо в cwd? Иначе мы возвращаемся как минимум к UNC-путям в винде, если не (как в общем-то и надо делать по уму) определению tmp-каталога для текущей системы.
Ах, да, настоящий гуру конечно и тут сделает "платформо-независимо" — потребует от пользователя указывать каталог для временных файлов, причём обязательно с соответствующим слэшем на конце.
Ну, тогда любой код, написанный на C платформо-зависимый, так как собирается платформо-зависимым компилятором, да?
Тебе же написали, что сам код не зависит от платформы. Либы - это либы, ты их не пишешь, а используешь, у тебя на входе имя файла (и тебе пофигу, какие там слеши, это входные данные ты его открываешь (и тебе пофигу, как именно происходит чтение). В чём проблема? Уж на что есть проблемы с переносимостью при разработке, напрмер, гуёв или тех же низкоуровневых библиотек, так так, блин, даже в такой абстрактной задаче проблему придумал.
Да, можно написать кроссплатформенно, и да, для этого не нужно написать ни одной дополнительной строчки кода.
Тебе же написали, что сам код не зависит от платформы. Либы - это либы, ты их не пишешь, а используешь, у тебя на входе имя файла (и тебе пофигу, какие там слеши, это входные данные ты его открываешь (и тебе пофигу, как именно происходит чтение). В чём проблема? Уж на что есть проблемы с переносимостью при разработке, напрмер, гуёв или тех же низкоуровневых библиотек, так так, блин, даже в такой абстрактной задаче проблему придумал.
Да, можно написать кроссплатформенно, и да, для этого не нужно написать ни одной дополнительной строчки кода.
Можно ли им доверять? Я поэтому и спросил "кто чем пользуется и как делает"Я для этого пользуюсь алгоритмом External Merge Sort, замечательно описанном по ссылке в вики. Реализация - своя. Кроссплатформенность мне была не актуальна, так что писал через fstream. Сортировка в памяти - квиксортом.
Ты передергиваешь. Когда ты пишешь код, ты не завязываешься на компилятор. Если завязываешься (используя всякие плюшки типа студийного макроса __DEBUG или gcc-ных аттрибутов то да, это платформо-зависимый код.
Если ты используешь стандартные средства языка, которые по стандарту одинаково везде работают, то ты платформо-независим. И если бы дело ограничивалось только входным файлом, то код можно было бы сделать платформо-независимым.
Для внешней сортировки тебе надо писать ещё и промежуточный результат. И либо ты ввиду отсутствия стандартных средств языка пишешь платформо-зависимую реализацию, либо ты пишешь говнокод, требуя от пользователя вводить ещё и каталог для временных файлов.
Если ты используешь стандартные средства языка, которые по стандарту одинаково везде работают, то ты платформо-независим. И если бы дело ограничивалось только входным файлом, то код можно было бы сделать платформо-независимым.
Для внешней сортировки тебе надо писать ещё и промежуточный результат. И либо ты ввиду отсутствия стандартных средств языка пишешь платформо-зависимую реализацию, либо ты пишешь говнокод, требуя от пользователя вводить ещё и каталог для временных файлов.
Ок. Допустим я выбираю 1й вариант. И не хочу напрягать пользователя. Какую бы мне выбрать временную папку для каждой из следующих осей?
Android OS
A/UX
BSD/OS
HP-UX
IBM AIX
INTEGRITY
IRIX
LynxOS
Mac OS X
Apple iOS
Minix
MPE/iX
OpenSolaris
OpenVMS
QNX
RTEMS
Solaris
UnixWare
velOSity
VxWorks
И второй вопрос. Почему для этого не подходит, например %filename%~?
Android OS
A/UX
BSD/OS
HP-UX
IBM AIX
INTEGRITY
IRIX
LynxOS
Mac OS X
Apple iOS
Minix
MPE/iX
OpenSolaris
OpenVMS
QNX
RTEMS
Solaris
UnixWare
velOSity
VxWorks
И второй вопрос. Почему для этого не подходит, например %filename%~?
И второй вопрос. Почему для этого не подходит, например %filename%~?Потому что на ФС без поддержки LFN, например, у тебя могут возникнуть проблемы прям сразу.
Ещё можно гипотетически предположить, что есть ФС, не поддерживающая символ "~" в именах файлов, почему бы нет. Может оказаться, что уже имеется файл с таким именем (файл бэкапа в линуксах, ага затирать его — это некрасиво.
Что касается выбора каталога под вышеперечисленные ОСи — это и есть платформозависимость. На каких-нибудь солярисах наверняка есть свой /tmp/, который и надо использовать, а где-то типа ведроида придётся таки генерить уникальное имя в текущей папке.
При этом для генерации уникального файла в позиксе надо использовать mkstemp, а в винде _mktemp_s.
Поразительно, сколько всего вылезает, да?
Ты заморачиваешься. Но если быть совсем дотошным
_mktemp_s принимает имя (ну, шаблон). Что ты туда поставишь? Спросишь, какая там fs стоит?
UPD. И, я так понял, проблема опять в кривожопой винде? для всех остальных решение общее, так?
_mktemp_s принимает имя (ну, шаблон). Что ты туда поставишь? Спросишь, какая там fs стоит?
UPD. И, я так понял, проблема опять в кривожопой винде? для всех остальных решение общее, так?
Не обязательно. На ведроиде, например, сделали свой libc с bj&sl, местами, насколько я знаю, несовместимый с оригиналом. Поэтому как и где он себя поведёт — понятия не имею.
Ты заморачиваешься. Но если быть совсем дотошнымВ винде это уже не имеет значения. Там есть всем известный workaround в виде filena~1.ext.
_mktemp_s принимает имя (ну, шаблон). Что ты туда поставишь?
Ну и в конце концов, там мы копошимся в местном %TMPDIR%, где можно создать свою папку и творить в ней что угодно.
Короче, мысль следующая.
1. Твои переживания не относятся напрумую к исходной задаче.
2. Не понимаю, почему не добавить ко входным данным имя выходного файла.
3. Запретить одинаковые имена для входного и выходного файла (вполне себе годное ограничение, раз уж разработчики упомянутого sort, который годился в качестве решения, на этом не заморачивались).
4. Не придумывать проблемы на ровном месте.
По сравнению с плясками вокруг временных файлов 3й пункт выглядит очень даже ничего.
1. Твои переживания не относятся напрумую к исходной задаче.
2. Не понимаю, почему не добавить ко входным данным имя выходного файла.
3. Запретить одинаковые имена для входного и выходного файла (вполне себе годное ограничение, раз уж разработчики упомянутого sort, который годился в качестве решения, на этом не заморачивались).
4. Не придумывать проблемы на ровном месте.
По сравнению с плясками вокруг временных файлов 3й пункт выглядит очень даже ничего.
> В винде это уже не имеет значения. Там есть всем известный workaround в виде filena~1.ext.
> Ну и в конце концов, там мы копошимся в местном %TMPDIR%, где можно создать свою папку и творить в ней что угодно.
Ещё можно гипотетически предположить, что есть ФС, не поддерживающая символ "~" в именах файлов, почему бы нет.
> Ну и в конце концов, там мы копошимся в местном %TMPDIR%, где можно создать свою папку и творить в ней что угодно.
Ещё можно гипотетически предположить, что есть ФС, не поддерживающая символ "~" в именах файлов, почему бы нет.
Я не имею ничего против указания входного и выходного файлов, в общем-то. Я против того, что пользователь должен указывать ещё и пути/шаблоны для временных файлов, потому что разбираться с ними должна именно программа, пользователь об этом ничего знать не нужен. И именно поэтому, я считаю, что ты всегда придёшь к платформо-зависимости.
У винды же очень ограниченный список поддерживаемых ФС
Но, зная, майкрософт, они скорее всего для такой ФС прикрутят очередной workaround. Если нет — то да, придётся плодить очередные костыли под конкретную платформу+ФС.
Но, зная, майкрософт, они скорее всего для такой ФС прикрутят очередной workaround. Если нет — то да, придётся плодить очередные костыли под конкретную платформу+ФС.
И именно поэтому, я считаю, что ты всегда придёшь к платформо-зависимости.Почему это само по себе проблема? Если ТС реализует кроссплатформенную программу, то он уже сталкивался с такими проблемами и знает как их решить, если нужно, чтобы программа работала на винде и каком-то конкретном линаксе (а не всех возможных то это тоже нетрудно устроить, думаю, даже если на яве писать, можно во что-то такое упереться.
3. Запретить одинаковые имена для входного и выходного файла (вполне себе годное ограничение, раз уж разработчики упомянутого sort, который годился в качестве решения, на этом не заморачивались).
sort создает временные файлы, и даже позволяет создавать их в разных каталогах, а не в одном:
‘--temporary-directory=tempdir’
Use directory tempdir to store temporary files, overriding the TMPDIR environment variable. If this option is given more than once, temporary files are stored in all the directories given. If you have a large sort or merge that is I/O-bound, you can often improve performance by using this option to specify directories on different disks and controllers.
Почему это само по себе проблема? Если ТС реализует кроссплатформенную программу, то он уже сталкивался с такими проблемами и знает как их решить, если нужно, чтобы программа работала на винде и каком-то конкретном линаксе (а не всех возможных то это тоже нетрудно устроить, думаю, даже если на яве писать, можно во что-то такое упереться.Я не говорю, что это проблема, ни в коем случае
Я говорю, что это есть факт платформо-зависимости, который с таким понтом пытался отрицать ункулункулу.Но по умолчанию, заметь, он использует именно TMPDIR системы, не требуя от пользователя, указывать каталог. Да и подозреваю, что sort как раз завязан на юникс-системы, если только его не портировали для какого-нибудь cygwin/unxutils.
cygwin/unxutilsесть и там, и там. в cygwin свой маленький темп (равно как и / в unxutils не знаю.
я просто 3й пункт у понимаю как намек на то, что сорт кроме выходного файла никаких других файлов не создает, что меня удивило
цитата была из мана gnu sort, он изначально для posix систем делался вроде, такчто логично что там TMPDIR
цитата была из мана gnu sort, он изначально для posix систем делался вроде, такчто логично что там TMPDIR
Но по умолчанию, заметь, он использует именно TMPDIR системы, не требуя от пользователя, указывать каталог. Да и подозреваю, что sort как раз завязан на юникс-системы, если только его не портировали для какого-нибудь cygwin/unxutils.бугога, нет уж, это ты влетел в тред и давай показывать на все пальцем и кричать: «А-А-А,
Да, я действительно этого не учёл. Бида (
Уважаемый, я прокомментировал единственный кусок у топикстартеа, конкретно вот этот:
Переносимый код и кто что когда начал писать оставлю без комментариев.
В несколько нитей выполняется блочная сортировка файла на диске.Именно на это я указал, потому что топикстартер при этом хотел платформо-независимую реализацию. Как бы я пришёл, высказался по теме топика, топикстартеру.
Но детали реализации почти всегда платформо-зависимы.
бугога, нет уж, это ты влетел в тред и давай показывать на все пальцем и кричатьИ вот как раз тут в тред влетел ты, с отсутствием разумных замечаний по теме и своим наинтончайшим стёбом на тему того, что я дурак.
Переносимый код и кто что когда начал писать оставлю без комментариев.
Да не, мне просто смешно, на диске => обычно платформо-зависимо, причем про в несколько потоков пох, просто как бык на красную тряпку. Не понятно.
Ну да, вероятно.
Пацану сказали: "Перепиши нам чтение файла, чтобы там вообще под линуксы".
Пацан теперь ВАЩЕ ВСЕ ПРО КРОССПЛАТФОРМЕННОСТЬ знает.
Пацану сказали: "Перепиши нам чтение файла, чтобы там вообще под линуксы".
Пацан теперь ВАЩЕ ВСЕ ПРО КРОССПЛАТФОРМЕННОСТЬ знает.
Для нескольких потоков в данной ситуации как раз легко и непринужденно можно использовать OpenMP, который, насколько я знаю, в винде тоже присутствует.
Тогда я бля файлы буду MPI'ем считывать
А он решит все вышеупомянутые проблемы?
А ещё OpenMP тащемта искаробки поддерживается и гцц, и студией, а mpi надо отдельно ставить.
А ещё OpenMP тащемта искаробки поддерживается и гцц, и студией, а mpi надо отдельно ставить.
Шучу ж
Какую бы мне выбрать временную папку для каждой из следующих осей?ботай POSIX, практически во всех перечисленных тобою ОС есть tmpnam
мною лично проверено на Win32, Linux, AIX, HP-UX и Solaris.
[xoft]$ man tmpnam | grep BUGS -A 1
BUGS
Never use this function. Use mkstemp(3) or tmpfile(3) instead.
кстати почему этот tmpnam не слушается переменной TMPDIR? всё равно в /tmp/ создает
[xoft]$ TMPDIR=/var/tmp/ ./tmpnam
/tmp/filenCYQuv
а /tmp/ это очень часто tmpfs, так что создавать там временные файлы это всё равно что на памяти сортировать.
up
ищу аналог вызову sort через shell.Вот тебе идея: если не хочется включать исходники sort'а в проект, можно попробовать сделать из него библиотеку с какой-то новой удобной функцией вместо main - и заюзать эту библиотеку.
Правда такая библиотека может коварно вызвать abort или exit - и грохнуть всё приложение 8-)
Оставить комментарий
Yulka-MOl
Всем привет!Давно бьюсь над вопросом: как в C++ эффективно и красиво выполнять сортировку больших файлов.
Есть замечательная утилита sort, код которой наcтолько объёмен и изменчив от версии к версии, что перенести его в проект не получается. Приходится вызывать её через shell, задавая платформо-зависимые параметры.
Короче жуть. Подскажите, как лучше сделать? Должны же быть красивые решения.
Заранее спасибо.